Title :

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

Author(s) :

Kaufmann, Emilie [Auteur]

Sequential Learning [SEQUEL]
Bonald, Thomas [Auteur]
Laboratoire Traitement et Communication de l'Information [LTCI]
Laboratory of Information, Network and Communication Sciences [LINCS]
Lelarge, Marc [Auteur]
Dynamics of Geometric Networks [DYOGENE]
Laboratory of Information, Network and Communication Sciences [LINCS]

Journal title :

Theoretical Computer Science

Pages :

3-26

Publisher :

Elsevier

Publication date :

2018-09-19

ISSN :

1879-2294

English keyword(s) :

Community detection
Stochastic blockmodel

HAL domain(s) :

Statistiques [stat]/Machine Learning [stat.ML]
Mathématiques [math]/Probabilités [math.PR]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Graphes, Algorithmes et Probabilités

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL