Related Experiment Videos
Shortest paths and load scaling in scale-free trees
Gábor Szabó1, Mikko Alava, János Kertész
1Helsinki University of Technology, Laboratory of Physics, P.O. Box 1100, FIN-02015 HUT, Finland.
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|September 21, 2002
Summary
This study analyzes scale-free graphs, revealing how average node-to-node distances scale logarithmically with the number of nodes (N). It explains why distance distributions approach a Gaussian for large N using a tree model.
Area of Science:
- Graph theory
- Network science
- Statistical physics
Background:
- Scale-free networks exhibit unique distance properties.
- The distribution of distances in these networks can vary.
- Understanding network topology is crucial for various applications.
Purpose of the Study:
- To analyze the average node-to-node distance in scale-free graphs.
- To investigate the probability distribution of these distances.
- To explain the origins of distance scaling and Gaussian distribution limits.
Main Methods:
- Employing mean-field arguments.
- Mapping the Barabási-Albert model (m=1) to a tree structure.
- Analyzing a depth-dependent branching ratio within the tree model.
Main Results:
- Confirmed logarithmic dependence of average distance on the number of nodes (N).
- Demonstrated the emergence of Gaussian distribution for distances as N becomes large.
- Explained the origins of average distance scaling through the tree mapping.
Conclusions:
- The tree model provides insight into the distance scaling properties of scale-free networks.
- The distribution of shortest path distances tends towards a Gaussian for large networks.
- Node 'load' can be effectively analyzed within this tree framework.