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 are generated independently at each time step. In this setting (which is a special case of several existing models), we are able to derive the detectability threshold exactly, as a function of the rate of change and the strength of the communities. Below this threshold, we claim that no algorithm can identify the communities better than chance. We then give two algorithms that are optimal in the sense that they succeed all the way down to this limit. The first uses belief propagation (BP), which gives asymptotically optimal accuracy, and the second is a fast spectral clustering algorithm, based on linearizing the BP equations. We verify our analytic and algorithmic results via numerical simulation, and close with a brief discussion of extensions and open questions.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Community Detection with Node Attributes and its Generalization
Community detection algorithms are fundamental tools to understand organizational principles in social networks. With the increasing power of social media platforms, when detecting communities there are two possi- ble so…
Community DetectionCommunity 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 ModelGraph energy as a measure of community detectability in networks
A key challenge in network science is the detection of communities, which are sets of nodes in a network that are densely connected internally but sparsely connected to the rest of the network. A fundamental result in co…
Community DetectionAlgorithmic 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 inf…
modelStochastic Block ModelPhase Transitions in Community Detection: A Solvable Toy Model
Recently, it was shown that there is a phase transition in the community detection problem. This transition was first computed using the cavity method, and has been proved rigorously in the case of $q=2$ groups. However,…
Community Detection