Loading...
Please wait, while we are loading the content...
Similar Documents
Scale-Free properties of weighted random graphs : Minimum Spanning Trees and Percolation
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kalisky, Tomer Sreenivasan, Sameet Braunstein, Lidia A. Buldyrev, Sergey V. Havlin, Shlomo Stanley, Harry Eugene |
| Copyright Year | 2005 |
| Abstract | We study Erdös-Rényi random graphs with random weights associated with each link. In our approach, nodes connected by links having weights below the percolation threshold form clusters, and each cluster merges into a single node, thus generating a new “clusters network”. We show that this network is scale-free with λ = 2.5. Furthermore, we show that optimization causes the percolation threshold to emerge spontaneously, thus creating naturally a scale-free “clusters network”. This phenomenon may be related to the evolution of several real world scale-free networks. Our results imply that: (i) 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 λ = 2.5 (ii) the optimal path may be partitioned into segments that follow the percolation clusters, and the lengths of these segments grow exponentially with the number of clusters that are crossed (iii) the optimal path in scale-free networks with λ < 3 scales as `opt ∼ logN, and the weights along the optimal path decay exponentially with their rank. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://argento.bu.edu/hes/articles/ksbbhs04.pdf |
| Alternate Webpage(s) | http://cps-www.bu.edu/hes/articles/ksbbhs04.pdf |
| Alternate Webpage(s) | http://polymer.bu.edu/hes/articles/ksbbhs04.pdf |
| Alternate Webpage(s) | http://cps-www.bu.edu/~hes/hes/articles/ksbbhs04.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | File spanning Graph - visual representation Mathematical optimization Minimum spanning tree Node - plant part Percolation theory Percolation threshold Random graph Social network Trees (plant) Weight |
| Content Type | Text |
| Resource Type | Article |
