A dynamic algorithm for local community detection in graphs

Anita Zakrzewska, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

45 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015
EditorsJian Pei, Jie Tang, Fabrizio Silvestri
PublisherAssociation for Computing Machinery, Inc
Pages559-564
Number of pages6
ISBN (Electronic)9781450338547
DOIs
StatePublished - Aug 25 2015
Externally publishedYes
EventIEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015 - Paris, France
Duration: Aug 25 2015Aug 28 2015

Publication series

NameProceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015

Other

OtherIEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015
Country/TerritoryFrance
CityParis
Period8/25/158/28/15

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'A dynamic algorithm for local community detection in graphs'. Together they form a unique fingerprint.

Cite this