Triadic closure as a basic generating mechanism of communities in complex networks

Most of the complex social, technological, and biological networks have a significant community structure. Therefore the community structure of complex networks has to be considered as a universal property, together with the much explored small-world and scale-free properties of these networks. Despite the large interest in characterizing the community structures of real networks, not enough attention has been devoted to the detection of universal mechanisms able to spontaneously generate networks with communities. Triadic closure is a natural mechanism to make new connections, especially in social networks. Here we show that models of network growth based on simple triadic closure naturally lead to the emergence of community structure, together with fat-tailed distributions of node degree and high clustering coefficients. Communities emerge from the initial stochastic heterogeneity in the concentration of links, followed by a cycle of growth and fragmentation. Communities are the more pronounced, the sparser the graph, and disappear for high values of link density and randomness in the attachment procedure. By introducing a fitness-based link attractivity for the nodes, we find a phase transition where communities disappear for high heterogeneity of the fitness distribution, but a different mesoscopic organization of the nodes emerges, with groups of nodes being shared between just a few superhubs, which attract most of the links of the system.

Figure 1

Basic model. One link associated with a new node $i$ is attached to a randomly chosen node $j$, the other links are attached to neighbors of $j$ with probability $p$, closing triangles, or to other randomly chosen nodes with probability $1-p$.

Figure 2

Scaling of $\Theta ={\langle {\Theta }_i\rangle }_{k_i=k}$, the average of ${\Theta }_i$, performed over nodes of degree $k_i=k$, versus the degree $k$. This scaling allows us to define the exponents $\theta =\theta \left(p\right)$ defined by Eq. $\left(6\right)$. The figure is obtained by performing 100 realizations of networks of size $n=100000$.

Figure 3

Degree distributions of the basic model, for different values of the parameter $p$. The continuous lines indicate the theoretical predictions of Eq. $\left(9\right)$, the symbols the distributions obtained from numerical simulations of the model. The figure is obtained by performing 100 realizations of networks of size $n=100000$.

Figure 4

Heat map of node-based embeddedness (a) and average clustering coefficient (b) as functions of $p$ and $m$ for the basic model. Community structure (higher embeddedness and clustering coefficient) is pronounced in the lower left region when $m$ is not too large (sparse graphs) and when the probability of triadic closure $p$ is very high. For each pair of parameter values we report the average over 50 network realizations. The white area in the upper right corresponds to systems where a single community, consisting of the whole network, is found. Here one would get a maximum value 1 for ${\xi }_n$, but it is not meaningful, and hence we discard this portion of the phase diagram, as well as in Figs. 7 and 8.

Figure 5

Schematic illustration of the formation and evolution of communities. Initial inhomogeneities in the link density make more likely the closure of triads in the denser parts, which keep growing until they become themselves inhomogeneous, leading to a split into smaller communities (different colors).

Figure 6

Evolution of node-based community embeddedness ${\xi }_n$ throughout the growth of the network. The curves refer to the extreme cases of absence of triadic closure (lower curve), yielding a random graph without communities, and of systematic triadic closure (upper curve), yielding a graph with pronounced community structure. For the latter case, we magnify in the inset the initial portion of the curve, to highlight the sudden drops of ${\xi }_n$, indicated by the arrows, which correspond to the breakout of clusters into smaller ones.

Figure 7

Heat map of node-based embeddedness (a) and average clustering coefficient (b) as functions of $P_t$ and $m$ for the model by Holme and Kim [20]. For each pair of parameter values we report the average over 50 network realizations. The white area in the upper right corresponds to systems where a single community, consisting of the whole network, is found, which is not interesting. The diagrams look qualitatively similar to that of the basic model (Fig. 4), with highest embeddedness and clustering coefficient in the lower left region.

Figure 8

Heat map of node-based embeddedness (a) and average clustering coefficient (b) as functions of the rates $\lambda$ and ${\xi }_M$ for the model by Marsili et al. [23] $\left(\eta =1\right)$. For each pair of parameter values we report the average over 50 network realizations. The white area in the upper right corresponds to systems where a single community, consisting of the whole network, is found, which is not interesting. These diagrams have better communities (higher embeddedness and clustering coefficient) towards the upper right, unlike those in Figs. 4 and 7, because of the different meaning and effect of the parameters. However, there is a strong correspondence between high clustering coefficient and strong community structure, as in the other models.

Figure 9

Degree distribution of the model with fitness, for three values of the parameter $\beta$, which indicates the heterogeneity of the distribution of the fitness of the nodes. Symbols stand for the results obtained by building the network via simulations, continuous lines of our analytical derivations. The figure is obtained by performing 100 realizations of networks of size $n=100000$ with $\nu =6$.

Figure 10

Heat map of node-based embeddedness (a) and average clustering coefficient (b) as functions of the probability of triadic closure $p$ and the heterogeneity parameter $\beta$ of the fitness distribution of the nodes, for the model with fitness. The number of new edges per node is $m=2$. For each pair of parameter values we report the average over 50 network realizations. When $\beta =0$ we recover the basic model, without fitness. We see the highest values of embeddedness in the lower left, while highest values of the clustering coefficient are in the lower right. When $\beta$ increases, we see a drastic change of structure in contrast to the previous pattern: communities disappear, whereas the clustering coefficient gets higher.

Figure 11

As Fig. 10, but for $m=5$. The picture is consistent with the case $m=2$, but communities are less pronounced.

Figure 12

Probability distributions of the scaled link density $\tilde{\rho }$ (left) and node-based embeddedness ${\xi }_n$ (right) of the communities of the fitness model, for $m=2$ and $\beta =0,6,20$. For each $\beta$ value we derived 100 network realizations, each with $100000$ nodes. We see that at $\beta =0$, the detected communities satisfy the expectations of good communities, while at $\beta =20$ they do not.

Figure 13

Picture of a network with 2000 nodes generated by the fitness model, for $p=0.97,m=2$, and $\beta =0$. Since $\beta =0$ fitness does not play a role and we recover the results of the basic model. Colors indicate communities as detected by the nonhierarchical infomap algorithm [32].

Figure 14

Picture of a network with 2000 nodes generated by the fitness model, for $p=0.97,m=2$, and $\beta =20$. The growing process is the same as in Fig. 13, but the addition of fitness changes the structural organization of the network. As seen in the inset, node aggregations form around hub nodes with high fitness. Looking at the inset we see that such aggregations do not satisfy the typical requirements for communities: they are internally treelike, and there are more external edges (blue or light gray) than internal (red or dark gray) touching its nodes. In particular, internal edges go only from regular nodes to superhubs.