Navigating Networks with Limited Information

Abstract

We study navigation with limited information in networks and demonstrate that many real-world networks have a structure which can be described as favoring communication at short distance at the cost of constraining communication at long distance. This feature, which is robust and more evident with limited than with complete information, reflects both topological and possibly functional design characteristics. For example, the characteristics of the networks studied derived from a city and from the Internet are manifested through modular network designs. We also observe that directed navigation in typical networks requires remarkably little information on the level of individual nodes. By studying navigation, or specific signaling, we take a complementary approach to the common studies of information transfer devoted to broadcasting of information in studies of virus spreading and the like.

6 pages, 6 figures. For associated Java applet, see http://cmol.nbi.dk/models/bit/bit.html

References in corpus (11)

• Specificity and stability in topology of protein networks
• Search in Power-Law Networks
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Networks and Cities: An Information Perspective
• Modularity and Extreme Edges of the Internet
• Diffusion, localization and dispersion relations on ``small-world'' lattices
• Hierarchy Measures in Complex Networks
• Topological Properties of Citation and Metabolic Networks
• Hide and seek on complex networks
• Disease Spreading in Structured Scale-Free Networks
• Modeling Dynamics of Information Networks

Cited by in corpus (15)

• Critical phenomena in complex networks
• Time Critical Social Mobilization: The DARPA Network Challenge Winning Strategy
• Biased random walks on complex networks: the role of local navigation rules
• Transport on Complex Networks: Flow, Jamming and Optimization
• Characteristic times of biased random walks on complex networks
• Searchability of Networks
• Two-dimensional small-world networks: navigation with local information
• The Gradient Mechanism in a Communication Network
• Degree Landscapes in Scale-Free Networks
• Smart random walkers: the cost of knowing the path
• Inter-arrival times of message propagation on directed networks
• Pathlength scaling in graphs with incomplete navigational information
• Message Transfer in a Communication Network
• Decentralized Routing on Spatial Networks with Stochastic Edge Weights
• Networks and Our Limited Information Horizon