Papers for

biological data analysts

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Spectral clustering enables exact community detection in bipartite networks

Exact Community Recovery in Bipartite Networks

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.

Fri 11 SeptSocial and Information Networks
The gist
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.
Open 2609.12445v1