Growing networks with superjoiners

We study the Krapivsky-Redner (KR) network growth model, but where new nodes can connect to any number of existing nodes, $m$, picked from a power-law distribution $p\left(m\right)\sim m^{-\alpha }$. Each of the $m$ new connections is still carried out as in the KR model with probability redirection $r$ (corresponding to degree exponent ${\gamma }_{\mathrm{KR}}=1+1/r$ in the original KR model). The possibility to connect to any number of nodes resembles a more realistic type of growth in several settings, such as social networks, routers networks, and networks of citations. Here we focus on the in-, out-, and total-degree distributions and on the potential tension between the degree exponent $\alpha$, characterizing new connections (outgoing links), and the degree exponent ${\gamma }_{\mathrm{KR}}\left(r\right)$ dictated by the redirection mechanism.

Figure 1

“Phase diagram” for the superjoiners model: The model exhibits different asymptotic behavior and divides into four regions in the $(\alpha ,r)$ space, with regard to the exponents characterizing the asymptotic power-law behavior of in-, out-, and total-degree distribution (${\gamma }_{\mathrm{in}}$, ${\gamma }_{\mathrm{out}}$, and $\gamma$, respectively). For $\alpha >2$, the networks are sustainable, $M\sim N^{\beta }$, $\beta =1$, and $\gamma =min\{{\gamma }_{\mathrm{in}},{\gamma }_{\mathrm{out}}\}$, yielding two distinct “phases” separated by the curve ${\gamma }_{\mathrm{out}}={\gamma }_{\mathrm{in}}$, or $\alpha =1+1/r$. For $\alpha <2$, the networks are unsustainable, with $\beta >1$, and the region divides into two distinct “phases” separated by the line $\alpha =1$. Additionally, the superjoiners model is ill-defined in the region marked as “extreme nonsustainability,” for $r>1/(3-\alpha )$, as conflicts arise in the implementation of the superjoiners growth model. The various results summarized in this diagram are derived throughout the paper.

Figure 2

Out-degree $G_l\left(t\right)$ for $\alpha =0.5$ (upper curve) and $\alpha =2$ (lower curve), for $t=10000$. The symbols represent a direct summation of Eq. (13) and the solid curves are fit from Eq. (14). Slopes of $l^{-\alpha }$ are shown as broken lines, for comparison.

Figure 3

In-degree $F_k\left(t\right)$ for $\alpha =1$, $r=0.3$ (a) and $\alpha =3$, $r=0.5$ (b), as computed from Eq. (15) (solid line) and from simulations ($\circ$) for $t=10000$, averaged over 50 runs. The predicted asymptotic slopes, of ${\gamma }_{\mathrm{out}}=0$ and ${\gamma }_{\mathrm{out}}=1+1/r=3$, respectively, are shown for comparison (broken line).

Figure 4

Total degree distribution $H_q\left(t\right)$ in small networks of $t=1000$ for (a) $\alpha =0.5$, $r=0.2$; (b) $\alpha =1.5$, $r=0.4$; (c) $\alpha =3$, $r=0.4$; and (d) $\alpha =3$, $r=0.8$. The solid curves represent the direct analytical approach (i), while dashed-dotted curves are computed from approach (ii). Simulation results, averaged over 1000 runs, are denoted by open circles ($\circ$). For comparison, the theoretical long-time asymptotic prediction of the exponent $\gamma$ is indicated by dashed lines.

Figure 5

Conflicts. The fraction of conflicts that arise in the construction of networks up to time $t=5000$ for each of the three strategies described in the text is indicated in different shadings, according to the scheme of the bars at the right. The theoretical curve $r=1/(3-\alpha )$ reasonably separates between regions of many conflicts (extreme unsustainability) and almost no conflicts in all three cases.

Figure 6

Largest Laplacian eigenvalue ${\lambda }_N\left(L\right)$ as a function of $\alpha$ in the superjoiner model averaged over 100 network simulations per parameter combination. The dashed curve shows the analytical estimate given by Eq. (33).