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

Emilie Kaufmann; Thomas Bonald; Marc Lelarge

doi:10.1007/978-3-319-46379-7_24

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

Emilie Kaufmann
, Thomas Bonald
, Marc Lelarge

University of Lille 1
Université Paris-Saclay
PSL research University & IPSL

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

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.

langue originale	Anglais
titre	Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings
rédacteurs en chef	Hans Ulrich Simon, Sandra Zilles, Ronald Ortner
Editeur	Springer Verlag
Pages	355-370
Nombre de pages	16
ISBN (imprimé)	9783319463780
Les DOIs	https://doi.org/10.1007/978-3-319-46379-7_24
état	Publié - 1 janv. 2016
Modification externe	Oui
Evénement	27th International Conference on Algorithmic Learning Theory, ALT 2016 - Bari, Italie Durée: 19 oct. 2016 → 21 oct. 2016

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9925 LNAI
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	27th International Conference on Algorithmic Learning Theory, ALT 2016
Pays/Territoire	Italie
La ville	Bari
période	19/10/16 → 21/10/16

Accès au document

10.1007/978-3-319-46379-7_24

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

Kaufmann, E., Bonald, T., & Lelarge, M. (2016). A spectral algorithm with additive clustering for the recovery of overlapping communities in networks. Dans H. U. Simon, S. Zilles, & R. Ortner (eds.), Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings (p. 355-370). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol 9925 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-46379-7_24

Kaufmann, Emilie ; Bonald, Thomas ; Lelarge, Marc. / A spectral algorithm with additive clustering for the recovery of overlapping communities in networks. Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings. Editeur / Hans Ulrich Simon ; Sandra Zilles ; Ronald Ortner. Springer Verlag, 2016. p. 355-370 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2cd67e3ebad34214abaf0c8a0400a3f9,

title = "A spectral algorithm with additive clustering for the recovery of overlapping communities in networks",

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.",

author = "Emilie Kaufmann and Thomas Bonald and Marc Lelarge",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 27th International Conference on Algorithmic Learning Theory, ALT 2016 ; Conference date: 19-10-2016 Through 21-10-2016",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-319-46379-7\_24",

language = "English",

isbn = "9783319463780",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "355--370",

editor = "Simon, \{Hans Ulrich\} and Sandra Zilles and Ronald Ortner",

booktitle = "Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings",

}

Kaufmann, E, Bonald, T & Lelarge, M 2016, A spectral algorithm with additive clustering for the recovery of overlapping communities in networks. Dans HU Simon, S Zilles & R Ortner (eds), Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), VOL. 9925 LNAI, Springer Verlag, p. 355-370, 27th International Conference on Algorithmic Learning Theory, ALT 2016, Bari, Italie, 19/10/16. https://doi.org/10.1007/978-3-319-46379-7_24

A spectral algorithm with additive clustering for the recovery of overlapping communities in networks. / Kaufmann, Emilie; Bonald, Thomas; Lelarge, Marc.
Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings. Ed. / Hans Ulrich Simon; Sandra Zilles; Ronald Ortner. Springer Verlag, 2016. p. 355-370 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol 9925 LNAI).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

TY - GEN

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

AU - Kaufmann, Emilie

AU - Bonald, Thomas

AU - Lelarge, Marc

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84994096908

U2 - 10.1007/978-3-319-46379-7_24

DO - 10.1007/978-3-319-46379-7_24

M3 - Conference contribution

AN - SCOPUS:84994096908

SN - 9783319463780

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 355

EP - 370

BT - Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings

A2 - Simon, Hans Ulrich

A2 - Zilles, Sandra

A2 - Ortner, Ronald

PB - Springer Verlag

T2 - 27th International Conference on Algorithmic Learning Theory, ALT 2016

Y2 - 19 October 2016 through 21 October 2016

ER -

Kaufmann E, Bonald T, Lelarge M. A spectral algorithm with additive clustering for the recovery of overlapping communities in networks. Dans Simon HU, Zilles S, Ortner R, rédacteurs en chef, Algorithmic Learning Theory - 27th International Conference, ALT 2016, Proceedings. Springer Verlag. 2016. p. 355-370. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-46379-7_24

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

Résumé

Série de publications

Une conférence

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation