Multiple phases in modularity-based community detection
arXiv:1506.04506 · doi:10.1103/PhysRevE.92.042804
Abstract
Detecting communities in a network, based only on the adjacency matrix, is a problem of interest to several scientific disciplines. Recently, Zhang and Moore have introduced an algorithm in [P. Zhang and C. Moore, Proceedings of the National Academy of Sciences 111, 18144 (2014)], called mod-bp, that avoids overfitting the data by optimizing a weighted average of modularity (a popular goodness-of-fit measure in community detection) and entropy (i.e. number of configurations with a given modularity). The adjustment of the relative weight, the "temperature" of the model, is crucial for getting a correct result from mod-bp. In this work we study the many phase transitions that mod-bp may undergo by changing the two parameters of the algorithm: the temperature and the maximum number of groups . We introduce a new set of order parameters that allow to determine the actual number of groups , and we observe on both synthetic and real networks the existence of phases with any , which were unknown before. We discuss how to interpret the results of mod-bp and how to make the optimal choice for the problem of detecting significant communities.
arXiv comment8 pages, 7 figures
References in corpus (22)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Resolution limit in community detection
- Statistical Mechanics of Community Detection
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Community detection in complex networks using Extremal Optimization
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Consensus clustering in complex networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Extracting the hierarchical organization of complex systems
- Phase transition in the detection of modules in sparse networks
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Multiresolution community detection for megascale networks by information-based replica correlations
- Community detection in networks: Structural communities versus ground truth
- Community Detection as an Inference Problem
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- Statistical significance of communities in networks
- Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
- Global disorder transition in the community structure of large-q Potts systems