Community detection in bipartite networks with stochastic block models

In bipartite networks, community structures are restricted to being disassortative, in that nodes of one type are grouped according to common patterns of connection with nodes of the other type. This makes the stochastic block model (SBM), a highly flexible generative model for networks with block structure, an intuitive choice for bipartite community detection. However, typical formulations of the SBM do not make use of the special structure of bipartite networks. Here we introduce a Bayesian nonparametric formulation of the SBM and a corresponding algorithm to efficiently find communities in bipartite networks which parsimoniously chooses the number of communities. The biSBM improves community detection results over general SBMs when data are noisy, improves the model resolution limit by a factor of $\sqrt{2}$, and expands our understanding of the complicated optimization landscape associated with community detection tasks. A direct comparison of certain terms of the prior distributions in the biSBM and a related high-resolution hierarchical SBM also reveals a counterintuitive regime of community detection problems, populated by smaller and sparser networks, where nonhierarchical models outperform their more flexible counterpart.

Figure 1

Diagram showing the biSBM community detection algorithm on the description length landscape of the malaria gene-substring network [45]. (a) Each square in the heat map shows the result of fitting a model using MCMC at the specified $\left(B_{\mathrm{I}},B_{\mathrm{II}}\right)$. The color bar scales linearly. An arrow indicates the minimizing point. (b) Trajectory of the efficient search routine over the landscape shown in the top panel. Circles indicate where MCMC inference was required. Pink shaded regions show neighborhoods of exhaustive local search, with sequential order indicated by $①$ to $⑤$. (c) Change of description length values as the algorithm progresses. Shaded circles show the steps at which the 36 MCMC calculations were performed. The minimizing point at (11,14) was found during local search $④$ and confirmed during local search $⑤$.

Figure 2

Numerical tests of the recovery of planted structure in synthetic networks with $N={10}^4$ nodes. Each point shows the median of ${10}^2$ replicates of the indicated model and algorithm (see legend) and error bars show $25\%-75\%$ quantiles. Insets show the structure of the problems at moderate $\epsilon$. (a) A test meant to be easy: mean degree 5, equally sized groups, and $B_{\mathrm{I}}=B_{\mathrm{II}}=10$. (b) A test meant to be challenging: mean degree 15, equally sized groups, and $B_{\mathrm{I}}=4$ and $B_{\mathrm{II}}=15$.

Figure 3

A numerical experiment on bipartite cliques to demonstrate the resolution limit. As an increasing number of bipartite cliques with 10 nodes of each type are presented to the SBM, biSBM, and hSBM (see legend), the hSBM continues to find all cliques while the SBM and biSBM begin to merge pairs, quartets, and eventually octets of cliques. Arrows indicate analytical predictions of merge transitions from posterior odds ratios, with colors matching the legend. Note that biSBM transitions occur at twice the value of $B$ as SBM transitions, showing the biSBM's expanded resolution limit.

Figure 4

Comparison of the description lengths resulting from prior distribution over edge counts using the biSBM, SBM, and hSBM priors. Regions where a flat prior has a lower description length than the hierarchical prior are shaded for (a) the SBM and (b) the biSBM. Flat priors are favored when there are fewer edges, more groups, and a smaller hierarchical branching factor $\sigma$ (defined in Sec. 6). The flat-model regime is larger for the biSBM than the SBM, as described in Sec. 6.

Figure 5

Repeated application of models (see legend in panel a) with default algorithms produces distributions of the description length and the number of groups, for eight of the empirical networks listed in Table 1. Vertical lines mark the value of the mean description length.

Figure 6

Scatter plots and histograms of description length for the ancient metabolic (a) [71] and malaria gene similarity (b) [45] networks from 100 independent experiments. Gray vertical lines connect biSBM results with their matching h-biSBM hierarchical results. Arrows in histograms mark the MDL points from the hSBM (gray) and by the h-biSBM (blue).