Natural emergence of a core structure in networks via clique percolation

Networks are often presented as containing a “core” and a “periphery.” The existence of a core suggests that some vertices are central and form the skeleton of the network, to which all other vertices are connected. An alternative view of graphs is through communities. Multiple measures have been proposed for dense communities in graphs, the most classical being $k$-cliques, $k$-cores, and $k$-plexes, all presenting groups of tightly connected vertices. We here show that the edge number thresholds for such communities to emerge and for their percolation into a single dense connectivity component are very close, in all networks studied. These percolating cliques produce a natural core and periphery structure. This result is generic and is tested in configuration models and in real-world networks. This is also true for $k$-cores and $k$-plexes. Thus, the emergence of this connectedness among communities leading to a core is not dependent on some specific mechanism but a direct result of the natural percolation of dense communities.

Figure 1

Illustration of a 3-core (gray and black vertices inside the circle) that also contains two adjacent 4-cliques (black vertices connected through the dashed edge).

Figure 2

Upper plot: Thresholds for clique appearance (blue/dark gray) and clique percolation (red/light gray) in terms of probability $p$ for two vertices to be linked by an edge in an ER $G(N,p)$ random graph. Beyond a clique size of $k=3$ the two surfaces are very close. The threshold for the emergence of cliques for $k=2$ is close to the vertex percolation threshold. Thus, in connected networks, the values of $p$ are typically on the green (medium gray) curve hence, much above the blue (dark gray) curve. The lower plot represents the same results for scale-free networks as a function of the average degree. The similarity between the two curves is even more pronounced in this case.

Figure 3

Comparison between theory and simulations. Dots give the average over 500 simulations, and the full lines represent the theoretical results. The left column (a, c, e) shows the number of cliques of a given size. The standard error for this column is smaller than the marker size. The right column (b, d, f) shows the number of adjacent cliques to a random clique. While, for the clique number estimate, the theoretical result is a tight estimate, for the number of neighboring cliques, the theoretical result is a lower bound. The first row (a, b) is for power-law graphs with average degree 3 ($\alpha =1.8$). and the second row (c, d), with average degree 2 ($\alpha =2.2$). The third row (e, f) row is for ER graphs with an average degree of 50. All Graphs are for graphs with 500 vertices.

Figure 4

Influence of assortativity (or disassortativity) on the number of cliques for different sizes. The first row (a, b) is for power-law graphs and the second row (c, d), for ER graphs. The left column (a, c) shows the number of cliques of a given size. The right column (b, d) shows the number of adjacent cliques to a random clique.

Figure 5

Fraction of nodes in the main connectivity component as defined by $k$-cliques percolation (upper plots), $k$-cores (middle plots), and $k$-plexes (lower plots). The right columns are for the studied networks (a, c, e) and the left columns are for the scrambled version of the same networks (b, d, f). Each band is a different network. In the absence of cliques of a given size, no value is plotted. For all scrambled networks, and for the majority of real-world networks, all cliques, cores, and plexes form a single fully connected component.