Robustness of community structure under edge addition

Abstract

Communities often represent key structural and functional clusters in networks. To preserve such communities, it is important to understand their robustness under network perturbations. Previous work in community robustness analysis has focused on studying changes in the community structure as a response of edge rewiring and node or edge removal. However, the impact of increasing connectivity on the robustness of communities in networked systems is relatively unexplored. Studying the limits of community robustness under edge addition is crucial to better understanding the cases in which density expands or false edges erroneously appear. In this paper, we analyze the effect of edge addition on community robustness in synthetic and empirical temporal networks. We study two scenarios of edge addition: random and targeted. We use four community detection algorithms, Infomap, Label Propagation, Leiden, and Louvain, and demonstrate the results in community similarity metrics. The experiments on synthetic networks show that communities are more robust when the initial partition is stronger or the edge addition is random, and the experiments on empirical data also indicate that robustness performance can be affected by the community similarity metric. Overall, our results suggest that the communities identified by the different types of community detection algorithms exhibit different levels of robustness, and so the robustness of communities depends strongly on the choice of detection method.

arXiv comment17 pages, 30 figures

References in corpus (25)

• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Community detection in graphs
• Finding community structure in very large networks
• Error and attack tolerance of complex networks
• From Louvain to Leiden: guaranteeing well-connected communities
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Community detection algorithms: a comparative analysis
• Attack vulnerability of complex networks
• Community detection in networks: A user guide
• Self-similar community structure in organisations
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Consensus clustering in complex networks
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• The ground truth about metadata and community detection in networks
• Robustness of community structure in networks
• Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
• Element-centric clustering comparison unifies overlaps and hierarchy
• Community detection in networks using graph embeddings
• Fast consensus clustering in complex networks
• Robustness of community structure to node removal

Cited by in corpus (2)

• Identifying robust features of community structure in complex networks
• Community detection robustness of graph neural networks