Local multiresolution order in community detection
arXiv:1208.5052 · doi:10.1088/1742-5468/2015/01/P01001
Abstract
Community detection algorithms attempt to find the best clusters of nodes in an arbitrary complex network. Multi-scale ("multiresolution") community detection extends the problem to identify the best network scale(s) for these clusters. The latter task is generally accomplished by analyzing community stability simultaneously for all clusters in the network. In the current work, we extend this general approach to define local multiresolution methods, which enable the extraction of well-defined local communities even if the global community structure is vaguely defined in an average sense. Toward this end, we propose measures analogous to variation of information and normalized mutual information that are used to quantitatively identify the best resolution(s) at the community level based on correlations between clusters in independently-solved systems. We demonstrate our method on two constructed networks as well as a real network and draw inferences about local community strength. Our approach is independent of the applied community detection algorithm save for the inherent requirement that the method be able to identify communities across different network scales, with appropriate changes to account for how different resolutions are evaluated or defined in a particular community detection method. It should, in principle, easily adapt to alternative community comparison measures.
arXiv comment19 pages, 11 figures
References in corpus (57)
- Finding and evaluating community structure in networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- Cooperative Game Theory Approaches for Network Partitioning
- 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
- Defining and identifying communities in networks
- Community detection algorithms: a comparative analysis
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Hierarchical structure and the prediction of missing links in networks
- Hierarchical Organization in Complex Networks
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Link communities reveal multiscale complexity in networks
- Detecting the overlapping and hierarchical community structure of complex networks
- Finding statistically significant communities in networks
- The performance of modularity maximization in practical contexts
- Finding local community structure in networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Detect overlapping and hierarchical community structure in networks
- Detecting fuzzy community structures in complex networks with a Potts model
- Mixture models and exploratory analysis in networks
- Extracting the hierarchical organization of complex systems
- Limits of modularity maximization in community detection
- Community detection in networks with positive and negative links
- Analysis of the structure of complex networks at different resolution levels
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Phase transition in the detection of modules in sparse networks
- An efficient and principled method for detecting communities in networks
- Narrow scope for resolution-limit-free community detection
- Detecting network communities by propagating labels under constraints
- Graph spectra and the detectability of community structure in networks
- A Bayesian Approach to Network Modularity
- A Local Method for Detecting Communities
- Characterizing the community structure of complex networks
- Hierarchy measure for complex networks
- Multiresolution community detection for megascale networks by information-based replica correlations
- Community Detection as an Inference Problem
- Local resolution-limit-free Potts model for community detection
- Limited resolution in complex network community detection with Potts model approach
- Community extraction for social networks
- Local modularity measure for network clusterizations
- Hierarchy Measures in Complex Networks
- Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
- Orbital order in classical models of transition-metal compounds
- Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
- 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
- Limitation of multi-resolution methods in community detection
- Community Detection in Complex Networks by Dynamical Simplex Evolution
- A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
- Networks in Motion
- Finding mesoscopic communities in sparse networks
- The stability to instability transition in the structure of large scale networks
- Global disorder transition in the community structure of large-q Potts systems
Cited by in corpus (5)
- Statistical inference of assortative community structures
- Assessing the structural heterogeneity of supercooled liquids through community inference
- Community Detection in Complex Networks Using Density-based Clustering Algorithm
- Enhancing community detection by local structural information
- Inference of hidden structures in complex physical systems by multi-scale clustering