Searchability of Networks
arXiv:cond-mat/0505400 · doi:10.1103/PhysRevE.72.046117
Abstract
We investigate the searchability of complex systems in terms of their interconnectedness. Associating searchability with the number and size of branch points along the paths between the nodes, we find that scale-free networks are relatively difficult to search, and thus that the abundance of scale-free networks in nature and society may reflect an attempt to protect local areas in a highly interconnected network from nonrelated communication. In fact, starting from a random node, real-world networks with higher order organization like modular or hierarchical structure are even more difficult to navigate than random scale-free networks. The searchability at the node level opens the possibility for a generalized hierarchy measure that captures both the hierarchy in the usual terms of trees as in military structures, and the intrinsic hierarchical nature of topological hierarchies for scale-free networks as in the Internet.
9 pages, 10 figures
References in corpus (16)
- Community structure in social and biological networks
- Specificity and stability in topology of protein networks
- Who is the best connected scientist? A study of scientific coauthorship networks
- Search in Power-Law Networks
- Scale-Free Networks are Ultrasmall
- 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
- Information Horizons in Networks
- Modeling Dynamics of Information Networks
- Navigating Networks with Limited Information
Cited by in corpus (11)
- Characterization of complex networks: A survey of measurements
- Street-based Topological Representations and Analyses for Predicting Traffic Flow in GIS
- Search in Complex Networks : a New Method of Naming
- Phase Synchronization in Railway Timetables
- Smart random walkers: the cost of knowing the path
- Pathlength scaling in graphs with incomplete navigational information
- Network-Based Approach for Modeling and Analyzing Coronary Angiography
- Quantifying navigation complexity in transportation networks
- Optimal transport with constraints: from mirror descent to classical mechanics
- Searchability of central nodes in networks
- Simplification of networks via conservation of path diversity and minimisation of the search information