Scale-free networks emerging from weighted random graphs

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\left(k\right)\sim 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.

Figure 1

Sketch of the supernode network. (a) The original ER network, partitioned into percolation clusters whose sizes $s$ are power-law distributed, with $n_s\sim s^{-\tau }$ where $\tau =2.5$ for ER graphs. The black links are the links with weights below $p_c$, the dotted links are the links that are removed by the bombing algorithm, and the gray links are the links whose removal will disconnect the network (and therefore are not removed even though their weight is above $p_c$). (b) The supernode network: the nodes are the clusters in the original network and the links are the links connecting nodes in different clusters (i.e., dotted and gray links). The supernode network is scale-free with $P\left(k\right)\sim k^{-\lambda }$ and $\lambda =2.5$. Notice the existence of self loops and of double connections between the same two supernodes. (c) The minimum spanning tree (MST), composed of black and gray links only. (d) The MST of the supernode network (gray tree), which is obtained by bombing the supernode network (thereby removing the dotted links), or equivalently, by merging the clusters in the MST to supernodes. The gray tree is scale-free, with $\lambda =2.5$.

Figure 2

(Color online) The degree distribution of the supernode network of Fig. 1b, where the supernodes are the percolation clusters, and the links are the links with weights larger than $p_c$ $(엯)$. The distribution exhibits a scale-free tail with $\lambda \approx 2.5$. If we choose a threshold less than $p_c$, we obtain the same power-law degree distribution with an exponential cutoff. The different symbols represent slightly different threshold values: $p_c-0.03$ $(◻)$ and $p_c-0.05$ $(▵)$. The original ER network has $N=50000$ and $⟨k⟩=5$. Note that for $k\approx ⟨k⟩$ the degree distribution has a maximum.

Figure 3

(Color online) (a) The degree distribution of the gray tree [the MST of the supernode network, shown in Fig. 1d], in which the supernodes are percolation clusters and the links are the gray links. Different symbols represent different threshold values: $p_c$ $(엯)$, $p_c+0.01$ $(◻)$, and $p_c+0.02$ $(▵)$. The distribution exhibits a scale-free tail with $\lambda \approx 2.5$, and is relatively insensitive to changes in $p_c$. (b) The average path length ${\ell }_{\mathrm{gray}}$ on a the gray tree as a function of original network size. It is seen that ${\ell }_{\mathrm{gray}}\sim \ln N_{\mathrm{sn}}\sim \ln N$.

Figure 4

(Color online) (a) The average weights ${\overline{w}}_r$ along the optimal path of an ER graph with $⟨k⟩=5$, sorted according to their rank. Different symbols represent different system sizes: $N=2000$ $(엯)$, $N=8000$ $(◻)$, and $N=32000$ $(▵)$. Below $p_c=0.2$, the weights are uniformly distributed, while weights above $p_c$ are significantly higher and independent of $N$. (b) Cluster size vs the minimal gray link emerging from each cluster, for ER graphs with $⟨k⟩=5$ and $N=10000$. Small clusters are associated with higher weights because they have a small number of exits and thus cannot be optimized.