Exploring the solution landscape enables more reliable network community detection

Abstract

To understand how a complex system is organized and functions, researchers often identify communities in the system's network of interactions. Because it is practically impossible to explore all solutions to guarantee the best one, many community-detection algorithms rely on multiple stochastic searches. But for a given combination of network and stochastic algorithm, how many searches are sufficient to find a solution that is good enough? The standard approach is to pick a reasonably large number of searches and select the network partition with the highest quality or derive a consensus solution based on all network partitions. However, if different partitions have similar qualities such that the solution landscape is degenerate, the single best partition may miss relevant information, and a consensus solution may blur complementary communities. Here we address this degeneracy problem with coarse-grained descriptions of the solution landscape. We cluster network partitions based on their similarity and suggest an approach to determine the minimum number of searches required to describe the solution landscape adequately. To make good use of all partitions, we also propose different ways to explore the solution landscape, including a significance clustering procedure. We test these approaches on synthetic networks and a real-world network using two contrasting community-detection algorithms: The algorithm that can identify more general structures requires more searches and networks with clearer community structures require fewer searches. We also find that exploring the coarse-grained solution landscape can reveal complementary solutions and enable more reliable community detection.

References in corpus (22)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Community detection in graphs
• Natural Scales in Geographical Patterns
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Detecting the overlapping and hierarchical community structure of complex networks
• The performance of modularity maximization in practical contexts
• Consensus clustering in complex networks
• Mapping change in large networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Phase transition in the detection of modules in sparse networks
• Robustness of community structure in networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Element-centric clustering comparison unifies overlaps and hierarchy
• Fast consensus clustering in complex networks
• Post-processing partitions to identify domains of modularity optimization
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks

Cited by in corpus (12)

• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Revealing consensus and dissensus between network partitions
• Representative community divisions of networks
• The Minimum Description Length Principle for Pattern Mining: A Survey
• Cross-validation of correlation networks using modular structure
• Mapping robust multiscale communities in chromosome contact networks
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Identifying robust features of community structure in complex networks
• Community detection by resistance distance: automation and benchmark testing
• Ensemble approach for generalized network dismantling
• Beyond One Solution: The Case for a Comprehensive Exploration of Solution Space in Community Detection
• Community membership consistency applied to corporate board interlock networks