Spectral clustering enables exact community detection in bipartite networks
Exact Community Recovery in Bipartite Networks
Social and Information Networks
Summary
Community detection means finding groups of related nodes in networks. Bipartite networks have two types of nodes connected only across types, making community detection harder. The authors show that a simple mathematical method, spectral clustering on a special matrix, can find the exact communities reliably under certain realistic conditions. They also extend this method to handle nodes with very different connection levels and confirm their theory with experiments.
What this means in practice
- •For recommendation system developers: Improve labeling of user and item groups in recommendation networks to boost match accuracy by using exact recovery spectral methods.
- •For biological data analysts: Identify exact clustered patterns in bipartite biological networks like gene-disease associations despite node degree variations.
Authors
Huan Qing
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.