Multiresolution community detection for megascale networks by information-based replica correlations

Abstract

We use a Potts model community detection algorithm to accurately and quantitatively evaluate the hierarchical or multiresolution structure of a graph. Our multiresolution algorithm calculates correlations among multiple copies ("replicas") of the same graph over a range of resolutions. Significant multiresolution structures are identified by strongly correlated replicas. The average normalized mutual information, the variation of information, and other measures in principle give a quantitative estimate of the "best" resolutions and indicate the relative strength of the structures in the graph. Because the method is based on information comparisons, it can in principle be used with any community detection model that can examine multiple resolutions. Our approach may be extended to other optimization problems. As a local measure, our Potts model avoids the "resolution limit" that affects other popular models. With this model, our community detection algorithm has an accuracy that ranks among the best of currently available methods. Using it, we can examine graphs over 40 million nodes and more than one billion edges. We further report that the multiresolution variant of our algorithm can solve systems of at least 200000 nodes and 10 million edges on a single processor with exceptionally high accuracy. For typical cases, we find a super-linear scaling, O(L^{1.3}) for community detection and O(L^{1.3} log N) for the multiresolution algorithm where L is the number of edges and N is the number of nodes in the system.

19 pages, 14 figures, published version with minor changes

References in corpus (23)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• 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
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of complex networks
• Extracting the hierarchical organization of complex systems
• Analysis of the structure of complex networks at different resolution levels
• Module identification in bipartite and directed networks
• Robustness of community structure in networks
• A sequential algorithm for fast clique percolation
• Community Detection as an Inference Problem
• Limited resolution in complex network community detection with Potts model approach
• Community Detection in Complex Networks by Dynamical Simplex Evolution
• Detecting modules in dense weighted networks with the Potts method
• What are the Best Hierarchical Descriptors for Complex Networks?
• Effect of size heterogeneity on community identification in complex networks
• Analysis of network by generalized mutual entropies
• Generalized entropies and open random and scale-free networks

Cited by in corpus (76)

• Community detection in graphs
• Community detection algorithms: a comparative analysis
• Community detection in networks: A user guide
• Mathematical Formulation of Multi-Layer Networks
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Hierarchical modularity in human brain functional networks
• Emergence of network features from multiplexity
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Detecting highly overlapping community structure by greedy clique expansion
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Local resolution-limit-free Potts model for community detection
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Community detection for correlation matrices
• Diffusion on networked systems is a question of time or structure
• Significant Scales in Community Structure
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Multi-scale community organization of the human structural connectome and its relationship with resting-state functional connectivity
• Bayesian stochastic blockmodeling
• Multiscale unfolding of real networks by geometric renormalization
• Deciphering Network Community Structure by Surprise
• Spectral methods for the detection of network community structure: a comparative analysis
• Surprise maximization reveals the community structure of complex networks
• Benchmark model to assess community structure in evolving networks
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Statistical inference of assortative community structures
• Assessing the structural heterogeneity of supercooled liquids through community inference
• The stability of a graph partition: A dynamics-based framework for community detection
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• Covariance, correlation matrix and the multi-scale community structure of networks
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Fast consensus clustering in complex networks
• A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
• Phase Transitions in Spectral Community Detection
• Machine-learning Iterative Calculation of Entropy for Physical Systems
• Hierarchical Graph Clustering using Node Pair Sampling
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Improving the performance of algorithms to find communities in networks
• Enhancing community detection by local structural information
• Identifying multi-scale communities in networks by asymptotic surprise
• Closed benchmarks for network community structure characterization
• Stochastic Replica Voting Machine Prediction of Stable Cubic and Double Perovskite Materials and Binary Alloys
• An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
• Overlapping modularity at the critical point of k-clique percolation
• The stability to instability transition in the structure of large scale networks
• Global disorder transition in the community structure of large-q Potts systems
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Multiple phases in modularity-based community detection
• Generalization of Clustering Agreements and Distances for Overlapping Clusters and Network Communities
• Automatic Segmentation of Fluorescence Lifetime Microscopy Images of Cells Using Multi-Resolution Community Detection
• Detecting the optimal number of communities in complex networks
• Link community detection through global optimization and the inverse resolution limit of partition density
• Emergence of coexisting percolating clusters in networks
• Community detection in weighted brain connectivity networks beyond the resolution limit
• Criterions for locally dense subgraphs
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Local multiresolution order in community detection
• Overlapping Communities in Social Networks
• Network Community Detection on Metric Space
• Evading Community Detection via Counterfactual Neighborhood Search
• Group fairness without demographics using social networks
• Detection of hidden structures on all scales in amorphous materials and complex physical systems: basic notions and applications to networks, lattice systems, and glasses
• Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm
• Considerations about multistep community detection
• The Stochastic Replica Approach to Machine Learning: Stability and Parameter Optimization
• Transforming complex network to the acyclic one
• The Importance of Being Negative: A serious treatment of non-trivial edges in brain functional connectome
• Community detection and tracking on networks from a data fusion perspective
• Fair treatment allocations in social networks
• GA Based Q-Attack on Community Detection