Post-processing partitions to identify domains of modularity optimization

Abstract

We introduce the Convex Hull of Admissible Modularity Partitions (CHAMP) algorithm to prune and prioritize different network community structures identified across multiple runs of possibly various computational heuristics. Given a set of partitions, CHAMP identifies the domain of modularity optimization for each partition ---i.e., the parameter-space domain where it has the largest modularity relative to the input set---discarding partitions with empty domains to obtain the subset of partitions that are "admissible" candidate community structures that remain potentially optimal over indicated parameter domains. Importantly, CHAMP can be used for multi-dimensional parameter spaces, such as those for multilayer networks where one includes a resolution parameter and interlayer coupling. Using the results from CHAMP, a user can more appropriately select robust community structures by observing the sizes of domains of optimization and the pairwise comparisons between partitions in the admissible subset. We demonstrate the utility of CHAMP with several example networks. In these examples, CHAMP focuses attention onto pruned subsets of admissible partitions that are 20-to-1785 times smaller than the sets of unique partitions obtained by community detection heuristics that were input into CHAMP.

http://www.mdpi.com/1999-4893/10/3/93

References in corpus (28)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Multilayer Networks
• Resolution limit in community detection
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Statistical Mechanics of Community Detection
• Community detection in networks: A user guide
• Community structure in directed networks
• The performance of modularity maximization in practical contexts
• Mathematical Formulation of Multi-Layer Networks
• Consensus clustering in complex networks
• Modularity and community detection in bipartite networks
• Robust Detection of Dynamic Community Structure in Networks
• Community detection in networks with positive and negative links
• Analysis of the structure of complex networks at different resolution levels
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• Analysis of community structure in networks of correlated data
• The many facets of community detection in complex networks
• Clique Graphs and Overlapping Communities
• Significant Scales in Community Structure
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
• Mesoscopic analysis of networks: applications to exploratory analysis and data clustering

Cited by in corpus (6)

• Multilayer Brain Networks
• Exploring the solution landscape enables more reliable network community detection
• Gene communities in co-expression networks across different tissues
• Consistency landscape of network communities
• Transient crosslinking kinetics optimize gene cluster interactions
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure