A Spectral Algorithm with Additive Clustering for the Recovery of Overlapping Communities in Networks

2015/06/12 by Emilie Kaufmann, Kaufmann, Emilie, Thomas Bonald +3
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (stat.ML) #Opinion Dynamics and Social Influence #Theoretical and Computational Physics #stat.ML

paper · pdf · doi:10.48550/arxiv.1506.04158

Journal of Theoretical Computer Science (TCS), Elsevier, A Paraître

openalex publication_date 2015/06/12 · arxiv created 2017/11/06 · arxiv updated 2017/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper presents a novel spectral algorithm with additive clustering designed to identify overlapping communities in networks. The algorithm is based on geometric properties of the spectrum of the expected adjacency matrix in a random graph model that we call stochastic blockmodel with overlap (SBMO). An adaptive version of the algorithm, that does not require the knowledge of the number of hidden communities, is proved to be consistent under the SBMO when the degrees in the graph are (slightly more than) logarithmic. The algorithm is shown to perform well on simulated data and on real-world graphs with known overlapping communities.

Citations

• The Rotation of Eigenvectors by a Perturbation. III
• A tutorial on spectral clustering
• Uncovering the overlapping community structure of complex networks in nature and society

Related

• Detecting Overlapping Communities in Networks Using Spectral Methods
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Community detection over a heterogeneous population of non-aligned networks
• A spectral method for community detection in moderately-sparse degree-corrected stochastic block models
• Spectral redemption in clustering sparse networks