Nonparametric Bayesian inference of the microcanonical stochastic block model

A principled approach to characterize the hidden structure of networks is to formulate generative models and then infer their parameters from data. When the desired structure is composed of modules or “communities,” a suitable choice for this task is the stochastic block model (SBM), where nodes are divided into groups, and the placement of edges is conditioned on the group memberships. Here, we present a nonparametric Bayesian method to infer the modular structure of empirical networks, including the number of modules and their hierarchical organization. We focus on a microcanonical variant of the SBM, where the structure is imposed via hard constraints, i.e., the generated networks are not allowed to violate the patterns imposed by the model. We show how this simple model variation allows simultaneously for two important improvements over more traditional inference approaches: (1) deeper Bayesian hierarchies, with noninformative priors replaced by sequences of priors and hyperpriors, which not only remove limitations that seriously degrade the inference on large networks but also reveal structures at multiple scales; (2) a very efficient inference algorithm that scales well not only for networks with a large number of nodes and edges but also with an unlimited number of modules. We show also how this approach can be used to sample modular hierarchies from the posterior distribution, as well as to perform model selection. We discuss and analyze the differences between sampling from the posterior and simply finding the single parameter estimate that maximizes it. Furthermore, we expose a direct equivalence between our microcanonical approach and alternative derivations based on the canonical SBM.

Figure 1

Illustration of the complete nonparametric generative process for the DC-SBM considered in this work. First the partition of the nodes is sampled (a), followed by the edge counts between groups (b), the degrees of the nodes (c), and finally the network itself (d).

Figure 2

Comparisons between the exact and approximated values of the number of restricted partitions $q(m,n)$, using Eqs. (30) and (31, 32, 33, 34, 35). The top panel shows both values computed for different values of $m$ and $n$, and the bottom panel shows the absolute difference of their logarithms, with the inset displaying a zoom into the large $m$ region.

Figure 3

Expected degree distributions for the three different priors considered in the text for the degree sequence inside each group—the NDC-SBM, the uniform prior of Eq. (26) and the prior of Eq. (29) conditioned on a degree distribution sampled randomly—for $N={10}^4$ nodes and average degree $〈k〉=10$. In all cases, the distributions were sampled from their respective microcanonical distributions using rejection sampling. The dashed line shows the Bose-Einstein distribution of Eq. (A13).

Figure 4

Planted partition of $B=6$ equal-sized groups (node colors), being wrongly fitted as a $B^{*}=3$ model (shaded region). In the fitted model, the two groups inside each shaded region are not properly identified. This problem happens whenever $B>B_{\text{max}}$ for $B_{\text{max}}=O\left(\sqrt{N}\right)$ using noninformative priors for the edge counts, but only for $B_{\text{max}}=O(N/lnN)$ when the hierarchical priors are used instead.

Figure 5

Most likely hierarchical partitions of a network of political blogs [52], according to the three model variants considered, as well as the number of groups $B_1$ at the bottom of the hierarchy, and the description length $\mathrm{\Sigma }$: (a) NDC-SBM, $B_1=42$, $\mathrm{\Sigma }\approx 89938$ bits; (b) DC-SBM, uniform prior, $B_1=23$, $\mathrm{\Sigma }\approx 87162$ bits; (c) DC-SBM, uniform hyperprior, $B_1=20$, $\mathrm{\Sigma }\approx 84890$ bits. The nodes circled in blue were classified as “liberals” and the remaining ones as “conservatives” in Ref. [52] based on the blog contents. Note that in all cases this division in two groups is correctly identified at the topmost level of the hierarchy. However, the lower levels yield significantly different subdivisions depending on which model type is used. The layout is obtained with an algorithm by Holten [53].

Figure 6

Hierarchical partitions of a network of collaboration between scientists [54]. (a) Most likely hierarchical partition according to the DC-SBM with a uniform hyperprior. (b) Uncorrelated samples from the posterior distribution. (c) Marginal posterior distribution of the number of groups at the first three hierarchical levels, according to the model variants described in the legend. The vertical lines mark the value obtained for the most likely partition.

Figure 7

Marginal posterior distribution of the number of groups at the first three hierarchical levels, according to the model variants described in the legend, for some of the empirical networks listed in Table 1: (a) dolphin social network; (b) characters in Les Misérables; (c) American college football; (d) Southern women interactions; (e) malaria gene similarity; (f) protein interactions (II); (g) global airport network; (h) dictionary entries. The vertical lines mark the value obtained for the most likely partition (the MDL criterion).

Figure 8

Posterior odds ratio relative to the best model, according to (a) the MDL criterion, ${\mathrm{\Lambda }}_1$ [Eq. (81)] and (b) full posterior probability, ${\mathrm{\Lambda }}_2$ [Eq. (83)] for the empirical networks listed in Table 1. The ratio is computed so that the preferred model has ${\mathrm{\Lambda }}_{1/2}=1$ and thus appears on the top of the figures. The remaining points for each dataset correspond to the odds ratio of the remaining models relative to the winning one. The solid lines mark a $\mathrm{\Lambda }={10}^{-2}$ confidence threshold. The networks are ordered by increasing number of nodes (see Table 1).

Figure 9

Degree histograms for the Email (left) and arXiv hep-th citations (right) networks. In both cases the solid lines show a geometric distribution $N_k=Np{(1-p)}^{k-1}$, with $p=1/〈k〉$.