Efficiently inferring community structure in bipartite networks

Abstract

Bipartite networks are a common type of network data in which there are two types of vertices, and only vertices of different types can be connected. While bipartite networks exhibit community structure like their unipartite counterparts, existing approaches to bipartite community detection have drawbacks, including implicit parameter choices, loss of information through one-mode projections, and lack of interpretability. Here we solve the community detection problem for bipartite networks by formulating a bipartite stochastic block model, which explicitly includes vertex type information and may be trivially extended to $k$-partite networks. This bipartite stochastic block model yields a projection-free and statistically principled method for community detection that makes clear assumptions and parameter choices and yields interpretable results. We demonstrate this model's ability to efficiently and accurately find community structure in synthetic bipartite networks with known structure and in real-world bipartite networks with unknown structure, and we characterize its performance in practical contexts.

12 pages, 9 figures

References in corpus (10)

• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• An information-theoretic framework for resolving community structure in complex networks
• Modularity and community detection in bipartite networks
• Phase transition in the detection of modules in sparse networks
• Parsimonious module inference in large networks
• Predicting human preferences using the block structure of complex social networks
• Predicting future conflict between team-members with parameter-free models of social networks
• Effect of size heterogeneity on community identification in complex networks

Cited by in corpus (41)

• Community detection in networks: A user guide
• Networks beyond pairwise interactions: structure and dynamics
• The ground truth about metadata and community detection in networks
• Structure and inference in annotated networks
• Common neighbours and the local-community-paradigm for link prediction in bipartite networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• A Clarified Typology of Core-Periphery Structure in Networks
• Community Detection in Large Hypergraphs
• Local dominance unveils clusters in networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Bank-firm credit network in Japan. An analysis of a bipartite network
• Disentangling bipartite and core-periphery structure in financial networks
• Efficient community detection of network flows for varying Markov times and bipartite networks
• Generalized Two-mode Cores
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Transitivity and degree assortativity explained: The bipartite structure of social networks
• Latent geometry of bipartite networks
• Degree distributions of bipartite networks and their projections
• Universality of the stochastic block model
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Randomizing hypergraphs preserving degree correlation and local clustering
• Core of communities in bipartite networks
• Algorithmic detectability threshold of the stochastic block model
• A unified data representation theory for network visualization, ordering and coarse-graining
• Ground truth? Concept-based communities versus the external classification of physics manuscripts
• Cluster analysis of weighted bipartite networks: a new copula-based approach
• Entropy-based randomisation of rating networks
• Mapping Flows on Bipartite Networks
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• A simple bipartite graph projection model for clustering in networks
• Choice Set Confounding in Discrete Choice
• The Infinity Mirror Test for Graph Models
• The Atlas for the Aspiring Network Scientist
• Impact of the mesoscale structure of a bipartite ecological interaction network on its robustness through a probabilistic modeling
• Fast Network Community Detection with Profile-Pseudo Likelihood Methods
• Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences
• Extracting hierarchical backbones from bipartite networks
• Graph-based open-ended survey on concerns related to COVID-19
• Co-factor analysis of citation networks