Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection

Modularity maximization using greedy algorithms continues to be a popular approach toward community detection in graphs, even after various better forming algorithms have been proposed. Apart from its clear mechanism and ease of implementation, this approach is persistently popular because, presumably, its risk of algorithmic failure is not well understood. This Rapid Communication provides insight into this issue by estimating the algorithmic performance limit of the stochastic block model inference using modularity maximization. This is achieved by counting the number of metastable states under a local update rule. Our results offer a quantitative insight into the level of sparsity at which a greedy algorithm typically fails.

Figure 1

Modularity landscapes and network figures for instances of the small stochastic block model with equal group sizes ($N=20$). The average degrees and strengths of the modular structures are $(c=9.6,\epsilon =0.04)$ (top) and $(c=9.2,\epsilon =0.4)$ (bottom), respectively. The landscapes were drawn using the code of the curvilinear component analysis distributed by Ref. [31] (see Ref. [32] for a detailed description of the visualization).

Figure 2

(a) Detectability phase diagram of a simple greedy algorithm for the symmetric stochastic block model with $N=10000$. The density plot represents the overlaps, while the solid yellow line represents our detectability limit estimate. The shaded region at the upper-left corner represents the region where the detection is information-theoretically impossible. (b) Overlaps of $c=10$ (top), $c=20$ (middle), and $c=30$ (bottom) as functions of $\epsilon$ for different graph sizes $N$. The shaded region with the dashed border line represents our undetectable region estimate. In all plots, the average overlap value of 100 graph instances was determined for each pair of $c$ and $\epsilon$ values.

Figure 3

Detectability phase diagrams of Louvain algorithm for a symmetric stochastic block model with (a) $N=500$, (b) $N=1000$, (c) $N=2000$, and (d) $N=4000$, respectively. Plotting was carried out in the same manner as that shown in Fig. 2. The overlap is set to 0.5 whenever the graph is partitioned into more than two groups. In all plots, the average overlap value of ten graph instances was determined for each $c$ and $\epsilon$ pair.