Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models

We present an efficient algorithm for the inference of stochastic block models in large networks. The algorithm can be used as an optimized Markov chain Monte Carlo (MCMC) method, with a fast mixing time and a much reduced susceptibility to getting trapped in metastable states, or as a greedy agglomerative heuristic, with an almost linear $O\left(N{ln}^{2}N\right)$ complexity, where $N$ is the number of nodes in the network, independent of the number of blocks being inferred. We show that the heuristic is capable of delivering results which are indistinguishable from the more exact and numerically expensive MCMC method in many artificial and empirical networks, despite being much faster. The method is entirely unbiased towards any specific mixing pattern, and in particular it does not favor assortative community structures.

Figure 1

Left: Local neighborhood of node $i$ belonging to block $r$, and a randomly chosen neighbor $j$ belonging to block $t$. Right: Block multigraph, indicating the number of edges between blocks, represented as the edge thickness. In this example, the attempted move $b_i\to s$ is made with a larger probability than either $b_i\to u$ or $b_i\to r$ (no movement), since $e_{ts}>e_{tu}$ and $e_{ts}>e_{tr}$.

Figure 2

Left: Autocorrelation function $R\left(\tau \right)$, for a PP model with $c=0.8$ and $B=100$, for a network of size $N={10}^4$ and $\langle k\rangle =10$, and two values of the parameter $\epsilon$, where for $\epsilon \to \infty$ we have fully random moves. The curves were averaged for 100 independent network realizations. Right: PDF of the values of ${\mathcal{S}}_t/E$ obtained for $T=2\times {10}^4$ consecutive sweeps for 100 independent network realizations, for different $\epsilon$ values, showing the same distribution.

Figure 3

Left: Correlation time ${\tau }^{*}$ as a function of the model parameter $c$, for different values of $\epsilon$, $N={10}^4$, $\langle k\rangle =10$, $B=100$, averaged over 40 independent network realizations. Right: Correlation time ${\tau }^{*}$ as a function of the number of blocks $B$, for different values of $\epsilon$, for $N=100\times B$, $\langle k\rangle =10$, $c=0.8$, averaged over 40 independent network realizations.

Figure 4

Evolution of the MCMC for a network sampled from the PP model with $N={10}^4$, $\langle k\rangle =10$, $B=3$, and $c=0.99$, starting from a fully random partition of the nodes. The networks show a representative snapshot of the state of the system before and after the last drop in ${\mathcal{S}}_t$.

Figure 5

Representation of the block merges used in the agglomerative heuristic. Each square node is a block in the original graph, and the merges (represented as red dashed lines) correspond simply to block membership moves.

Figure 6

Left: An example of a typical partition obtained by starting with a random $B=3$ configuration and applying only greedy moves until no further improvement is possible for a PP network with $N=300$, $\langle k\rangle =10$, and $c=0.9$. Right: A typical outcome for the same network, with the greedy agglomerative algorithm described in the text.

Figure 7

Normalized mutual information (NMI) (see footnote 6, page 6) between the planted and the inferred partitions for (top) the PP model and (bottom) the circular multipartite model described in the text, as a function of the modular strength $c$, for $N={10}^4$ and $B=10$. The “Escape” curves correspond to MCMC equilibrations starting from the planted partition, and the remaining curves to the greedy agglomerative heuristic with ratio $\sigma$ shown in the legend, and $n_m=10$. All curves are averaged over 20 independent network realizations. The grey vertical dashed line corresponds to the detectability threshold $c^{*}$ for the PP model, and the red dashed line to the MDL model selection threshold of Eq. (7).

Figure 8

Description length $\Sigma$ for different empirical networks collected for 100 independent runs of the MCMC algorithm (MC) and the agglomerative heuristic (Agg) for different agglomeration ratios $\sigma$.

Figure 9

Normalized mutual information (NMI) between the best overall partition and each one collected for 100 independent runs of the MCMC algorithm (MC) and the agglomerative heuristic (Agg) for different agglomeration ratios $\sigma$.

Figure 10

Description length $\Sigma$ for different empirical networks, as well the normalized mutual information (NMI) between the best overall partition and each one, collected for 100 independent runs of the agglomerative heuristic, for different agglomeration ratios $\sigma$.