KIT | KIT-Bibliothek | Impressum | Datenschutz

Local community detection based on small cliques

Hamann, Michael; Röhrs, Eike; Wagner, Dorothea

Abstract:
Community detection aims to find dense subgraphs in a network. We consider the problem of finding a community locally around a seed node both in unweighted and weighted networks. This is a faster alternative to algorithms that detect communities that cover the whole network when actually only a single community is required. Further, many overlapping community detection algorithms use local community detection algorithms as basic building block. We provide a broad comparison of different existing strategies of expanding a seed node greedily into a community. For this, we conduct an extensive experimental evaluation both on synthetic benchmark graphs as well as real world networks. We show that results both on synthetic as well as real-world networks can be significantly improved by starting from the largest clique in the neighborhood of the seed node. Further, our experiments indicate that algorithms using scores based on triangles outperform other algorithms in most cases. We provide theoretical descriptions as well as open source implementations of all algorithms used.

Open Access Logo


Volltext §
DOI: 10.5445/IR/1000075429
Originalveröffentlichung
DOI: 10.3390/a10030090
Scopus
Zitationen: 2
Seitenaufrufe: 8
seit 04.05.2018
Downloads: 23
seit 31.12.2017
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Jahr 2017
Sprache Englisch
Identifikator ISSN: 1999-4893
urn:nbn:de:swb:90-754295
KITopen-ID: 1000075429
Erschienen in Algorithms
Band 10
Heft 3
Seiten Art.Nr.: 90
Schlagworte community detection, local community, clique, iterative expansion
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page