Papers › Community detection for binary graphical models in high dimension
Community detection for binary graphical models in high dimension
Julien Chevallier, Guilherme Ost
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Let N components be partitioned into two communities, denoted P_+ and P_-, possibly of different sizes. Assume that they are connected via a directed and weighted Erd\"os-R\'enyi (DWER) random graph with unknown parameter p ∈(0, 1). The weights assigned to the existing connections are of mean-field-type, scaling as N⁻¹. At each time \modif{step}, we observe the state of each component: either it sends some signal to its successors (in the directed graph) or remains silent otherwise. In this paper, we show that it is possible to find the communities P_+ and P_- based only on the activity of the N components observed over T time units. More specifically, we propose \modif{ two simple methods, an aggregated method and a spectral method, whose {\it misclassification rates} vanish as long as T ≫N (up to log terms). This condition is proved to be near-optimal in the minimax sense. Moreover, under the stronger condition T ≫N² (up to log terms), the aggregated method is shown to achieve {\it exact recovery} with probability tending to $1$. } Interestingly, these simple \modif{methods} do not require any prior knowledge of the other model parameters (e.g. the edge probability p). The key step in our analysis is to derive an asymptotic approximation of the 1-lagged covariance matrix associated to the states of the N components, as N diverges. This asymptotic approximation relies on the study of the behavior of the solutions of a \modif{Stein-type} matrix equation satisfied by the simultaneous (0-lagged) covariance matrix associated to the states of the components. This study is challenging, especially because the simultaneous covariance matrix is random since it depends on the underlying DWER random graph.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections