TY - GEN
T1 - A dynamic algorithm for local community detection in graphs
AU - Zakrzewska, Anita
AU - Bader, David A.
N1 - Publisher Copyright:
© 2015 ACM.
PY - 2015/8/25
Y1 - 2015/8/25
N2 - A variety of massive datasets, such as social networks and biological data, are represented as graphs that reveal underlying connections, trends, and anomalies. Community detection is the task of discovering dense groups of vertices in a graph. Its one specific form is seed set expansion, which finds the best local community for a given set of seed vertices. Greedy, agglomerative algorithms, which are commonly used in seed set expansion, have been previously designed only for a static, unchanging graph. However, in many applications, new data is constantly produced, and vertices and edges are inserted and removed from a graph. We present an algorithm for dynamic seed set expansion, which incrementally updates the community as the underlying graph changes. We show that our dynamic algorithm outputs high quality communities that are similar to those found when using a standard static algorithm. The dynamic approach also improves performance compared to re-computation, achieving speedups of up to 600x.
AB - A variety of massive datasets, such as social networks and biological data, are represented as graphs that reveal underlying connections, trends, and anomalies. Community detection is the task of discovering dense groups of vertices in a graph. Its one specific form is seed set expansion, which finds the best local community for a given set of seed vertices. Greedy, agglomerative algorithms, which are commonly used in seed set expansion, have been previously designed only for a static, unchanging graph. However, in many applications, new data is constantly produced, and vertices and edges are inserted and removed from a graph. We present an algorithm for dynamic seed set expansion, which incrementally updates the community as the underlying graph changes. We show that our dynamic algorithm outputs high quality communities that are similar to those found when using a standard static algorithm. The dynamic approach also improves performance compared to re-computation, achieving speedups of up to 600x.
UR - https://www.scopus.com/pages/publications/84962564760
UR - https://www.scopus.com/pages/publications/84962564760#tab=citedBy
U2 - 10.1145/2808797.2809375
DO - 10.1145/2808797.2809375
M3 - Conference contribution
AN - SCOPUS:84962564760
T3 - Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015
SP - 559
EP - 564
BT - Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015
A2 - Pei, Jian
A2 - Silvestri, Fabrizio
A2 - Tang, Jie
PB - Association for Computing Machinery
T2 - 7th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015
Y2 - 25 August 2015 through 28 August 2015
ER -