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 (11)

• Fast unfolding of communities in large networks
• 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
• Extracting the hierarchical organization of complex systems
• Narrow scope for resolution-limit-free community detection
• Limited resolution in complex network community detection with Potts model approach
• Model selection and hypothesis testing for large-scale network models with overlapping groups