Finite-size scaling of geometric renormalization flows in complex networks

Some characteristics of complex networks need to be derived from global knowledge of the network topologies, which challenges the practice for studying many large-scale real-world networks. Recently, the geometric renormalization technique has provided a good approximation framework to significantly reduce the size and complexity of a network while retaining its “slow” degrees of freedom. However, due to the finite-size effect of real networks, excessive renormalization iterations will eventually cause these important “slow” degrees of freedom to be filtered out. In this paper, we systematically investigate the finite-size scaling of structural and dynamical observables in geometric renormalization flows of both synthetic and real evolutionary networks. Our results show that these observables can be well characterized by a certain scaling function. Specifically, we show that the critical exponent implied by the scaling function is independent of these observables but depends only on the structural properties of the network. To a certain extent, the results of this paper are of great significance for predicting the observable quantities of large-scale real systems and further suggest that the potential scale invariance of many real-world networks is often masked by finite-size effects.

Figure 1

The RGN transformation process of a weighted ${\mathbb{S}}^1$ geometric model. Starting from the initial network ($l=0$), the nonoverlapping coarse-graining block (the shadowed areas in the figure) consisting of $s$ continuous nodes is defined along the circle, and the dashed lines with arrows map the nodes in the block to their supernodes in layer $l+1$. The straight solid lines in each layer represent the links between nodes, and two supernodes in layer $l+1$ will be connected only if and only if a node in one coarse-graining block in layer $l$ is connected to a node in another coarse-graining block. The figure shows the case of $s=2, s$ can be set to a larger value during the actual transformation process. Furthermore, for each layer of the network, when the total number of nodes is not divisible by $s$, the number of nodes contained in the last coarse-graining block in the layer will be less than $s$, and it will still be mapped to the supernode in the next layer.

Figure 2

The average degree ${\langle k\rangle }_l$ as a function of $l$ for renormalized networks. Each solid curve represents the variation of the average degree of a particular network in the corresponding region along the RGN flow, and the dashed lines show the result predicted by Eq. (3). In region I, ($\nu ,\sigma$) = (2.5,1.5). At the edge of the transition between regions I and II, ($\nu ,\sigma$) = (3.0,2.5). In region II, ($\nu ,\sigma$) = (3.5,2.5). In region III, ($\nu ,\sigma$) = (4.0,1.1). The average hidden degree ${\langle \kappa \rangle }_0\approx 6$ and the expected average degree ${\langle k\rangle }_0\approx 6$ for all initial networks. The sizes of the initial networks are $N_0=50000$. All results are averaged over 10 independent realizations.

Figure 3

FSS analysis of ${\mathbb{S}}^1$-network topological observables along the RGN flow. The main figures show each observable as a function of the variable $n_l$ in the process of RGN transformation, and the inset shows their scaling functions related to the variable $n_l{N}_0^{1/\delta }$. Key parameters of the ${\mathbb{S}}^1$ network are $\nu =2.5$ and $\sigma =1.5$, respectively. These networks belong to phase I, and the scaling exponent corresponding to four observables is $\delta =1.6\left(1\right)$. For observables $k_{l,\max }$ and ${\langle k\rangle }_{l,n}$, the black dashed lines show the predicted behavior of the scaling function. The average hidden degree ${\langle \kappa \rangle }_0\approx 6$ and the expected average degree ${\langle k\rangle }_0\approx 6$ for all initial networks. All results are averaged over 10 independent realizations.

Figure 4

FSS analysis of ${\mathbb{S}}^1$-network dynamic observables along the RGN flow. The main figures show each observable as a function of the variable $n_l$ in the process of RGN transformation, and the inset shows their scaling functions related to the variable $n_l{N}_0^{1/\delta }$. Key parameters of the ${\mathbb{S}}^1$ network are $\nu =2.5$ and $\sigma =1.5$, respectively. These networks belong to phase I, and the scaling exponent corresponding to four observables is $\delta =1.6\left(1\right)$. For all observables, the black dashed lines show the predicted behavior of the scaling function. The average hidden degree ${\langle \kappa \rangle }_0\approx 6$ and the expected average degree ${\langle k\rangle }_0\approx 6$ for all initial networks. All results are averaged over 10 independent realizations.

Figure 5

The contour plot of the critical exponent $\delta$. Only numerical results for the normalized average degree are given here, and our results show that other observables have very similar numerical results. The black and red solid lines in the figure are theoretical boundaries that separate these regions defined in Sec. 2b. The results show that the phase diagram for $\delta$ here has a strong correlation with the phase diagram for $\alpha$ [see Eq. (3)] in the previous study [27].

Figure 6

Self-similarity of real evolutionary networks. For each type of network, we show the complementary cumulative distribution function (CCDF) $P_c$ of node rescaled degrees $k_{res}=k/\langle k\rangle$. Topological characteristics of this series of evolutionary networks are given in Table 1.

Figure 7

FSS analysis of IG5 evolutionary networks' topological observables along the RGN flow. The main figures show each observable as a function of the variable $n_l$ in the process of RGN transformation, and the inset shows their scaling functions related to the variable $n_l{N}_0^{1/\delta }$. These networks belong to phase III, and the scaling exponent corresponding to four observables is $\delta =2.0\left(1\right)$.

Figure 8

FSS analysis of IG5 evolutionary networks' dynamic observables along the RGN flow. The main figures show each observable as a function of the variable $n_l$ in the process of RGN transformation, and the inset shows their scaling functions related to the variable $n_l{N}_0^{1/\delta }$. The scaling exponent corresponding to four observables is $\delta =2.0\left(1\right)$.