Skip to main content

A fast algorithm to find overlapping communities in networks

Steve Gregory, A fast algorithm to find overlapping communities in networks. Proceedings of the 12th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2008). ISBN 978-3-540-87478-2, pp. 408–423. September 2008. PDF, 154 Kbytes.


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.

Bibtex entry.

Contact details

Publication Admin