Inhomogeneous substructures hidden in random networks
arXiv:cond-mat/0603515 · doi:10.1103/PhysRevE.73.037102
Abstract
We study the structure of the load-based spanning tree (LST) that carries the maximum weight of the Erdos-Renyi (ER) random network. The weight of an edge is given by the edge-betweenness centrality, the effective number of shortest paths through the edge. We find that the LSTs present very inhomogeneous structures in contrast to the homogeneous structures of the original networks. Moreover, it turns out that the structure of the LST changes dramatically as the edge density of an ER network increases, from scale free with a cutoff, scale free, to a starlike topology. These would not be possible if the weights are randomly distributed, which implies that topology of the shortest path is correlated in spite of the homogeneous topology of the random network.
arXiv comment4 pages, 4 figures
References in corpus (19)
- Statistical mechanics of complex networks
- Community structure in social and biological networks
- Lethality and centrality in protein networks
- The diameter of the world wide web
- The large-scale organization of metabolic networks
- Evolution of networks
- Who is the best connected scientist? A study of scientific coauthorship networks
- Resilience of the Internet to random breakdowns
- Self-similarity of complex networks
- Universal Behavior of Load Distribution in Scale-free Networks
- Classification of scale-free networks
- Generic scale of the "scale-free" growing networks
- Skeleton and fractal scaling in complex networks
- Optimal Paths in Disordered Complex Networks
- Traceroute sampling makes random graphs appear to have power law degree distributions
- Accuracy and Scaling Phenomena in Internet Mapping
- Scale-free trees: the skeletons of complex networks
- Effect of Disorder Strength on Optimal Paths in Complex Networks
- Scale-Free Networks Emerging from Weighted Random Graphs