PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficiently inferring community structure in bipartite networks

Daniel B. Larremore, Aaron Clauset, Abigail Z. Jacobs

arXiv:1403.2933v2cs.SIphysics.data-anphysics.soc-phq-bio.QMstat.ML

TL;DR

Bipartite community detection is challenged by projection-based information loss, implicit assumptions, and methods that do not explicitly encode vertex types. The paper formulates a bipartite stochastic block model and likelihood-search algorithm, evaluates it on synthetic and empirical networks, and reports more efficient and accurate inference than unrestricted and projection-based alternatives in tested cases.

  • Problem

    Existing bipartite community-detection approaches can make implicit choices and discard information through one-mode projections, limiting interpretability.

  • Method

    The paper formulates a bipartite stochastic block model that explicitly encodes vertex types and uses a type-constrained likelihood-search algorithm for community inference.

  • Results

    The biSBM finds higher-likelihood solutions more efficiently than the SBM and outperforms one-mode projections in all tested cases.

  • Takeaways & Limitations

    Bipartite structure can be used directly for projection-free community inference with explicit assumptions and interpretable results.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Bipartite community detection must account for two vertex types and their cross-type-only edges, rather than applying assumptions designed for assortative unipartite networks. The paper introduces a projection-free biSBM that explicitly models types, preserves information, and supports interpretable inference.

  • I. INTRODUCTION: Bipartite networks contain two vertex types, with edges allowed only between different types.Examples include plant–pollinator and document–word networks.
  • I. INTRODUCTION: Assortativity-based community definitions are ill-suited because same-type vertices cannot be connected in bipartite networks.The paper instead seeks groups whose vertices connect to the rest of the network in similar ways.
  • I. INTRODUCTION: One-mode projections discard information and can make structurally different or highly structured bipartite networks appear identical or unstructured.Projection networks also consist of overlapping cliques that can conflict with common null-model assumptions.
  • I. INTRODUCTION: The biSBM directly applies an SBM to bipartite data while explicitly enforcing vertex-type structure.Its notation uses type-specific groups and zeroes same-type connectivity parameters, extending naturally to k-partite networks.
  • I. INTRODUCTION: The paper evaluates whether the biSBM recovers planted partitions in noisy synthetic networks and outperforms a non-bipartite SBM on empirical networks.The synthetic evaluation includes cases where one-mode projections are uninformative.

A. biSBM without degree correction

The uncorrected biSBM defines bipartite network structure through group-level expected edge rates and performs likelihood-based inference over pure-type vertex partitions. Its constraints treat the absence of same-type edges as known bipartite structure.

  • A. biSBM without degree correction: The uncorrected biSBM models expected adjacency entries with a group-interrelationship matrix ω and Poisson-distributed edge counts.The Poisson formulation permits multi-edges for computational convenience, which are unlikely in sparse networks.
  • A. biSBM without degree correction: The model restricts generation and inference to bipartite networks by excluding same-type connectivity.Unlike the unrestricted SBM, it does not infer bipartiteness from the absence of same-type edges.
  • A. biSBM without degree correction: Given group assignments, types, and ω, the model writes the network likelihood and maximizes its logarithm without changing the maximizing parameters.The optimization then proceeds over group assignments subject to pure-type community constraints.

B. Degree-corrected biSBM

The degree-corrected biSBM incorporates heterogeneous observed degree sequences before inferring community structure. This correction preserves expected group edge counts and degrees while retaining pure-type groups.

  • B. Degree-corrected biSBM: The degree-corrected biSBM models heterogeneous vertex degrees explicitly before finding community structure.Without correction, Poisson degree distributions can sort vertices primarily by degree rather than community.
  • B. Degree-corrected biSBM: Vertex-pair edge counts follow Poisson means θ_iθ_jω_gi_gj under the bipartite constraints.The parameters θ_i control expected vertex degrees, while ω controls edge counts between groups.
  • B. Degree-corrected biSBM: The normalization makes θ_i the probability that an edge reaching its community lands on vertex i.This removes the multiplicative scale ambiguity between θ and ω.
  • B. Degree-corrected biSBM: Maximum-likelihood estimates preserve both expected numbers of edges between groups and the expected degree sequence.The resulting likelihood is maximized over partitions g.
  • B. Degree-corrected biSBM: Both corrected and uncorrected formulations find K pure-type groups, with K_a groups among type a vertices and K_b among type b vertices.Their apparently simple likelihood substitution can nevertheless drastically change optimal partitions when degrees are heterogeneous.

C. A biSBM algorithm

The biSBM algorithm initializes type-specific groups and searches the likelihood surface through type-compatible vertex moves. Repeated stochastic runs help select a high-scoring solution for either corrected or uncorrected models.

  • C. A biSBM algorithm: The algorithm initializes type a and type b vertices uniformly at random into their respective K_a and K_b groups.Group types are fixed to match the corresponding vertex types.
  • C. A biSBM algorithm: It proposes moving vertices only between groups with matching types and selects moves that increase likelihood most.When no improvement exists, it may choose the least-decreasing move to escape local optima.
  • C. A biSBM algorithm: The algorithm should be run repeatedly, retaining the highest score across independent replicates.The same procedure applies to degree-corrected and uncorrected models.

III. COMPARISON OF THE BISBM AND SBM

The biSBM and SBM can represent the same bipartite networks under type-purity and no same-type-edge constraints, but their unconstrained optimization behavior differs. The SBM may favor mixed-type communities, whereas the biSBM enforces bipartite structure directly.

  • Model relationship: The biSBM and SBM likelihoods are numerically equivalent when communities remain pure-type and same-type edges are absent.These constraints are applied explicitly in the biSBM but only a posteriori in the SBM.
  • Model relationship: The SBM can prefer mixed-type communities because it optimizes over both assortative and disassortative structures, while the biSBM permits only disassortative groups.The biSBM treats the absence of same-type edges as given rather than as evidence to explain.
  • Model relationship: The SBM's higher likelihood does not guarantee a more appropriate bipartite partition, because mixed-type solutions can achieve higher scores than pure-type alternatives.The SBM is a nested model and can always match or exceed the biSBM objective value.
  • Model relationship: When K is odd, the SBM overfits a bipartite ring by finding a higher-likelihood mixed-type partition; when K is even, both models find identical partitions.The result holds for both degree-corrected and uncorrected models.

B. Performance relative to SBM

The biSBM searches separate type-specific spaces, reducing computational complexity and avoiding many mixed-type local optima. In experiments, it converges faster, finds better partitions, and retains solution quality relative to the SBM.

  • Performance relative to SBM: The biSBM divides one search over K communities into separate searches over Ka and Kb communities, making each iteration faster than the SBM.The speed advantage follows from (x + y)^2 ≥ x^2 + y^2 for nonnegative x and y.
  • Performance relative to SBM: 3.25 times faster: the biSBM converged in 1.64 seconds versus 5.33 seconds per replicate for the SBM on the malaria dataset.Across 2000 replicates, the SBM found only eight pure-type partitions, while the biSBM generally found higher-quality partitions.
  • Performance relative to SBM: The biSBM generally reaches higher-quality solutions by eliminating mixed-type partitions and narrowing the rugged SBM likelihood landscape.Random SBM initializations often fall into local optima corresponding to mixed-type partitions with lower log-likelihood.
  • Performance relative to SBM: BiSBM partitions were also local optima for the SBM in all tested cases, indicating no observed partition-quality tradeoff from the smaller search space.The comparison tested whether the SBM's additional flexibility could improve biSBM partitions.

IV. RESULTS

The study evaluates biSBM recovery on synthetic networks with planted structure and applies it to three empirical bipartite networks. Experiments vary noise, degree correction, projections, and partition-evaluation procedures.

  • Empirical networks: The empirical evaluation covers the Southern Women network, a malaria gene–substring network, and a subset of the Internet Movie Database.The biSBM supplies partitions for both women and events in the Southern Women benchmark.
  • Synthetic networks: The experiments test recovery of planted partitions under uniformly random noise, reflecting the missing or spurious edges found in empirical networks.The mixing parameter λ interpolates between all noise and all planted structure.
  • Synthetic networks: Two synthetic cases probe different conditions: an easy network with four clear bipartite components and a difficult network with unequal community counts, heterogeneous degrees, and sizes.The easy case is also informative in its one-mode projection, whereas the difficult case is designed to challenge projection-based methods.
  • Evaluation: Performance is measured by normalized mutual information between inferred and correct partitions, with direct comparison of biSBM partitions and SBM recovery on type-specific projections.The evaluation focuses on recovery of the correct partition of type b vertices while the biSBM partitions both types.
  • Evaluation: Figure 3 compares methods as noise decreases toward λ = 1 using medians from 100 replicates and 10%–90% quantile bands.Panels distinguish easy recovery, difficult recovery, and initialized projection-SBM behavior.

1. An easy case

The easy synthetic case uses four clear, non-overlapping bipartite components with identifiable mixing structure. Under this unambiguous structure, biSBM and projection-based methods recover communities effectively.

  • 1. An easy case: The easy network contains four equally sized, unambiguous, non-overlapping components, each pairing one type a community with one type b community.Its community structure is obvious in both the original bipartite network and its one-mode projection.
  • 1. An easy case: The mixing matrix assigns positive within-component parameters α, β, γ, and δ while separating the four component pairs.The construction uses N = 1000 vertices of each type, divided evenly across the four components, without degree correction.
  • 1. An easy case: When λ = 1, the biSBM always extracts the correct communities, and projection methods also perform well because the structure is unambiguous.Performance declines sharply as the network approaches the detectability limit.

2. A difficult case

The planted network creates overlapping communities and heterogeneous degrees so that its one-mode projection obscures structure. The degree-corrected biSBM recovers the planted partition across noise levels where projection-based approaches fail or become unreliable.

  • 2. A difficult case: The difficult construction uses partially overlapping communities, unequal community sizes, and heterogeneous degree distributions, while its one-mode projection is relatively uninformative.Type a communities number 100, 150, and 50 vertices; type b communities each contain 350 vertices.
  • 2. A difficult case: When correctly sorted, the bipartite adjacency matrix shows community structure that the SBM cannot detect from the b-mode projection.The projection’s equal connections from the third type a community mask structure from the other communities.
  • 2. A difficult case: The degree-corrected biSBM reaches the detectability transition at λ ≈0.33, whereas the uncorrected biSBM finds the planted structure only near λ ≈1.The uncorrected model’s performance is highly variable, with either extremely accurate or extremely inaccurate partitions.
  • 2. A difficult case: Weighted and unweighted projections both fail to find community structure, while degree correction keeps the SBM near the correct partition when λ ≈1 under correct initialization.The uncorrected SBM fails completely in this initialized comparison.
  • 2. A difficult case: Weighted projection outperforms unweighted projection, but projection-based methods remain difficult to optimize and are outperformed by the biSBM.Fast modularity maximization partially extracts structure for λ > 0.5 with high variability.

B. Empirical Networks

Across empirical networks, the bipartite SBM identifies interpretable partitions for women and events, malaria genes and substrings, and actors and movies. Degree correction is especially useful for heterogeneous-degree malaria data, while the Southern Women dataset provides only a minimal benchmark.

  • 1. The Southern Women Dataset: The biSBM and degree-corrected biSBM identify the same Southern Women partition, with women matching the literature consensus while events are partitioned simultaneously.The inferred event partition largely matches a three-group structure, unlike the separately partitioned two-community result cited from prior work.
  • 1. The Southern Women Dataset: The Southern Women dataset is a minimal benchmark because most of 21 reviewed methods produced identical partitions or differed by only one vertex label.The authors therefore evaluate the model on a more challenging empirical network.
  • 2. Malaria Dataset: For malaria data, the degree-corrected biSBM recovers unequal-sized communities in which one gene group nearly exclusively matches one substring group, while two pairs partially overlap.The model accommodates varying community sizes and degrees; a previous analysis found a similar gene partition but no substring partition.
  • 2. Malaria Dataset: The uncorrected biSBM groups connected malaria vertices by degree and produces a partition that does not correspond well to biological gene classifications.The degree-corrected model succeeds on broad or heterogeneous degree distributions where the uncorrected model does not.
  • 3. IMDb Dataset: In the IMDb network, inferred movie groups separate primarily by language, except for a multilingual Adult-film group defined by genre.This correspondence between blocks, genre, and language provides insight into multiple mechanisms associated with edges.

V. CONCLUSIONS

The biSBM avoids information loss and null-model mismatch from one-mode projections while using known bipartite structure for more efficient and accurate inference. Its explicit parameters improve interpretability but require model-selection choices, and extensions remain open.

  • Motivation: One-mode projections discard information and create overlapping cliques that can violate community-detection null-model assumptions.Structurally different bipartite networks can share an identical projection.
  • Results: In ambiguous-projection synthetic networks, the biSBM substantially outperformed all projection-based methods.The networks included type a vertices with high connection probability to all type b vertices.
  • Comparison with SBM: The biSBM uses known vertex types to achieve substantially more efficient and accurate inference than the unconstrained SBM on bipartite data.The SBM must learn bipartiteness, making it more prone to overfitting and mixed-type partitions.
  • Model selection: The model's explicit Ka and Kb choices support imbalanced networks but require parameter specification and model selection.Choosing these parameters is related to, but distinct from, choosing the number of communities.
  • Model selection: Likelihood-based model selection remains difficult because rugged likelihood functions can invalidate standard assumptions and make AIC or BIC decisions incorrect.Likelihood-ratio and MDL-based approaches are described as promising or recently developed.
  • Interpretability and future work: The biSBM provides a clear generative hypothesis with interpretable parameters, while mixed-membership, weighted-edge, hierarchical, and richer multipartite extensions remain future directions.The matrix ω is described as informative about hypothetical mechanisms underlying the data-generating processes.

Appendix B: Southern Women

The Southern Women appendix presents a maximum-likelihood bipartite-SBM partition of the network's women into two groups. The supplied passage identifies the groups and their members, while the second passage contrasts degree-uncorrected and degree-corrected partitioning on another network.

  • Southern Women partition: The maximum-likelihood partition assigns the listed Southern Women participants to Group A or Group B.Group A is shown in red and Group B in blue.
  • Degree correction: Without degree correction, the biSBM tends to group vertices with similar degree, producing unintuitive partitions for heterogeneous degree distributions.The Malaria-network comparison uses vertex size to represent degree.
Loading 1403.2933v2…