A spectral algorithm with additive clustering for the recovery of overlapping communities in networks

DOI10.1007/978-3-319-46379-7_24zbMATH Open1398.68442arXiv1506.04158OpenAlexW3023166002MaRDI QIDQ1663638FDOQ1663638

Authors: Emilie Kaufmann, Thomas Bonald, Marc Lelarge 

Publication date: 22 August 2018

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1506.04158

Recommendations

• A spectral algorithm with additive clustering for the recovery of overlapping communities in networks
• Detecting overlapping communities in networks using spectral methods
• Overlapping community detection in networks via sparse spectral decomposition
• Overlapping community detection using a generative model for networks
• Uncovering the overlapping community structure of complex networks by maximal cliques

zbMATH Keywords

community detectionstochastic blockmodel

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Social networks; opinion dynamics (91D30)

Cites Work

• Title not available (Why is that?)
• Elements of Information Theory
• Spectral clustering and the high-dimensional stochastic blockmodel
• The Rotation of Eigenvectors by a Perturbation. III
• Title not available (Why is that?)
• Consistency of community detection in networks under degree-corrected stochastic block models
• Matrix estimation by universal singular value thresholding
• Consistency of spectral clustering in stochastic block models
• Spectral redemption in clustering sparse networks
• Mixed membership stochastic blockmodels
• Concentration inequalities. A nonasymptotic theory of independence
• Overlapping stochastic block models with application to the French political blogosphere
• User-friendly tail bounds for sums of random matrices
• Title not available (Why is that?)
• Overlapping community detection in networks

Cited In (4)

• Survival Mixed Membership Blockmodel
• Community Detection and Stochastic Block Models
• Estimating Mixed Memberships With Sharp Eigenvector Deviations
• Detecting Overlapping Communities in Networks Using Spectral Methods

Uses Software

• SNAP
• k-means++

This page was built for publication: A spectral algorithm with additive clustering for the recovery of overlapping communities in networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1663638)