title: 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 "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) approximately k(-lambda) with lambda=2.5. Our results imply that the minimum spanning tree 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 suggest 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.
authors.affiliation: Minerva Center and Department of Physics, Bar-Ilan University, 52900 Ramat-Gan, Israel. kaliskt@mail.biu.ac.il
authors.forename: Tomer
authors.initials: T
authors.lastname: Kalisky
authors.forename: Sameet
authors.initials: S
authors.lastname: Sreenivasan
authors.forename: Lidia A
authors.initials: LA
authors.lastname: Braunstein
authors.forename: Sergey V
authors.initials: SV
authors.lastname: Buldyrev
authors.forename: Shlomo
authors.initials: S
authors.lastname: Havlin
authors.forename: H Eugene
authors.initials: HE
authors.lastname: Stanley