Shortest paths and load scaling in scale-free trees

Abstract

The average node-to-node distance of scale-free graphs depends logarithmically on N, the number of nodes, while the probability distribution function (pdf) 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 Barabasi-Albert model into a tree with a depth-dependent branching ratio. This shows the origins of the average distance scaling and allows a demonstration of why the distribution approaches a Gaussian in the limit of N large. The load (betweenness), the number of shortest distance paths passing through any node, is discussed in the tree presentation.

8 pages, 8 figures; v2: load calculations extended

References in corpus (11)

• Statistical mechanics of complex networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Growing Scale-Free Networks with Tunable Clustering
• Epidemic dynamics in finite size scale-free networks
• Pseudofractal Scale-free Web
• Highly clustered scale-free networks
• Growing Scale-Free Networks with Small World Behavior
• Scaling properties of scale-free evolving networks: Continuous approach
• Path finding strategies in scale-free networks
• Statistical ensemble of scale-free random graphs

Cited by in corpus (29)

• Dynamics of market correlations: Taxonomy and portfolio analysis
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Layered Complex Networks
• Classification of scale-free networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Congestion and centrality in traffic flow on complex networks
• Trainspotting: Extraction and Analysis of Traffic and Topologies of Transportation Networks
• From the betweenness centrality in street networks to structural invariants in random planar graphs
• Scale-free trees: the skeletons of complex networks
• Metric structure of random networks
• Stability of shortest paths in complex networks with random edge weights
• Modeling of Information Diffusion on Social Networks with Applications to WeChat
• Topologies and Laplacian spectra of a deterministic uniform recursive tree
• Reply to "Comment on 'Universal Behavior of Load Distribution in Scale-Free Networks'"
• Recursive weighted treelike networks
• Random walks and diameter of finite scale-free networks
• Supremacy distribution in evolving networks
• Shortest path discovery of complex networks
• Distribution of Edge Load in Scale-free Trees
• Scaling of load in communications networks
• Structural and spectral properties of a family of deterministic recursive trees: Rigorous solutions
• Unraveling the structure of treelike networks from first-passage times of lazy random walkers
• Properties of weighted complex networks
• Ferromagnetic Ising spin systems on the growing random tree
• Log-periodic oscillations due to discrete effects in complex networks
• Memory effect in growing trees
• Growing spin model in deterministic and stochastic trees
• Inferring Tree Structure with Hidden Traps from First Passage Times