Exotic phase transitions of $k$-cores in clustered networks

The giant $k$-core—maximal connected subgraph of a network where each node has at least $k$ neighbors—is important in the study of phase transitions and in applications of network theory. Unlike Erdős-Rényi graphs and other random networks where $k$-cores emerge discontinuously for $k\ge 3$, we show that transitive linking (or triadic closure) leads to 3-cores emerging through single or double phase transitions of both discontinuous and continuous nature. We also develop a $k$-core calculation that includes clustering and provides insights into how high-level connectivity emerges.

Figure 1

1-core, 2-core, and 3-core of an example network from the $(c,q)$,process. The solid (dashed) lines represent ER (clustered) links. The motifs around the larger hatched node are labeled by their probabilities of occurring. That is, $u$ is the probability that a link not part of a triangle does not lead to the 3-core; $(1-v)$ is the probability that both edges of a triangle lead to the 3-core; while $vw$ is the probability that neither of the edges of the triangle lead to the 3-core.

Figure 2

Top: Plot showing the 3-core for representative values of $q$. The values of $q$ from right to left in different regimes are (i) 0.02, 0.03, 0.04, 0.05; (ii) 0.06, 0.07, 0.08; (iii) 0.09, 0.1; and (iv) 0.15, 0.2, 0.3, and 0.5. On the extreme right we see the classic discontinuous emergence [regime (i)], whereas the other three regimes show very different behavior. The forbidden region corresponds to impossible 3-core sizes for a given $c$; its solid black borders are drawn to highlight this region.

Figure 3

Top: The susceptibility of our simulations for representative values of $q$ in regimes (ii) and (iii) highlighting a double phase transition. Dashed and solid lines are obtained on networks of size ${10}^6$ (${10}^3$ realizations) and ${10}^7$ (${10}^2$ realizations), respectively. Bottom: The heights of the peaks of susceptibility for networks of size $N={10}^{5.5}$ through $N={10}^7$. The number of realizations $={10}^9/N$. The circles (squares) show the heights of the left (right) peaks. The fits to the left peaks show a slope of $0.54\pm 0.04$ for $q=0.09$ and $0.47\pm 0.04$ for $q=0.08$. The fits to the right peaks show slopes that are statistically indistinguishable from zero.

Figure 4

Panel to the left (right) showing the jump (divergence) in the slope of the giant 3-core size as a function of $c$ for $q=0.09\left(0.08\right)$.

Figure 5

Comparison between simulations of the $(c,q)$ process (solid light markers) and analytical predictions using the configuration model (dashed light lines) and the clustered configuration model (solid dark lines). We also compare the clustered configuration model to the rewired $(c,q)$ networks preserving degree-triangle distributions (open dark symbols).