Statistical significance of communities in networks

Nodes in real-world networks are usually organized in local modules. These groups, called communities, are intuitively defined as subgraphs with a larger density of internal connections than of external links. In this work, we define a measure aimed at quantifying the statistical significance of single communities. Extreme and order statistics are used to predict the statistics associated with individual clusters in random graphs. These distributions allows us to define one community significance as the probability that a generic clustering algorithm finds such a group in a random graph. The method is successfully applied in the case of real-world networks for the evaluation of the significance of their communities.

Figure 1

(Color online) Sketch of the theoretical framework referring to the null model. Node $i$ has $k_i$ free ends to allocate. Each of them can connect to nodes within $\mathcal{C}$ or vertices belonging to the rest of the network.

Figure 2

(Color online) Distributions $f\left(k^{int}\right)$ and $g\left(k^{int}\right)$ for randomly generated networks of homogeneous degree. The (black) circles are numerical results with $N=100$, $n_{\mathcal{C}}=20$, and $k=15$. The distributions refer to external nodes of groups selected at random (inset) or by maximizing modularity (main plot). Dashed (red) curves are the approximation given by Eq. (1) and the continuous (blue) one that of Eq. (2).

Figure 3

(Color online) Probability distribution $P\left(k_w^{int}\right)$ for the internal degree of the worst node of the community calculated for groups $\mathcal{C}$ detected by maximizing the modularity in randomly generated networks of $N=100$ (left) and $N=300$ (right) with homogeneous degree $k=15$ and for groups of $n_{\mathcal{C}}=20$. The black circles are the results of numerical simulation, while the continuous blue curves correspond to the theoretical predictions derived from Eq. (3). The extreme value distribution of $f\left(k^{int}\right)$ from Eq. (1) is also plotted for comparison (violet dashed curve).

Figure 4

(Color online) Cumulative distribution of the $\mathcal{C}$-score for groups of size $n_{\mathcal{C}}=20$ obtained in random networks of $N=100$ nodes by modularity maximization. (a) Homogeneous networks with degree $k=15$. (b) Heterogeneous networks with average degree $⟨k⟩=15$. The degree distribution follows a power law $P\left(k\right)\sim k^{-\gamma }$ with $\gamma =2$. The gray areas delimit the values of $\mathcal{C}$ score that indicate group statistical significance (probability $\le 5\mathrm{\%}$).

Figure 5

(Color online) (a) $\mathcal{C}$ and $\mathcal{B}$ scores for communities in benchmarks. The disorder in the connections increases with $⟨k^{ext}⟩$. The continuous (green) curve corresponds to the target distribution obtained numerically (see text for details). (b) Distribution $P\left(m_{\mathcal{C}}^{int}\right)$, continuous curves are for the benchmark with the $⟨k^{ext}⟩$ shown over the curve. The black circles are the numerical distribution measured for an equivalent random graph with the group found by maximizing modularity.

Figure 6

(Color online) $\mathcal{C}$ score (red circles) and $\mathcal{B}$ score (blue squares) calculated for communities in LFR (heterogeneous) benchmarks. The scores are displayed as a function of the mixing parameter, $k^{ext}/k$. The benchmark networks size is $N=1000$, the $⟨k⟩=15$ with a degree sequence exponent of $\gamma =-2$ and a size of the community $n_{\mathcal{C}}=50$.

Figure 7

(Color online) Iterative application of the $\mathcal{B}$ score in order to detect the presence of an internal organization in groups. At each stage, we remove the worst node of the community and compute the $\mathcal{B}$ score for the remaining group. We consider two examples: (a) a well-defined cluster with the addition of a few random nodes; and (b) a group composed by the union of two (good) communities.

Figure 8

(Color online) Community structure for the C. Elegans metabolic network [16] obtained by modularity optimization. In (a), an overview of the graph partition is shown. In (b), we display a zoom of a single community depicting in red the nodes that are not significant group members. And (c), the $\mathcal{C}\text{−}q\text{core}$ analysis of the community.