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 contribution||An algorithm to find overlapping community structure in networks|
|Title of host publication||Knowledge Discovery in Databases: PKDD 2007, 11th European Conference on Principles and Practice of Knowledge Discovery in Databases, Warsaw, Poland, 17-21 September|
|Editors||Joost N. Kok, Andrzej Skowron|
|Pages||91 - 102|
|Number of pages||12|
|Publication status||Published - 17 Sep 2007|