Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
arXiv:1908.04653 · doi:10.1137/19M1279812
Abstract
Modularity based community detection encompasses a number of widely used, efficient heuristics for identification of structure in networks. Recently, a belief propagation approach to modularity optimization provided a useful guide for identifying non-trivial structure in single-layer networks in a way that other optimization heuristics have not. In this paper, we extend modularity belief propagation to multilayer networks. As part of this development, we also directly incorporate a resolution parameter. We show that adjusting the resolution parameter affects the convergence properties of the algorithm and yields different community structures than the baseline. We compare our approach with a widely used community detection tool, GenLouvain, across a range of synthetic, multilayer benchmark networks, demonstrating that our method performs comparably to the state of the art. Finally, we demonstrate the practical advantages of the additional information provided by our tool by way of two real-world network examples. We show how the convergence properties of the algorithm can be used in selecting the appropriate resolution and coupling parameters and how the node-level marginals provide an interpretation for the strength of attachment to the identified communities. We have released our tool as a Python package for convenient use.
References in corpus (40)
- 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
- Multilayer Networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Analysis of weighted networks
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- The ground truth about metadata and community detection in networks
- Analysis of the structure of complex networks at different resolution levels
- Statistical physics of inference: Thresholds and algorithms
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
- Laplacian Dynamics and Multiscale Modular Structure in Networks
- Phase transition in the detection of modules in sparse networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Graph spectra and the detectability of community structure in networks
- Community Detection as an Inference Problem
- Nonparametric Bayesian inference of the microcanonical stochastic block model
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- The many facets of community detection in complex networks
- Clique Graphs and Overlapping Communities
- Significant Scales in Community Structure
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Clustering Network Layers With the Strata Multilayer Stochastic Block Model
- Consistent estimation of dynamic and multi-layer block models
- Enhanced detectability of community structure in multilayer networks through layer aggregation
- Communities and bottlenecks: Trees and treelike networks have high modularity
- Party Polarization in Congress: A Network Science Approach
- A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
- Post-processing partitions to identify domains of modularity optimization
- Comparative Study for Inference of Hidden Classes in Stochastic Block Models
- Weighted Community Detection and Data Clustering Using Message Passing
- Multiple phases in modularity-based community detection
- Case studies in network community detection