Community Detection in Bipartite Networks with Stochastic Blockmodels

Abstract

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.

arXiv comment17 pages, 6 figures. Code is available at https://github.com/junipertcy/bipartiteSBM and a documentation at https://docs.netscied.tw/bipartiteSBM/index.html

References in corpus (34)

• Stochastic blockmodels and community structure in networks
• Mixed membership stochastic blockmodels
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• The ground truth about metadata and community detection in networks
• Structure and inference in annotated networks
• Random hypergraphs and their applications
• A network approach to topic models
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Network structure from rich but noisy data
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Efficiently inferring community structure in bipartite networks
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Network histograms and universality of blockmodel approximation
• Entropy of stochastic blockmodel ensembles
• A network approach to analyzing highly recombinant malaria parasite genes
• Model Selection for Degree-corrected Block Models
• Marvel Universe looks almost like a real social network
• Estimating network structure from unreliable measurements
• Efficient method for estimating the number of communities in a network
• Reconstructing networks with unknown and heterogeneous errors
• Consistencies and inconsistencies between model selection and link prediction in networks
• Minimum Description Length Revisited
• Justice blocks and predictability of US Supreme Court votes
• Exploring the solution landscape enables more reliable network community detection
• Accurate and scalable social recommendation using mixed-membership stochastic block models
• Typology of phase transitions in Bayesian inference problems
• Network structure, metadata and the prediction of missing nodes and annotations
• Enhanced capital-asset pricing model for the reconstruction of bipartite financial networks
• Universality of the stochastic block model
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Detectability thresholds of general modular graphs

Cited by in corpus (9)

• Statistical inference of assortative community structures
• The simpliciality of higher-order networks
• Randomizing hypergraphs preserving degree correlation and local clustering
• Multilayer Networks for Text Analysis with Multiple Data Types
• Robustness modularity in complex networks
• Mapping Flows on Bipartite Networks
• Community detection in bipartite signed networks is highly dependent on parameter choice
• Node metadata can produce predictability transitions in network inference problems
• Co-factor analysis of citation networks