A fast algorithm to find overlapping communities in networks

Steve Gregory

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

130 Citations (Scopus)
229 Downloads (Pure)

Abstract

Many networks possess a community structure, such that vertices form densely connected groups which are more sparsely linked to other groups. In some cases these groups overlap, with some vertices shared between two or more communities. Discovering communities in networks is a computationally challenging task, especially if they overlap. In previous work we proposed an algorithm, CONGA, that could detect overlapping communities using the new concept of split betweenness. Here we present an improved algorithm based on a local form of betweenness, which yields good results but is much faster. It is especially effective in discovering small-diameter communities in large networks, and has a time complexity of only O(n log n) for sparse networks.
Translated title of the contributionA fast algorithm to find overlapping communities in networks
Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationEuropean Conference, ECML PKDD 2008, Antwerp, Belgium, September 15-19, 2008, Proceedings, Part I
PublisherSpringer
Pages408-423
Number of pages16
ISBN (Electronic)9783540874799
ISBN (Print)9783540874782
DOIs
Publication statusPublished - 21 Oct 2008

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5211
ISSN (Print)0302-9743

Cite this