Fast incremental community detection on dynamic graphs

Anita Zakrzewska, David A. Bader

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

3 Scopus citations

Abstract

Community detection, or graph clustering, is the problem of finding dense groups in a graph. This is important for a variety of applications, from social network analysis to biological interactions. While most work in community detection has focused on static graphs, real data is usually dynamic, changing over time. We present a new algorithm for dynamic community detection that incrementally updates clusters when the graph changes. The method is based on a greedy, modularity maximizing static approach and stores the history of merges in order to backtrack. On synthetic graph tests with known ground truth clusters, it can detect a variety of structural community changes for both small and large batches of edge updates.

Original languageEnglish (US)
Title of host publicationParallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015, Revised Selected Papers
EditorsEwa Deelman, Jack Dongarra, Konrad Karczewski, Roman Wyrzykowski, Jacek Kitowski, Kazimierz Wiatr
PublisherSpringer Verlag
Pages207-217
Number of pages11
ISBN (Print)9783319321486
DOIs
StatePublished - 2016
Externally publishedYes
Event11th International Conference on Parallel Processing and Applied Mathematics, PPAM 2015 - Krakow, Poland
Duration: Sep 6 2015Sep 9 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9573
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Parallel Processing and Applied Mathematics, PPAM 2015
Country/TerritoryPoland
CityKrakow
Period9/6/159/9/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Community detection
  • Dynamic graphs
  • Graph clustering
  • Graphs

Fingerprint

Dive into the research topics of 'Fast incremental community detection on dynamic graphs'. Together they form a unique fingerprint.

Cite this