Browse wiki

Jump to: navigation, search
Human navigation in networks
Abstract World around us interconnected in giant neWorld around us interconnected in giant networks and we are daily navigating and finding paths through such networks. For example, we browse the Web [2], search for connections among friends in social networks [6, 3], follow leads in citation networks of scientific literature, and look up things in cross-referenced dictionaries and encyclopedias [9]. Even though navigating networks is an essential part of our everyday lives, little is known about the mechanisms humans use to navigate networks as well as the properties of networks that allow for efficient navigation. We conduct two large scale studies of human navigation in networks. First, we present a study an instance of Milgram's small-world experiment where the task is to navigate from a given source to a given target node using only the local network information [5]. We perform a computational analysis of a planetary-scale social network of 240 million people and 1.3 billion edges and investigate the importance of geographic cues for navigating the network. Second, we also discuss a large-scale study of human wayfinding, in which, given a network of links between the concepts of Wikipedia, people play a game of finding a short path from a given start to a given target concept by following hyperlinks (Figure 1)[7]. We study more than 30,000 goal-directed human search paths through Wikipedia network and identify strategies people use when navigating information spaces [8, 9]. Even though the domains of social and information networks are very different, we find many commonalities in navigation of the two networks. Humans tend to be good at finding short paths, despite the fact that the networks are very large [8]. Human paths differ from shortest paths in characteristic ways. At the early stages of the search navigating to a high-degree hub node helps, while in the later stage, content features and geography provide the most important clues. We also observe a trade-off between simplicity and efficiency: conceptually simple solutions are more common but tend to be less efficient than more complex ones [9]. One potential reason for good human performance could be that humans possess vast amounts of background knowledge about the network, which they leverage to make good guesses about possible paths. So we ask the question: Are human-like high-level reasoning skills really necessary for finding short paths? To answer this question, we design a number of navigation agents without such skills, which use only simple numerical features [8]. We evaluate the agents on the task of navigating both networks. We observe that the agents find shorter paths than humans on average and therefore conclude that, perhaps surprisingly, no sophisticated background knowledge or high-level reasoning is required for navigating a complex network. The talk is based on joint work with Robert West and Eric Horvitz.nt work with Robert West and Eric Horvitz.
Abstractsub World around us interconnected in giant neWorld around us interconnected in giant networks and we are daily navigating and finding paths through such networks. For example, we browse the Web [2], search for connections among friends in social networks [6, 3], follow leads in citation networks of scientific literature, and look up things in cross-referenced dictionaries and encyclopedias [9]. Even though navigating networks is an essential part of our everyday lives, little is known about the mechanisms humans use to navigate networks as well as the properties of networks that allow for efficient navigation. We conduct two large scale studies of human navigation in networks. First, we present a study an instance of Milgram's small-world experiment where the task is to navigate from a given source to a given target node using only the local network information [5]. We perform a computational analysis of a planetary-scale social network of 240 million people and 1.3 billion edges and investigate the importance of geographic cues for navigating the network. Second, we also discuss a large-scale study of human wayfinding, in which, given a network of links between the concepts of Wikipedia, people play a game of finding a short path from a given start to a given target concept by following hyperlinks (Figure 1)[7]. We study more than 30,000 goal-directed human search paths through Wikipedia network and identify strategies people use when navigating information spaces [8, 9]. Even though the domains of social and information networks are very different, we find many commonalities in navigation of the two networks. Humans tend to be good at finding short paths, despite the fact that the networks are very large [8]. Human paths differ from shortest paths in characteristic ways. At the early stages of the search navigating to a high-degree hub node helps, while in the later stage, content features and geography provide the most important clues. We also observe a trade-off between simplicity and efficiency: conceptually simple solutions are more common but tend to be less efficient than more complex ones [9]. One potential reason for good human performance could be that humans possess vast amounts of background knowledge about the network, which they leverage to make good guesses about possible paths. So we ask the question: Are human-like high-level reasoning skills really necessary for finding short paths? To answer this question, we design a number of navigation agents without such skills, which use only simple numerical features [8]. We evaluate the agents on the task of navigating both networks. We observe that the agents find shorter paths than humans on average and therefore conclude that, perhaps surprisingly, no sophisticated background knowledge or high-level reasoning is required for navigating a complex network. The talk is based on joint work with Robert West and Eric Horvitz.nt work with Robert West and Eric Horvitz.
Bibtextype inproceedings  +
Doi 10.1145/2309996.2310020  +
Has author Leskovec J. +
Has extra keyword Background knowledge + , Citation networks + , Complex networks + , Computational analysis + , Decentralized searches + , Finding paths + , High-level reasoning + , Human navigation + , Human performance + , Human search + , Hyperlinks + , Information networks + , Information spaces + , Local networks + , Numerical features + , Scientific literature + , Short-path + , Shortest path + , Small worlds + , Social Networks + , Target concept + , Target nodes + , Way-finding + , Wikipedia + , Hypertext systems + , Information services + , Information use + , Websites + , Navigation +
Has keyword Decentralized search + , Information networks + , Navigation + , Small-world +
Isbn 9781450313353  +
Language English +
Number of citations by publication 0  +
Number of references by publication 0  +
Pages 143–144  +
Published in HT'12 - Proceedings of 23rd ACM Conference on Hypertext and Social Media +
Title Human navigation in networks +
Type conference paper  +
Year 2012 +
Creation dateThis property is a special property in this wiki. 7 November 2014 23:49:53  +
Categories Publications without license parameter  + , Publications without remote mirror parameter  + , Publications without archive mirror parameter  + , Publications without paywall mirror parameter  + , Conference papers  + , Publications without references parameter  + , Publications  +
Modification dateThis property is a special property in this wiki. 7 November 2014 23:49:53  +
DateThis property is a special property in this wiki. 2012  +
hide properties that link here 
Human navigation in networks + Title
 

 

Enter the name of the page to start browsing from.