Exploring the limits of community detection strategies in complex networks

Abstract

The characterization of network community structure has profound implications in several scientific areas. Therefore, testing the algorithms developed to establish the optimal division of a network into communities is a fundamental problem in the field. We performed here a highly detailed evaluation of community detection algorithms, which has two main novelties: 1) using complex closed benchmarks, which provide precise ways to assess whether the solutions generated by the algorithms are optimal; and, 2) A novel type of analysis, based on hierarchically clustering the solutions suggested by multiple community detection algorithms, which allows to easily visualize how different are those solutions. Surprise, a global parameter that evaluates the quality of a partition, confirms the power of these analyses. We show that none of the community detection algorithms tested provide consistently optimal results in all networks and that Surprise maximization, obtained by combining multiple algorithms, obtains quasi-optimal performances in these difficult benchmarks.

13 pages, 8 figures, 1 table. Scientific Reports (in press)

References in corpus (14)

• Fast unfolding of communities in large networks
• 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
• Resolution limit in community detection
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Finding statistically significant communities in networks
• Narrow scope for resolution-limit-free community detection
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Comparative Evaluation of Community Detection Algorithms: A Topological Approach
• Surprise maximization reveals the community structure of complex networks
• Jerarca: Efficient Analysis of Complex Networks Using Hierarchical Clustering
• Closed benchmarks for network community structure characterization

Cited by in corpus (15)

• Men Set Their Own Cites High: Gender and Self-citation across Fields and over Time
• Infomap Bioregions: Interactive mapping of biogeographical regions from species distributions
• Detecting communities using asymptotical Surprise
• Flow networks: A characterization of geophysical fluid transport
• Estimating the resolution limit of the map equation in community detection
• Constrained information flows in temporal networks reveal intermittent communities
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Mesoscopic analysis of online social networks - The role of negative ties
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Detecting Core-Periphery Structures by Surprise
• SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
• Generalized Markov stability of network communities
• Mining the modular structure of protein interaction networks
• Network Community Detection on Metric Space
• Community Detection with the Map Equation and Infomap: Theory and Applications