Shortest paths and load scaling in scale-free trees

2002/03/31 by Gábor Szabó, Gabor Szabo, Mikko J. Alava +3
Mathematics · Physics and Astronomy · #Betweenness centrality #Combinatorics #Complex Network Analysis Techniques #Complex network #Gaussian #Gaussian free field #Geometry #Mathematics #Node (physics) #Physics #Scale-free network #Scaling #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #Tree (set theory) #cond-mat.dis-nn #cond-mat.stat-mech

paper · pdf · doi:10.1103/physreve.66.026101

published as Phys. Rev. E 66, 026101 (2002) · 8 pages, 8 figures; v2: load calculations extended

arxiv created 2002/05/08 · openalex publication_date 2002/08/07 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

The average node-to-node distance of scale-free graphs depends logarithmically on N, the number of nodes, while the probability distribution function of the distances may take various forms. Here we analyze these by considering mean-field arguments and by mapping the m=1 case of the Barabási-Albert model into a tree with a depth-dependent branching ratio. This shows the origins of the average distance scaling and allows one to demonstrate why the distribution approaches a Gaussian in the limit of N large. The load, the number of the shortest distance paths passing through any node, is discussed in the tree presentation.

Citations

• Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
• Organization of growing random networks
• Emergence of scaling in random networks
• Epidemic Spreading in Scale-Free Networks
• Path finding strategies in scale-free networks
• Growing scale-free networks with small-world behavior
• Statistical mechanics of complex networks
• Random graphs with arbitrary degree distributions and their applications