Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection
Open Access
- 18 September 2023
- journal article
- research article
- Published by Springer Nature in Applied Network Science
- Vol. 8 (1) , 1-29
Abstract
Dynamic (temporal) graphs are a convenient mathematical abstraction for many practical complex systems including social contacts, business transactions, and computer communications. Community discovery is an extensively used graph analysis kernel with rich literature for static graphs. However, community discovery in a dynamic setting is challenging for two specific reasons. Firstly, the notion of temporal community lacks a widely accepted formalization, and only limited work exists on understanding how communities emerge over time. Secondly, the added temporal dimension along with the sheer size of modern graph data necessitates new scalable algorithms. In this paper, we investigate how communities evolve over time based on several graph metrics under a temporal formalization. We compare six different algorithmic approaches for dynamic community detection for their quality and runtime. We identify that a vertex-centric (local) optimization method works as efficiently as the classical modularity-based methods. To its advantage, such local computation allows for the efficient design of parallel algorithms without incurring a significant parallel overhead. Based on this insight, we design a shared-memory parallel algorithmDyComPar, which demonstrates between 4 and 18 fold speed-up on a multi-core machine with 20 threads, for several real-world and synthetic graphs from different domains.Keywords
Funding Information
- Lawrence Berkeley National Laboratory (Contract No. DE-AC02-05CH11231, Contract No. DE-AC02-05CH11231)
- National Science Foundation (Award No. 2323533)
This publication has 48 references indexed in Scilit:
- Evolutionary community structure discovery in dynamic weighted networksPhysica A: Statistical Mechanics and its Applications, 2014
- Defining and evaluating network communities based on ground-truthKnowledge and Information Systems, 2013
- Computer science fields as ground-truth communities2013
- Sequential detection of temporal communities by estrangement confinementScientific Reports, 2012
- High-Resolution Measurements of Face-to-Face Contact Patterns in a Primary SchoolPLOS ONE, 2011
- Community Structure in Time-Dependent, Multiscale, and Multiplex NetworksScience, 2010
- Community detection algorithms: A comparative analysisPhysical Review E, 2009
- Benchmark graphs for testing community detection algorithmsPhysical Review E, 2008
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002