Path finding strategies in scale-free networks

2001/11/30 by Beom Jun Kim, Chang No Yoon, Seung Kee Han +1 · 1 citation
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Graph theory and applications #Opinion Dynamics and Social Influence #cond-mat.dis-nn #cond-mat.stat-mech

paper · pdf · doi:10.1103/physreve.65.027103

published as Phys. Rev. E 65, 027103 (2002). · 4 pages, final form

arxiv created 2002/01/02 · openalex publication_date 2002/01/23 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We numerically investigate the scale-free network model of Barabási and Albert [A. L. Barabási and R. Albert, Science 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 is equivalent to N(0.5) is found.

Citations

• Error and attack tolerance of complex networks

Cited by

• Characteristics of Molecular-biological Systems and Process-network Synthesis

Related

• Random Networks Growing Under a Diameter Constraint
• Random and Longest Paths: Unnoticed Motifs of Complex Networks
• Realistic network growth using only local information: From random to scale-free and beyond
• Knowing a network by walking on it: emergence of scaling
• A Simple Model of Scale-free Networks Driven by both Randomness and Adaptability