Limits of modularity maximization in community detection

Modularity maximization is the most popular technique for the detection of community structure in graphs. The resolution limit of the method is supposedly solvable with the introduction of modified versions of the measure, with tunable resolution parameters. We show that multiresolution modularity suffers from two opposite coexisting problems: the tendency to merge small subgraphs, which dominates when the resolution is low; the tendency to split large subgraphs, which dominates when the resolution is high. In benchmark networks with heterogeneous distributions of cluster sizes, the simultaneous elimination of both biases is not possible and multiresolution modularity is not capable to recover the planted community structure, not even when it is pronounced and easily detectable by other methods, for any value of the resolution parameter. This holds for other multiresolution techniques and it is likely to be a general problem of methods based on global optimization.

Figure 1

Schematic representation of the problem of merging versus splitting subgraphs. Here $A$ and $B$ are two subgraphs, the problem is whether one yields a higher value for modularity by merging them in a single subgraph or by keeping them separated. The parameters involved in the decision are the number of internal links in $A$ and $B$ (multiplied by 2), $k_{\mathrm{in}}^A$ and $k_{\mathrm{in}}^B$, the number of links $v$ between $A$ and $B$ (here $v=3$), the number of links $l$ between $A$ and vertices belonging neither to $A$ nor to $B$ (here $l=4$), and its equivalent $r$ for $B$ (here $r=2$).

Figure 2

The plot shows ${\alpha }_{\mathcal{S}}$ measured on Erdös-Rényi and scale-free graphs. For each type of graph, we plot the analytical estimate of Reichardt and Bornholdt (RB) and a numerical estimate obtained by optimizing modularity with simulated annealing (SA) [13]. The minimum cut $v={\alpha }_{\mathcal{S}}\times M_{\mathcal{S}}$ was measured by optimizing modularity for different values of $\lambda$ over the set of bipartitions. To optimize modularity, we are looking for small values of $v$ and equal values of $k^A$ and $k^B$, so tuning $\lambda$ just controls the importance of either requirement. However, simulations show that the dependence on $\lambda$ is quite weak, validating our approximation $k^A\approx k^B$.

Figure 3

Schematic network with two cliques and a random subgraph, which are the natural communities of the network.

Figure 4

This plot shows Eq. (21) as a function of $n_{\mathcal{S}}$ and $n_{\mathcal{C}}$ for the simple network with the three clusters described in the legend of Fig. 3. Above the curves, modularity cannot find the right partition for any value of $\lambda$.

Figure 5

Threshold parameters ${\lambda }_1$ and ${\lambda }_2$ as a function of $n_{\mathcal{S}}$ ($n_{\mathcal{C}}=13$, ${\langle k\rangle }_{\mathcal{S}}=100$). The theoretical line for ${\lambda }_1$ is obtained by approximating ${\alpha }_{\mathcal{S}}$ as described in the text. We see that ${\lambda }_1>{\lambda }_2$, up to $n_{\mathcal{S}}\approx 230$, so that no $\lambda$ can eliminate the biases for bigger values of $n_{\mathcal{S}}$. When $n_{\mathcal{S}}<\approx 230$, the biases can be both eliminated only in the shadowed area between the curves.

Figure 6

Test of multiresolution modularity on LFR benchmark graphs. Each panel shows the fraction of misclassified vertices due to artificial mergers (circles) and splits (squares) of clusters, as a function of the resolution parameter $\lambda$. The panels correspond to different choices of the exponent ${\tau }_2$ of the cluster size distribution of the graph and of the mixing parameter $\mu$. Each point represents an average over 100 benchmark graphs. All graphs have $10000$ vertices. The other parameters are: average degree $\langle k\rangle =20$; maximum degree $k_{\max }=100$; minimum cluster size $c_{\min }=10$; maximum cluster size $c_{\max }=1000$; degree exponent ${\tau }_1=2$.

Figure 7

Same as Fig. 6, but for LFR benchmark graphs of $50000$ vertices. All other parameters are the same as for the graphs used in Fig. 6.

Figure 8

Comparative analysis of several multiresolution techniques on the LFR benchmark. The graphs are made of 1000 and 5000 vertices, the exponent of the degree distribution ${\tau }_1=2$, the exponent of the clusters size distribution ${\tau }_2=1$, the average degree $\langle k\rangle =20$, the maximum degree $k_{\max }=50$, the cluster size ranges are $S=[10,50]$ and $B=[20,100]$.

Figure 9

Comparative analysis of several multiresolution techniques on the LFR benchmark. The network parameters are now the same as for the graphs used in Fig. 6. In particular, the network size is $10000$ and the cluster size spans two orders of magnitude. The two panels correspond to ${\tau }_2=2$ (left) and ${\tau }_2=3$ (right).