Blind identification of stochastic block models from dynamical observations
This addresses a blind identification challenge for network inference in fields like social science or biology, but it is incremental as it builds on existing spectral methods and random matrix theory.
The paper tackles the problem of recovering a stochastic block model (SBM) of a network without edge information, using only nodal observations from diffusive processes, and presents spectral algorithms that achieve high accuracy in partition recovery and parameter estimation.
We consider a blind identification problem in which we aim to recover a statistical model of a network without knowledge of the network's edges, but based solely on nodal observations of a certain process. More concretely, we focus on observations that consist of single snapshots taken from multiple trajectories of a diffusive process that evolves over the unknown network. We model the network as generated from an independent draw from a latent stochastic block model (SBM), and our goal is to infer both the partition of the nodes into blocks, as well as the parameters of this SBM. We discuss some non-identifiability issues related to this problem and present simple spectral algorithms that provably solve the partition recovery and parameter estimation problems with high accuracy. Our analysis relies on recent results in random matrix theory and covariance estimation, and associated concentration inequalities. We illustrate our results with several numerical experiments.