Path finding strategies in scale-free networks

Abstract

We numerically investigate the scale-free network model of Barab{á}si and Albert [A. L. Barab{á}si and R. Albert, Science {\bf 286}, 509 (1999)] through the use of various path finding strategies. In real networks, global network information is not accessible to each vertex, and the actual path connecting two vertices can sometimes be much longer than the shortest one. A generalized diameter depending on the actual path finding strategy is introduced, and a simple strategy, which utilizes only local information on the connectivity, is suggested and shown to yield small-world behavior: the diameter $D$ of the network increases logarithmically with the network size $N$, the same as is found with global strategy. If paths are sought at random, $D\sim N^{0.5}$ is found.

4 pages, final form

References in corpus (6)

• Emergence of scaling in random networks
• Error and attack tolerance of complex networks
• The diameter of the world wide web
• Who is the best connected scientist? A study of scientific coauthorship networks
• Mean-field theory for scale-free random networks
• Search in Power-Law Networks

Cited by in corpus (39)

• The structure and function of complex networks
• Identity and Search in Social Networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Bipartite Graphs as Models of Complex Networks
• Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity
• Integrating static and dynamic information for routing traffic
• The network topology of a potential energy landscape: A static scale-free network
• Biased random walks on complex networks: the role of local navigation rules
• Efficient local strategies for vaccination and network attack
• The Topology of Music Recommendation Networks
• Efficient routing on scale-free networks based on local information
• Characterizing the network topology of the energy landscapes of atomic clusters
• Shortest paths and load scaling in scale-free trees
• Mean-field diffusive dynamics on weighted networks
• Self-avoiding walks on scale-free networks
• Networking - A Statistical Physics Perspective
• Transportation dynamics on networks of mobile agents
• Reliability of rank order in sampled networks
• The Competition for Shortest Paths on Sparse Graphs
• Dynamic behaviors in directed networks
• Navigation in a small world with local information
• Mixing navigation on networks
• Kinetic growth walks on complex networks
• Optimal transport on supply-demand networks
• Two-dimensional small-world networks: navigation with local information
• Kinetic-growth self-avoiding walks on small-world networks
• Inter-arrival times of message propagation on directed networks
• Dynamical and Topological Aspects of Consensus Formation in Complex Networks
• Boolean Game on Scale-free Networks
• Statistical-mechanical iterative algorithms on complex networks
• A novel approach to study realistic navigations on networks
• Dependence of the average to-node distance on the node degree for random graphs and growing networks
• Characteristics of Molecular-biological Systems and Process-network Synthesis
• Efficiency of navigation in indexed networks
• Funnelling effect in networks
• Realistic searches on stretched exponential networks
• An effective local routing strategy on the BA network
• Navigating the Small World Web by Textual Cues