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 contribution||A fast algorithm to find overlapping communities in networks|
|Title of host publication||Machine Learning and Knowledge Discovery in Databases|
|Subtitle of host publication||European Conference, ECML PKDD 2008, Antwerp, Belgium, September 15-19, 2008, Proceedings, Part I|
|Number of pages||16|
|Publication status||Published - 21 Oct 2008|
|Name||Lecture Notes in Computer Science|