Skip to main content

An algorithm to find overlapping community structure in networks

Steve Gregory, An algorithm to find overlapping community structure in networks. Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2007). ISBN 978-3-540-74975-2, pp. 91–102. September 2007. PDF, 254 Kbytes.


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.

Bibtex entry.

Contact details

Publication Admin