Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
arXiv:1811.04209 · doi:10.1103/PhysRevE.99.042310
Abstract
We study the problem of identifying macroscopic structures in networks, characterizing the impact of introducing link directions on the detectability phase transition. To this end, building on the stochastic block model, we construct a class of hardly detectable directed networks. We find closed form solutions by using belief propagation method showing how the transition line depends on the assortativity and the asymmetry of the network. Finally, we numerically identify the existence of a hard phase for detection close to the transition point.
arXiv comment9 pages, 7 figures
References in corpus (17)
- Community detection in graphs
- Comparing community structure identification
- The Bethe lattice spin glass revisited
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Clustering and Community Detection in Directed Networks: A Survey
- The ground truth about metadata and community detection in networks
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Efficiently inferring community structure in bipartite networks
- Reconstruction on trees and spin glass transition
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- A ferromagnet with a glass transition
- The Nishimori line and Bayesian Statistics
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- (Un)detectable cluster structure in sparse networks
- Universality of the stochastic block model
- Weighted Community Detection and Data Clustering Using Message Passing