Skip to content
Preprint

Exact Community Recovery in Bipartite Networks

Sep 2026 · 0 citations · 24 references
Computer Science Mathematics

TL;DR

This work proves that a simple spectral clustering algorithm based on the diagonal-deleted Gram matrix achieves exact recovery with high probability under mild conditions on sparsity, community balance, and the number of clusters.

Abstract

Community detection in bipartite networks is a fundamental problem in modern data analysis, with applications in recommendation systems, biological networks, and social network analysis. Unlike conventional unipartite graphs, bipartite networks consist of two distinct types of nodes with edges only connecting across types, so recovering latent communities requires estimating labels on the two node types. The stochastic co-blockmodel is a classical probabilistic framework for such networks, yet theoretical guarantees for exact community recovery in this setting remain limited, especially when the number of communities grows, the community sizes are unbalanced, or the degrees are heterogeneous. In this work, we prove that a simple spectral clustering algorithm based on the diagonal-deleted Gram matrix achieves exact recovery with high probability under mild conditions on sparsity, community balance, and the number of clusters. We further extend the result to the degree-corrected stochastic co-blockmodel, where each node carries its own degree heterogeneity parameter, and show that a row-normalized version of the same algorithm maintains the exact recovery guarantee. Extensive experiments validate our theoretical findings.

View source

Similar papers

Conference Aug 2026

Performance Trade-offs of Community Detection Algorithms in Dense and Sparse Network Topologies

Community detection is commonly used to uncover latent group structure in complex networks, but its effectiveness is highly dependent on the topology of the graph being analyzed. An algorithm that performs well on a dense social network may not show the same behavior on a sparse collaboration network, making it difficu...

Renaldy Fredyan, Donny Fernando · 0 citations
Review Open access Sep 2026

Spectral Graph Methods for Community Detection in Complex Networks

By connecting core linear algebra with practical structure discovery, the review clarifies both the continuing value and the limits of the spectral perspective.

Ji Li · 0 citations
#machine learning Preprint Oct 2026

Degree-Corrected Joint Matrix Factorization for Multilayer Community Detection

Multilayer networks allow the modeling of interactions between the same entities across different contexts, such as temporal observations, varying settings, or interactions of different types. The goal of community detection in multilayer networks is to identify groups of nodes exhibiting similar connectivity patterns,...

Alexandra Dache, Manon Rustin, Arnaud Vandaele et al. · 0 citations
Sep 2026

A Novel Approach for the SDIR Epidemic Model on Online Social Networks

Information diffusion can be controlled by restricting or removing links (edges) in online social networks, as well as in real-world networks. To identify the most influential links to remove while minimizing diffusion, previous studies have proposed upper bounds for spreading processes in SIR and SIS models, using sup...

Phúc Hồng Nguyễn, K. Duong, Dung Phi Hoang · 0 citations
Sep 2026

WCCS: Efficient Wedge Conductance Community Search over Large Temporal Bipartite Graphs (Full Paper)

An online priority-driven filter-and-expand framework with several effective pruning techniques and a powerful geometric slope optimization for rapid temporal wedge conductance calculation is developed and a novel temporal wedge conductance metric is proposed that explicitly balances internal density and external spars...

Long-Long Lin, Wei Chen, Ping-Peng Yuan et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.