Measuring the significance of community structure in complex networks

Many complex systems can be represented as networks, and separating a network into communities could simplify functional analysis considerably. Many approaches have recently been proposed to detect communities, but a method to determine whether the detected communities are significant is still lacking. In this paper, an index to evaluate the significance of communities in networks is proposed based on perturbation of the network. In contrast to previous approaches, the network is disturbed gradually, and the index is defined by integrating all of the similarities between the community structures before and after perturbation. Moreover, by taking the null model into account, the index eliminates scale effects. Thus, it can evaluate and compare the significance of communities in different networks. The method has been tested in many artificial and real-world networks. The results show that the index is in fact independent of the size of the network and the number of communities. With this approach, clear communities are found to always exist in social networks, but significant communities cannot be found in protein interactions and metabolic networks.

Figure 1

(Color online) The expected values of the mutual information $I\left(A_x,A_y\right)$ of two partitions $A_x$ and $A_y$. Each partition divides the $n$ nodes into two groups. $x$ and $y$ represent the fractions of nodes in the first group for the partitions $A_x$ and $A_y$, respectively. The nodes in each group are randomly selected from the entire set of nodes. From the bottom to the top, $n$ is 1000, 200, and 100, respectively.

Figure 2

(Color online) The dependence of $R$ on the network size, average degree and number of communities. In the plot, $n$ denotes the number of nodes and $c$ the number of predetermined communities of the same size. Every predetermined community (subnetwork) is an ER random network and is detached from the others. According to the plot, the value of $R$ increases as the average degrees of the subgraphs increase, and $R$ is almost independent of the network size and the number of communities.

Figure 3

(Color online) Comparison of the modularity $Q$ with the index $R$ on BA and ER networks with no distinct community structures. According to the plot, $Q$ is very large when the average degree is about 1, while $R$ is near 0.2. Thus, when the average degree is near 1, the $Q$ index indicates a very strong community structure, while $R$ shows fuzzy community structures [fuzzy community structure exists when $R=0.2$ according to the numerical results in artificial networks (see Fig. 5)]. However, $Q$ falls more slowly than $R$ as the average degree increases. When the average degree is larger than or equal to 2, $R$ is very low and reaches a stable state, which shows that the $R$ index performs well in both BA and ER networks.

Figure 4

(Color online) Numerical results of testing (a) $\widehat{S}$ [23], (b) $Q$, (c) $Z$ score, and (d) $Q/Q_{rand}$ with the benchmark employed in Fig. 2. The $\widehat{S}$, $Z$ score, and $Q/Q_{rand}$ are all sensitive to the size of the network and the number of communities. $Q$ is sensitive to the network size. Moreover, $\widehat{S}$ falls to 0 very rapidly, which implies that it cannot measure the significance when the community structure is clear.

Figure 5

(Color online) The performance of index $R$ in both the GN-benchmark and LFR-benchmark tests. In the GN-benchmark test, $k_{out}$ is the average number of connections between communities and $\mu =\frac{k_{out}}{16}$. In the LFR-benchmark test, $\mu$ is the mixing parameter, meaning that each node shares a fraction $1-\mu$ of its links with the nodes of its community and a fraction $\mu$ with the nodes outside of its community. Each $R$ corresponding to a given $\mu$ is the average value of more than 20 numerical experiments, and a new independent network is generated each time.

Figure 6

(Color online) The $x$ axis represents the perturbation probability, while the $y$ axis is the corresponding similarity value $S\left(p\right)$. In each network, we highlight the maximum, minimum, and mean values of 20 realizations. The networks are social network (Jazz), neural network (C. elegans), metabolic network (Helicobacter pylori), protein interaction network (E. coli), BA scale-free network and ER random network up-down.