Algorithmic detectability threshold of the stochastic block model
The assumption that the values of model parameters are known or correctly learned, i.e., the Nishimori condition, is one of the requirements for the detectability analysis of the stochastic block model in statistical inference. In practice, however, there is no example demonstrating that we can know the model parameters beforehand, and there is no guarantee that the model parameters can be learned accurately. In this study, we consider the expectation--maximization (EM) algorithm with belief propagation (BP) and derive its algorithmic detectability threshold. Our analysis is not restricted to the community structure, but includes general modular structures. Because the algorithm cannot always learn the planted model parameters correctly, the algorithmic detectability threshold is qualitatively different from the one with the Nishimori condition.
Code (0)
등록된 구현이 없습니다.
Tasks
modelStochastic Block ModelSimilar Papers 제목 키워드 기반
Detectability thresholds and optimal algorithms for community structure in dynamic networks
We study the fundamental limits on learning latent community structure in dynamic networks. Specifically, we study dynamic stochastic block models where nodes change their community membership over time, but where edges …
ClusteringAlgorithmic infeasibility of community detection in higher-order networks
In principle, higher-order networks that have multiple edge types are more informative than their lower-order counterparts. In practice, however, excessively rich information may be algorithmically infeasible to extract.…
Community DetectionDisentangling group and link persistence in Dynamic Stochastic Block models
We study the inference of a model of dynamic networks in which both communities and links keep memory of previous network states. By considering maximum likelihood inference from single snapshot observations of the netwo…
Community DetectionNeural-prior stochastic block model
The stochastic block model (SBM) is widely studied as a benchmark for graph clustering aka community detection. In practice, graph data often come with node attributes that bear additional information about the communiti…
Community DetectionGraph ClusteringmodelStochastic Block ModelCommunity detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
This article considers the problem of community detection in sparse dynamical graphs in which the community structure evolves over time. A fast spectral algorithm based on an extension of the Bethe-Hessian matrix is prop…
Community DetectionStochastic Block Model