Network cloning unfolds the effect of clustering on dynamical processes

We introduce network $L$-cloning, a technique for creating ensembles of random networks from any given real-world or artificial network. Each member of the ensemble is an $L$-cloned network constructed from $L$ copies of the original network. The degree distribution of an $L$-cloned network and, more importantly, the degree-degree correlation between and beyond nearest neighbors are identical to those of the original network. The density of triangles in an $L$-cloned network, and hence its clustering coefficient, is reduced by a factor of $L$ compared to those of the original network. Furthermore, the density of loops of any fixed length approaches zero for sufficiently large values of $L$. Other variants of $L$-cloning allow us to keep intact the short loops of certain lengths. As an application, we employ these network cloning methods to investigate the effect of short loops on dynamical processes running on networks and to inspect the accuracy of corresponding tree-based theories. We demonstrate that dynamics on $L$-cloned networks (with sufficiently large $L$) are accurately described by the so-called adjacency tree-based theories, examples of which include the message passing technique, some pair approximation methods, and the belief propagation algorithm used respectively to study bond percolation, SI epidemics, and the Ising model.

Figure 1

(a) To create an $L$-cloned network, we start with $L$ clones of the original network. In particular, for each node $i$ of the original network there exist $L$ copies $i_1,i_2,...,i_L$, each placed in one of the $L$ layers. (b) We then reassign existing links uniformly at random, subject to the following restriction: If nodes $i$ and $j$ are connected in the original network, then each copy of $i$ is connected to exactly one copy of $j$ and each copy of $j$ is connected to exactly one copy of $i$.

Figure 2

The dependence of clustering coefficient $C$ of $L$-cloned networks on $L$ (blue circles). Here $C_1$ is the value of the clustering coefficient of the original $\left(L=1\right)$ network. The red dashed line is $C_1/L$.

Figure 3

Schematic of a $\gamma (3,3)$ network described in the text. All nodes have degree 3. Each node is part of exactly one triangle and has exactly one single edge that is not part of any triangle. The triangles are randomly connected via single edges. The dashed lines represent connections to nodes not included in the schematic.

Figure 4

Bond percolation on (a) a $\gamma (3,3)$ network with approximately ${10}^4$ nodes and (b) the U.S. power grid network and their respective $L$-cloned networks. Here $L=1$ indicates the result of numerical simulations on the original network. The result of the $A_{ij}$ theory is shown by the dashed line. The result of numerical simulation on $L$-cloned networks approaches the $A_{ij}$ theory as $L$ is increased. On the U.S. power grid network the prediction made by the $A_{ij}$ theory is different from and more accurate than that of the $P_{k,k^{\prime }}$ theory studied in Refs. [10, 21]. Nevertheless, the two theories have the same result on $\gamma (3,3)$ networks. The numerical results were derived from averaging over at least 100 realizations of the bond percolation process.

Figure 5

For a large number of layers, the simulation results of bond percolation on $L_{-3}$-cloned versions of the western U.S. power grid [17] network converges to a curve that has an appreciable difference from the $A_{ij}$ theory. This indicates that the presence of triangles causes a significant error in the theoretical prediction. Similarly, the numerics for $L_{-3,-4}$-cloned networks have an appreciable deviation from the theory; this deviation is even larger than that of $L_{-3}$-cloned networks, indicating that squares have also an appreciable effect on the accuracy of the theory. These deviations are not due to the smaller number of links rewired in $L_{-3}$ and $L_{-3,-4}$ cloned networks, since the numerics on $L_{f(3,4)}$-cloned networks (in which the fraction of rewired links is as low as that of $L_{-3,-4}$-cloned networks) with a large number of layers matches the theory very well. The number of layers is indicated by $L$ for each curve and the index of $L$ denotes the type of cloning.

Figure 6

Numerical simulations and $A_{ij}$ theory for SI model on (a) a $\gamma (3,3)$ network with approximately ${10}^4$ nodes and (b) the U.S. power grid network and their corresponding $L$-cloned versions. Here $L=1$ indicates the results of numerical simulations on original networks. The $A_{ij}$ theory is not accurate on the original clustered networks, however its performance improves with $L$ on $L$-cloned networks.

Figure 7

For a sufficiently large number of layers, the results of numerical simulations for SI epidemics on $L_{-3}$- or $L_{-3,-4}$-cloned versions of the power grid network approach a specific curve, which is different from the $A_{ij}$ theory curve; this is in contrast to the convergence of the results on $L$-cloned networks to the $A_{ij}$ theory. Although the fraction of reassigned (rewired) links in $L_{-3}$- or $L_{-3,-4}$-cloned networks is smaller than that of $L$-cloned networks, this is not the cause of difference in the corresponding numerical results, as the numerics on $L_{f(3,4)}$-cloned networks (in which the fraction of reassigned links is the same as that of the $L_{-3,-4}$-cloned network) with a large number of layers match very well with the $A_{ij}$ theory.

Figure 8

Magnetization $M$ versus inverse temperature for the Ising model on a $\gamma (3,3)$ network and its $L$-cloned versions. Here $L=1$ indicates the result of numerical simulations on the original $\gamma (3,3)$ network with approximately ${10}^6$ nodes, averaged over 20 realizations of the Ising model. The $A_{ij}$ theory is inaccurate on this network; however its performance improves appreciably with $L$ on the $L$-cloned versions of this network.