Densification and structural transitions in networks that grow by node copying

We introduce a growing network model, the copying model, in which a new node attaches to a randomly selected target node and, in addition, independently to each of the neighbors of the target with copying probability $p$. When $p<\frac{1}{2}$, this algorithm generates sparse networks, in which the average node degree is finite. A power-law degree distribution also arises, with a nonuniversal exponent whose value is determined by a transcendental equation in $p$. In the sparse regime, the network is “normal,” e.g., the relative fluctuations in the number of links are asymptotically negligible. For $p\ge \frac{1}{2}$, the emergent networks are dense (the average degree increases with the number of nodes $N$), and they exhibit intriguing structural behaviors. In particular, the $N$ dependence of the number of $m$ cliques (complete subgraphs of $m$ nodes) undergoes $m-1$ transitions from normal to progressively more anomalous behavior at an $m$-dependent critical values of $p$. Different realizations of the network, which start from the same initial state, exhibit macroscopic fluctuations in the thermodynamic limit: absence of self-averaging. When linking to second neighbors of the target node can occur, the number of links asymptotically grows as $N^2$ as $N\to \infty$, so that the network is effectively complete as $N\to \infty$.

Figure 1

The copying model. A new node (filled circle) attaches to a random target (open circle) and independently to each of the friends of the target (squares) with probability $p$.

Figure 2

Realizations of the copying model for $p=0.1$, 0.4, 0.7, and 1 for $N=100$, and a summary of the dense regimes. For simplicity, only the last of the structural transitions is shown (see Sec. 4).

Figure 3

The scaled degree distributions in the sparse regime for (a) $p=0.1$ and (b) $p=0.4$, For each $N$, the number of realizations is ${10}^{10}/N$.

Figure 4

The scaled degree distributions multiplied by $\langle k\rangle$ versus scaled degree in the dense regime for (a) $p=0.6$, (b) $p=0.75$, and (c) $p=0.9$. For each $N$, the number of realizations is ${10}^{10}/N$.

Figure 5

The degree distributions for two representative realizations of the copying model for $p=0.75$ for a network of $N={10}^5$ nodes. The data are averaged over a 20-point range.

Figure 6

Counting triangles. The target node (open circle) has five neighbors (squares), two of which are joined by “clustering” links (heavy lines). When a new node (filled circle) is introduced, three copying links (dashed) create three new triangles (one is hatched for illustration) and one new triangle by induced linking (shaded).

Figure 7

The transitivity $\tau \left(N\right)$ (solid symbols) and the local clustering coefficient $\text{CC}\left(N\right)$ (open symbols) versus the copying probability $p$ for networks of different sizes. The solid smooth curve is the analytical expression (48). The dotted curves are guides to the eye.

Figure 8

Semilogarithmic plot of the distribution $P(L,N)$ versus the scaled number of links for $N={10}^4$ and representative values of $p$. Data are collected over ${10}^6$ realizations for $p$ up to 0.7 and ${10}^5$ realizations for $p=0.9$.

Figure 9

Skewness (solid symbols) and excess kurtosis (open symbols) of the link distribution as a function of $N$.

Figure 10

The scaled distribution of the number of links for the copying model with $p=0.7$.

Figure 11

Numerical evaluation of the probability for network completeness, $\mathcal{C}\left(N\right)$ from Eq. (57), for fixed $p=\frac{1}{2}$ and representative values of $q$. The saturation is obvious, $\mathcal{C}\left(\infty \right)>0$ for all $q>0$. The ultimate values of $\mathcal{C}\left(\infty \right)$ can be very small for small $q$.

Figure 12

The $N$ dependence of the number of links for second-neighbor copying with $q=p^2$.