TY - GEN
T1 - A fast algorithm to find overlapping communities in networks
AU - Gregory, Steve
PY - 2008/10/21
Y1 - 2008/10/21
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/56049112624
UR - http://www.cs.bris.ac.uk/Publications/pub_master.jsp?id=2000885
U2 - 10.1007/978-3-540-87479-9_45
DO - 10.1007/978-3-540-87479-9_45
M3 - Conference Contribution (Conference Proceeding)
SN - 9783540874782
T3 - Lecture Notes in Computer Science
SP - 408
EP - 423
BT - Machine Learning and Knowledge Discovery in Databases
PB - Springer
ER -