Decentralized search in networks is an activity that is often performed in online tasks. It refers to situations where a user has no global knowledge of a network's topology, but only local knowledge. On Wikipedia for instance, humans typically have local knowledge of the links emanating from a given Wikipedia article, but no global knowledge of the entire Wikipedia graph. This makes the task of navigation to a target Wikipedia article from a given starting article an interesting problem for both humans and algorithms. As we know from previous studies, people can have very efficient decentralized search procedures that find shortest paths in many cases, using intuitions about a given network. These intuitions can be modeled as hierarchical background knowledge that people access to approximate a networks' topology. In this paper, we explore the differences and similarities between decentralized search that utilizes hierarchical background knowledge and actual human navigation in information networks. For that purpose we perform a large scale study on the Wikipedia information network with over 500,000 users and 1,500,000 click trails. As our results reveal, a decentralized search procedure based on hierarchies created directly from the link structure of the information network simulates human navigational behavior better than simulations based on hierarchies that are created from external knowledge.
Описание
Exploring the differences and similarities between hierarchical decentralized search and human navigation in information networks
%0 Conference Paper
%1 Trattner:2012:EDS:2362456.2362474
%A Trattner, Christoph
%A Singer, Philipp
%A Helic, Denis
%A Strohmaier, Markus
%B Proceedings of the 12th International Conference on Knowledge Management and Knowledge Technologies
%C New York, NY, USA
%D 2012
%I ACM
%K decentralized human information navigation networks path search similarity wikipedia
%P 14:1--14:8
%R 10.1145/2362456.2362474
%T Exploring the Differences and Similarities Between Hierarchical Decentralized Search and Human Navigation in Information Networks
%U http://doi.acm.org/10.1145/2362456.2362474
%X Decentralized search in networks is an activity that is often performed in online tasks. It refers to situations where a user has no global knowledge of a network's topology, but only local knowledge. On Wikipedia for instance, humans typically have local knowledge of the links emanating from a given Wikipedia article, but no global knowledge of the entire Wikipedia graph. This makes the task of navigation to a target Wikipedia article from a given starting article an interesting problem for both humans and algorithms. As we know from previous studies, people can have very efficient decentralized search procedures that find shortest paths in many cases, using intuitions about a given network. These intuitions can be modeled as hierarchical background knowledge that people access to approximate a networks' topology. In this paper, we explore the differences and similarities between decentralized search that utilizes hierarchical background knowledge and actual human navigation in information networks. For that purpose we perform a large scale study on the Wikipedia information network with over 500,000 users and 1,500,000 click trails. As our results reveal, a decentralized search procedure based on hierarchies created directly from the link structure of the information network simulates human navigational behavior better than simulations based on hierarchies that are created from external knowledge.
%@ 978-1-4503-1242-4
@inproceedings{Trattner:2012:EDS:2362456.2362474,
abstract = {Decentralized search in networks is an activity that is often performed in online tasks. It refers to situations where a user has no global knowledge of a network's topology, but only local knowledge. On Wikipedia for instance, humans typically have local knowledge of the links emanating from a given Wikipedia article, but no global knowledge of the entire Wikipedia graph. This makes the task of navigation to a target Wikipedia article from a given starting article an interesting problem for both humans and algorithms. As we know from previous studies, people can have very efficient decentralized search procedures that find shortest paths in many cases, using intuitions about a given network. These intuitions can be modeled as hierarchical background knowledge that people access to approximate a networks' topology. In this paper, we explore the differences and similarities between decentralized search that utilizes hierarchical background knowledge and actual human navigation in information networks. For that purpose we perform a large scale study on the Wikipedia information network with over 500,000 users and 1,500,000 click trails. As our results reveal, a decentralized search procedure based on hierarchies created directly from the link structure of the information network simulates human navigational behavior better than simulations based on hierarchies that are created from external knowledge.},
acmid = {2362474},
added-at = {2017-03-29T09:57:05.000+0200},
address = {New York, NY, USA},
articleno = {14},
author = {Trattner, Christoph and Singer, Philipp and Helic, Denis and Strohmaier, Markus},
biburl = {https://www.bibsonomy.org/bibtex/29531ee6e09047836fcc042cebb454215/mbockholt},
booktitle = {Proceedings of the 12th International Conference on Knowledge Management and Knowledge Technologies},
description = {Exploring the differences and similarities between hierarchical decentralized search and human navigation in information networks},
doi = {10.1145/2362456.2362474},
interhash = {68c7fee515df10aabb4ce773c8be6a16},
intrahash = {9531ee6e09047836fcc042cebb454215},
isbn = {978-1-4503-1242-4},
keywords = {decentralized human information navigation networks path search similarity wikipedia},
location = {Graz, Austria},
numpages = {8},
pages = {14:1--14:8},
publisher = {ACM},
series = {i-KNOW '12},
timestamp = {2017-03-29T09:57:05.000+0200},
title = {Exploring the Differences and Similarities Between Hierarchical Decentralized Search and Human Navigation in Information Networks},
url = {http://doi.acm.org/10.1145/2362456.2362474},
year = 2012
}