Scale-Free Networks Emerging from Weighted Random Graphs

Abstract

We study Erdös-Rényi random graphs with random weights associated with each link. We generate a new ``Supernode network'' by merging all nodes connected by links having weights below the percolation threshold (percolation clusters) into a single node. We show that this network is scale-free, i.e., the degree distribution is $P(k)\sim k^{-\lambda }$ with $\lambda =2.5$. Our results imply that the minimum spanning tree (MST) in random graphs is composed of percolation clusters, which are interconnected by a set of links that create a scale-free tree with $\lambda =2.5$. We show that optimization causes the percolation threshold to emerge spontaneously, thus creating naturally a scale-free ``supernode network''. We discuss the possibility that this phenomenon is related to the evolution of several real world scale-free networks.

References in corpus (2)

• Optimal Paths in Disordered Complex Networks
• Scale-free trees: the skeletons of complex networks

Cited by in corpus (9)

• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Optimal Paths in Complex Networks with Correlated Weights: The World-wide Airport Network
• Optimization of the post-crisis recovery plans in scale-free networks
• A New Methodology for Generalizing Unweighted Network Measures
• The process of coevolutionary competitive exclusion: speciation, multifractality and power-laws in correlation
• On Strategic Defense of Stochastic Networks
• Inhomogeneous substructures hidden in random networks
• Extrema Analysis of Node Centrality in Weighted Networks
• The Continuous Node Degree: a New Measure for Complex Networks