Community Detection and Improved Detectability in Multiplex Networks
arXiv:1909.10477 · doi:10.1109/TNSE.2019.2949036
Abstract
We investigate the widely encountered problem of detecting communities in multiplex networks, such as social networks, with an unknown arbitrary heterogeneous structure. To improve detectability, we propose a generative model that leverages the multiplicity of a single community in multiple layers, with no prior assumption on the relation of communities among different layers. Our model relies on a novel idea of incorporating a large set of generic localized community label constraints across the layers, in conjunction with the celebrated Stochastic Block Model (SBM) in each layer. Accordingly, we build a probabilistic graphical model over the entire multiplex network by treating the constraints as Bayesian priors. We mathematically prove that these constraints/priors promote existence of identical communities across layers without introducing further correlation between individual communities. The constraints are further tailored to render a sparse graphical model and the numerically efficient Belief Propagation algorithm is subsequently employed. We further demonstrate by numerical experiments that in the presence of consistent communities between different layers, consistent communities are matched, and the detectability is improved over a single layer. We compare our model with a "correlated model" which exploits the prior knowledge of community correlation between layers. Similar detectability improvement is obtained under such a correlation, even though our model relies on much milder assumptions than the correlated model. Our model even shows a better detection performance over a certain correlation and signal to noise ratio (SNR) range. In the absence of community correlation, the correlation model naturally fails, while ours maintains its performance.
References in corpus (24)
- Uncovering the overlapping community structure of complex networks in nature and society
- The structure and dynamics of multilayer networks
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Stochastic blockmodels and community structure in networks
- Quantifying social group evolution
- Multirelational Organization of Large-scale Social Networks in an Online World
- Mathematical Formulation of Multi-Layer Networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Layer aggregation and reducibility of multilayer interconnected networks
- Emergence of network features from multiplexity
- Community Detection in Networks with Node Attributes
- Phase transition in the detection of modules in sparse networks
- Structure and inference in annotated networks
- Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
- Community detection, link prediction, and layer interdependence in multilayer networks
- Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Clustering Network Layers With the Strata Multilayer Stochastic Block Model
- Evolution of network architecture in a granular material under compression
- Multilayer stochastic block models reveal the multilayer structure of complex networks
- Enhanced detectability of community structure in multilayer networks through layer aggregation
- Comparison of Communities Detection Algorithms for Multiplex
- Community detection in networks with unequal groups
- Detectability thresholds of general modular graphs