A Comparative Analysis of Community Detection Algorithms on Artificial Networks

Abstract

Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms' computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm's predicting power and the effective computing time.

arXiv comment18 pages, 8 figures

References in corpus (29)

• Emergence of scaling in random networks
• 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
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Statistical Mechanics of Community Detection
• Self-similar community structure in organisations
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The map equation
• An information-theoretic framework for resolving community structure in complex networks
• Community detection in networks with positive and negative links
• Structure and inference in annotated networks
• Characterizing the community structure of complex networks
• Community detection in networks: Structural communities versus ground truth
• Complex cooperative networks from evolutionary preferential attachment
• Evaluating Local Community Methods in Networks
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Evaluating accuracy of community detection using the relative normalized mutual information
• Effect of size heterogeneity on community identification in complex networks

Cited by in corpus (34)

• From Louvain to Leiden: guaranteeing well-connected communities
• The ground truth about metadata and community detection in networks
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Multilayer Brain Networks
• Fake news agenda in the era of COVID-19: Identifying trends through fact-checking content
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Network polarization, filter bubbles, and echo chambers: An annotated review of measures and reduction methods
• Comparative evaluation of community-aware centrality measures
• Characterization of citizens using word2vec and latent topic analysis in a large set of tweets
• The time geography of segregation during working hours
• Hierarchical benchmark graphs for testing community detection algorithms
• Synwalk -- Community Detection via Random Walk Modelling
• Embedding-based Silhouette Community Detection
• Ensemble Clustering for Graphs
• Ensemble Clustering for Graphs: Comparisons and Applications
• Exploring the effect of streamed social media data variations on social network analysis
• Opinion formation on social networks with algorithmic bias: Dynamics and bias imbalance
• Digging the topology of rock art in Northwestern Patagonia
• Robustness of community structure under edge addition
• A Review of Spatial Network Insights and Methods in the Context of Planning: Applications, Challenges, and Opportunities
• An Exact No Free Lunch Theorem for Community Detection
• Structure constrained by metadata in networks of chess players
• Social network structure and the spread of complex contagions from a population genetics perspective
• Performance of attack strategies on modular networks
• Metrics matter in community detection
• Identifying robust features of community structure in complex networks
• Mutual information and the encoding of contingency tables
• HiPart: Hierarchical Divisive Clustering Toolbox
• AOC; Assembling Overlapping Communities
• EC-SBM Synthetic Network Generator
• I will be there for you: six friends in a clique
• Community detection analysis in wind speed-monitoring systems using mutual information-based complex network
• On the Modeling and Simulation of Portfolio Allocation Schemes: an Approach based on Network Community Detection
• A modified Ricci flow on arbitrary weighted graph