CoDÆN: Benchmarks and Comparison of Evolutionary Community Detection Algorithms for Dynamic Networks
Open Access
- 22 August 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on the Web
- Vol. 19 (3) , 1-25
Abstract
Web data are often modelled as complex networks in which entities interact and form communities. Nevertheless, web data evolves over time, and network communities change alongside it. This makes Community Detection (CD) in dynamic graphs a relevant problem, calling for evolutionary CD algorithms. The choice and evaluation of such algorithm performance is challenging because of the lack of a comprehensive set of benchmarks and specific metrics. To address these challenges, we propose CoDÆN—Community Detection Algorithms in Evolving Networks—a benchmarking framework for evolutionary CD algorithms in dynamic networks, that we offer as open source to the community. CoDÆN allows us to generate synthetic community-structured graphs with known ground truth and design evolving scenarios combining nine basic graph transformations that modify edges, nodes, and communities. We propose three complementary metrics (i.e., Correctness, Delay, and Stability) to compare evolutionary CD algorithms. Armed with CoDÆN, we consider three evolutionary modularity-based CD approaches, dissecting their performance to gauge the trade-off between the stability of the communities and their correctness. Next, we compare the algorithms in real Web-oriented datasets, confirming such a trade-off. Our findings reveal that algorithms that introduce memory in the graph maximise stability but add delay when abrupt changes occur. Conversely, algorithms that introduce memory by initialising the CD algorithms with the previous solution fail to identify the split and birth of new communities. These observations underscore the value of CoDÆN in facilitating the study and comparison of alternative evolutionary community detection algorithms.Keywords
Funding Information
- National Center for HPC, Big Data and Quantum Computing (CN00000013)
This publication has 70 references indexed in Scilit:
- Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detectionApplied Network Science, 2023
- Clique Percolation Method: Memory Efficient Almost Exact Communities2022
- Motif‐based embedding label propagation algorithm for community detectionInternational Journal of Intelligent Systems, 2021
- Hybrid Louvain-Clustering Model Using Knowledge Graph for Improvement of Clustering User’s Behavior on Social Networks2021
- Community detection in node-attributed social networks: A surveyComputer Science Review, 2020
- Time-Dependent Graphs: Definitions, Applications, and AlgorithmsData Science and Engineering, 2019
- Tracking community evolution in social networks: A surveyInformation Processing & Management, 2019
- Community detection in social networksWIREs Data Mining and Knowledge Discovery, 2016
- MONIC and Followups on Modeling and Monitoring Cluster TransitionsLecture Notes in Computer Science, 2013
- On Nearest-Neighbor GraphsDiscrete & Computational Geometry, 1997