Multiresolution Consensus Clustering in Networks

Abstract

Networks often exhibit structure at disparate scales. We propose a method for identifying community structure at different scales based on multiresolution modularity and consensus clustering. Our contribution consists of two parts. First, we propose a strategy for sampling the entire range of possible resolutions for the multiresolution modularity quality function. Our approach is directly based on the properties of modularity and, in particular, provides a natural way of avoiding the need to increase the resolution parameter by several orders of magnitude to break a few remaining small communities, necessitating the introduction of ad-hoc limits to the resolution range with standard sampling approaches. Second, we propose a hierarchical consensus clustering procedure, based on a modified modularity, that allows one to construct a hierarchical consensus structure given a set of input partitions. While here we are interested in its application to partitions sampled using multiresolution modularity, this consensus clustering procedure can be applied to the output of any clustering algorithm. As such, we see many potential applications of the individual parts of our multiresolution consensus clustering procedure in addition to using the procedure itself to identify hierarchical structure in networks.

19 pages, 9 figures, code available at https://github.com/LJeub/HierarchicalConsensus

References in corpus (20)

• 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
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The performance of modularity maximization in practical contexts
• Extracting the hierarchical organization of complex systems
• The ground truth about metadata and community detection in networks
• Narrow scope for resolution-limit-free community detection
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Limited resolution in complex network community detection with Potts model approach
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• The Impact of Random Models on Clustering Similarity