An algorithm to find overlapping community structure in networks

S Gregory

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

249 Citations (Scopus)


Recent years have seen the development of many graph clustering algorithms, which can identify community structure in networks. The vast majority of these only find disjoint communities, but in many real-world networks communities overlap to some extent. We present a new algorithm for discovering overlapping communities in networks, by extending Girvan and Newman's well-known algorithm based on the betweenness centrality measure. Like the original algorithm, ours performs hierarchical clustering -- partitioning a network into any desired number of clusters -- but allows them to overlap. Experiments confirm good performance on randomly generated networks based on a known overlapping community structure, and interesting results have also been obtained on a range of real-world networks.
Translated title of the contributionAn algorithm to find overlapping community structure in networks
Original languageEnglish
Title of host publicationKnowledge Discovery in Databases: PKDD 2007, 11th European Conference on Principles and Practice of Knowledge Discovery in Databases, Warsaw, Poland, 17-21 September
EditorsJoost N. Kok, Andrzej Skowron
Pages91 - 102
Number of pages12
ISBN (Print)9783540749752
Publication statusPublished - 17 Sept 2007

Bibliographical note

Other: Lecture Notes in Computer Science 4702


Dive into the research topics of 'An algorithm to find overlapping community structure in networks'. Together they form a unique fingerprint.

Cite this