Random sequential renormalization and agglomerative percolation in networks: Application to Erdös-Rényi and scale-free graphs

We study the statistical behavior under random sequential renormalization (RSR) of several network models including Erdös-Rényi (ER) graphs, scale-free networks, and an annealed model related to ER graphs. In RSR the network is locally coarse grained by choosing at each renormalization step a node at random and joining it to all its neighbors. Compared to previous (quasi-)parallel renormalization methods [Song et al., Nature (London) 433, 392 (2005)], RSR allows a more fine-grained analysis of the renormalization group (RG) flow and unravels new features that were not discussed in the previous analyses. In particular, we find that all networks exhibit a second-order transition in their RG flow. This phase transition is associated with the emergence of a giant hub and can be viewed as a new variant of percolation, called agglomerative percolation. We claim that this transition exists also in previous graph renormalization schemes and explains some of the scaling behavior seen there. For critical trees it happens as $N/N_0\to 0$ in the limit of large systems (where $N_0$ is the initial size of the graph and $N$ its size at a given RSR step). In contrast, it happens at finite $N/N_0$ in sparse ER graphs and in the annealed model, while it happens for $N/N_0\to 1$ on scale-free networks. Critical exponents seem to depend on the type of the graph but not on the average degree and obey usual scaling relations for percolation phenomena. For the annealed model they agree with the exponents obtained from a mean-field theory. At late times, the networks exhibit a starlike structure in agreement with the results of Radicchi et al. [Phys. Rev. Lett. 101, 148701 (2008)]. While degree distributions are of main interest when regarding the scheme as network renormalization, mass distributions (which are more relevant when considering “supernodes” as clusters) are much easier to study using the fast Newman-Ziff algorithm for percolation, allowing us to obtain very high statistics.

Figure 1

One step of RSR with radius $b=1$. The randomly chosen target node [yellow (white)] absorbs all its nearest neighbors [red (light gray)]. All links to the absorbed nodes [blue (dark gray)] are then redirected to the target. Alternatively, one can view the supernode as a cluster that grows by eating all its neighboring clusters. RSR with any $b>1$ can be performed by applying the above procedure on the same target $b$ times.

Figure 2

Time dependence of network size, $N$, in rescaled units. The size decreases monotonically under RSR. Data is obtained from ER graphs with ${\langle k\rangle }^{*}=2$ under RSR with $b=1$. The curves with dashed lines are obtained by averaging $t$ values corresponding to fixed $N$, and the curves with solid lines are obtained by averaging $N$ for fixed $t$. The magenta (gray) solid line shows the mean-field theory prediction (see Sec. 4). The two averages differ when mean-field theory breaks down due to fluctuations. In the rest of the paper we choose $N$ as the independent variable and average all other quantities at fixed $N$. Numbers in the legend show the initial size of the ER graph, $N^{*}$, from which the initial giant components are obtained.

Figure 3

Plot of $k_{\max }/N_0$ vs $N/N_0$ for ER graphs with ${\langle k\rangle }^{*}=2$ and several initial sizes. Note that the direction of the RSR flow is from right to left. While $k_{\max }/N_0$ is close to zero in the mean-field regime, the hub at late times absorbs a finite and increasing fraction of the nodes. The transition gets sharper with increased system size. (Inset) Similar behavior for the rescaled maximal cluster mass $M_{\max }/N_0$. Note that $M_{\max }$ always increases monotonically under RSR, whereas $k_{\max }$ has to finally decrease. Using the Newman-Ziff algorithm mass related properties can be measured on much larger systems than degree related properties.

Figure 4

The largest degree $k_{\max }$ and the second largest degree, $k_{\max ,2}$, are of comparable size in the mean-field regime, but in the hub regime a giant hub takes over and the second largest degree shrinks. This behavior is also consistent with a continuous percolation transition and shows that there is only one outstanding hub (cluster) in every network. The inset shows the same behavior for the largest and the second largest mass. The data are obtained from ER graphs with ${\langle k\rangle }^{*}=2$.

Figure 5

Cluster mass distribution at different stages of the RSR flow for ER graphs of $N^{*}={10}^6$ nodes, and ${\langle k\rangle }^{*}=2$. This distribution broadens and approaches a power law $p_m\sim m^{-\tau }$ as $x=N/N_0$ decreases. The power law is broadest at $x^{*}\left(N_0\right)=0.645$, for this system size. For $N_0\to \infty$, the critical point converges to $x^{*}\to x_c=0.688$ (the green dashed-dotted curve). For $x<x^{*}$ a giant cluster emerges and a gap expands between this cluster and the rest of the distribution. Note that the size distribution of the giant cluster has a shoulder on the right (unlike OP). This is due to the possibility of selecting the hub as a target node and is discussed in more detail in Sec. V.

Figure 6

Convergence of the effective critical point, $x^{*}\left(N_0\right)$, to $x_c=0.688$ as the system size increases. (Inset) The critical point $x_c$ and the exponent $1/\nu$ are consistent with the values $x_c=0.688$ and $-1/\nu =-0.225$, as indicated by the slope of the straight line.

Figure 7

Data collapse using the FSS ansatz in Eq. (1) for the mass distribution at $x^{*}\left(N_0\right)$. The exponent $D=0.6$ gives the best data collapse, and $\tau =2.67$ fits the power law (see the inset). These values are consistent with Eq. (6).

Figure 8

Degree distributions for $N^{*}=1.2\times {10}^5$ at different stages of the RSR flow. The initial, narrow distribution gets broader and approaches a power law $p_k=k^{-{\tau }_k}$ close to the transition. Then a giant hub stands out and a gap opens between the hub and the rest of the nodes.

Figure 9

Scaling plot of $M_{\max }$ in the critical region. The value of $x_c=0.688$ in here and the following figures is the same as in Fig. 6, and the critical exponents are those given in Table . The inset shows that the exponents ${\nu }_k$ and ${\beta }_k$ for the maximum degree are the same as those for the maximum mass within error.

Figure 10

Data collapse for the second largest mass and the second largest degree. Again $\nu$ is taken from Table , while $\sigma$ is fitted for optimal collapse. The value of ${\sigma }_k$ used in the inset is equal to $\sigma$, which is here $\sigma =0.395$.

Figure 11

Scaling plot of the second moment of the mass distribution, $\langle m^2\rangle$, for ER graphs, with $\gamma /\nu =0.17\pm 0.03$. The inset shows the same plot for ${\langle m^2\rangle }_{ex}$. The same exponents are obtained.

Figure 12

Scaling plot for the variance of the maximum degree, with $x_c=0.688$, $1/\nu =0.225$, and ${\alpha }_k/\nu =1.53\pm 0.02$.

Figure 13

Comparison between the annealed model (AM), mean-field theory (MFT), and ER graphs with ${\langle k\rangle }^{*}=2$. There is good agreement between theory and data in the mean-field regime $x\ge x_c$. After the transition the effect of loops in ER graphs can no longer be ignored and results in smaller $\langle k\rangle$ for ER graphs.

Figure 14

FSS analysis of the second moment of the degree distribution, $\langle k^2\rangle$, close to criticality for the AM. The values of $x_c=0.718$ and $\gamma =0.5$ used in the plot are those obtained from the MFT. While the exponent $1/\nu =0.225\pm 0.015$, obtained from the FSS data collapse, is similar to ER graphs, the exponent $\gamma$ is different from $\gamma =0.88$ in ER graphs.

Figure 15

Scatter plot of $t$ vs $N$ in rescaled units for ER graphs with ${\langle k\rangle }^{*}=2$ and $N^{*}=120\times {10}^3$. The color map shows the relative frequency of each $(N,t)$ pair in the ensemble. The main, intermediate, and weak bands correspond to realizations where the giant hub has been hit zero, one, or two times, respectively. The inset shows the probability that the giant hub is targeted $f$ times by RSR.

Figure 16

The relative maximum degree, $\kappa =k_{\max }/(N-1)$, vs $N/N_0$ for different system sizes. The plot shows that the network is starlike at late times since $\kappa$ approaches 1. (Inset) Variance of $\kappa$ vs $N/N_0$. Although the qualitative behavior of graphs under RSR at late times is the same as for the (quasi-)parallel renormalization method [18], the quoted exponents are different.

Figure 17

Data collapse for the distribution of the last sizes. The distribution follows the FSS ansatz in Eq. (47) with ${\tau }_s=1.40\pm 0.15$ and $D_s=0.25\pm 0.05$, except for the leftmost points. The reason for their special behavior is given in [21].

Figure 18

Rescaled maximum degree, $k_{\max }/N_0$ vs system size for ER graphs with $N^{*}=30000$. The transition shifts to the right with increase of ${\langle k\rangle }^{*}$.

Figure 19

Scaling of $M_{\max }$ for ER graphs with ${\langle k\rangle }^{*}=4$. The values $x_c=0.865\pm 0.010$, $1/\nu =0.215\pm 0.030$, and $1-\beta /\nu =0.62\pm 0.05$, obtained by finding the best data collapse, agree with Eq. (37) and the exponents for ER graphs with ${\langle k\rangle }^{*}=2$ within error bars.

Figure 20

Flow of the order parameter under RSR with box radius $b=2$ for ER graphs of ${\langle k\rangle }^{*}=2$ and several sizes. The data show a sharp transition at early times, but a clean FSS analysis including precisely locating the critical point is not numerically tractable.

Figure 21

FSS analysis of $k_{\max }/N_0$ for the BA model. The critical point is pushed toward one, and there is a perfect data collapse after the hubs are well established.

Figure 22

FSS analysis of $M_{\max }$ and ${\langle m^2\rangle }_{ex}$ for the BA model. The critical point is set at $x_c=1$. The exponents $1/\nu =0.18\pm 0.02$, $D=0.5\pm 0.1$, and $\gamma /\nu =0.25\pm 0.03$ are obtained from the data collapse.

Figure 23

Log-log plot of normalized maximum degree $k_{\max }/N_0$ vs $M_{\max }/N_0$ for ER graphs with ${\langle k\rangle }^{*}=2$ and size $N^{*}=1.2\times {10}^5$. These are proportional to each other in a region close to criticality which extends over larger domains with increase of system size. While $M_{\max }$ increases with $N_0$ monotonically, $k_{\max }$ is confined to the current system size $N$ and starts to decrease deep in the hub phase. The inset shows the ratio of maximal mass and degree on a linear scale. The curve is linear in the critical region.

Figure 24

Scatter plot of masses and degrees of all clusters close to criticality. The data are obtained from one RSR trajectory of an ER graph of $N^{*}=1.2\times {10}^5$ nodes, with ${\langle k\rangle }^{*}=2$ at $N/N_0=0.688$. The red line with circles shows the average degree of clusters of a given mass, and the green line with squares shows the average masses of nodes with a given degree. The inset shows the number of clusters of a given mass ($w_m$) and the number of nodes of a given degree ($w_k$).