Robustness modularity in complex networks

A basic question in network community detection is how modular a given network is. This is usually addressed by evaluating the quality of partitions detected in the network. The Girvan-Newman (GN) modularity function is the standard way to make this assessment, but it has a number of drawbacks. Most importantly, it is not clearly interpretable, given that the measure can take relatively large values on partitions of random networks without communities. Here we propose a measure based on the concept of robustness: modularity is the probability to find trivial partitions when the structure of the network is randomly perturbed. This concept can be implemented for any clustering algorithm capable of telling when a group structure is absent. Tests on artificial and real graphs reveal that robustness modularity can be used to assess and compare the strength of the community structure of different networks. We also introduce two other quality functions: modularity difference, a suitably normalized version of the GN modularity, and information modularity, a measure of distance based on information compression. Both measures are strongly correlated with robustness modularity, but have lower time complexity, so they could be used on networks whose size makes the calculation of robustness modularity too costly.

Figure 1

Schematic representation of the proposed methodology. The network is the one at the top. First, links in the network are randomly rewired with a probability $p$. Then a clustering algorithm is applied on all perturbed networks, producing an $R$ profile (bottom). The RM is the area above the curve of the $R$ profile (highlighted).

Figure 2

Trivial partition ratio ($R$) for SBM benchmark graphs.

Figure 3

$R$ curves obtained for the hybrid model consisting of an ER graph and a clique including a fraction $F$ of the nodes.

Figure 4

Typical $R$ curves obtained for real networks. Number of nodes ($N$), average node degree $\langle k\rangle$ and the RM $Q_r$ are shown for each pattern. The last panel (p) shows all the $R$ curves obtained from the Facebook social networks in the dataset, which are fairly similar to each other.

Figure 5

Relationship of the ranks of our artificial and real network datasets, obtained by using the RM $Q_r$ and the GN modularity $Q$. The Spearman correlation coefficient is $-0.12$. The Pearson correlation coefficient between the scores is $-0.03$. Inset: scatter plot between the actual values of $Q_r$ and $Q$.

Figure 6

Relationship between $Q_r$ and $Q_{\mathrm{diff}}$. As in Fig. 5 points are identified by the ranks of the corresponding datasets according to the two scores. The networks shown in Fig. 4, and a few others are highlighted and their respective structures are displayed. The colors of the nodes in each network identify the communities obtained from the microcanonical SBM inference. The shaded red region highlights the social networks from the set socfb. We connect the dots representing LFR and (standard) SBM model graphs to show that both modularity scores decrease (ranks increase) when the mixing parameter $\mu$ increases. Inset: scatter plot between the actual values of $Q_r$ and $Q_{\mathrm{diff}}$. Spearman ($S_{\mathrm{corr}}$) and Pearson ($P_{\mathrm{corr}}$) correlation coefficients equal 0.63 and 0.62, respectively.

Figure 7

Relationship between $Q_r$ and $Q_{\mathrm{DL}}$. The diagram is analogous to the one in Fig. 6. The Spearman ($S_{\mathrm{corr}}$) and Pearson ($P_{\mathrm{corr}}$) correlation coefficients are 0.69 and 0.75, respectively.

Figure 8

Relationship between $Q_{\mathrm{diff}}$ and $Q_{\mathrm{DL}}$. The diagram is analogous to the ones in Figs. 6 and 7. The Spearman ($S_{\mathrm{corr}}$) and Pearson ($P_{\mathrm{corr}}$) correlation coefficients are 0.88 and 0.86, respectively.

Figure 9

Trivial partition ratio ($R$) as a function of $p$ for LFR benchmark graphs for different values of the mixing parameter $\mu$.

Figure 10

$R$ curves for various random network models.

Figure 11

Starlike networks and respective $R$ curves obtained by using random and degree-preserving rewiring. Colors indicate the communities detected using the SBM method.

Figure 12

Description lengths for three divisions obtained on unperturbed SBM benchmark networks ($p=0$), as a function of the mixing parameter $\mu$: the partition detected by the SBM clustering method, the planted partition, and the trivial partition.

Figure 13

Description lengths for three divisions obtained on unperturbed LFR benchmark networks ($p=0$), as a function of the mixing parameter $\mu$: the partition detected by the SBM clustering method, the planted partition, and the trivial partition.

Figure 14

$R$ curves for biological networks.

Figure 15

$R$ curves for the transportation and geographic networks.

Figure 16

$R$ curves for social networks.

Figure 17

$R$ curves for information and economic networks.