Blind identification of stochastic block models from dynamical observations

Abstract

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.

arXiv comment33 pages; 4 figures

References in corpus (18)

• Discovering governing equations from data: Sparse identification of nonlinear dynamical systems
• Cooperative Game Theory Approaches for Network Partitioning
• Stochastic blockmodels and community structure in networks
• Social Structure of Facebook Networks
• Random walks and diffusion on networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• The ground truth about metadata and community detection in networks
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• Consistency of spectral clustering in stochastic block models
• Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems
• Revealing networks from dynamics: an introduction
• Causal Network Inference via Group Sparse Regularization
• Network reconstruction and community detection from dynamics
• Revealing physical interaction networks from statistics of collective dynamics
• Centrality measures for graphons: Accounting for uncertainty in networks
• On the sample covariance matrix estimator of reduced effective rank population matrices, with applications to fPCA
• Community detection in networks without observing edges

Cited by in corpus (8)

• Exact Blind Community Detection from Signals on Multiple Graphs
• Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis
• Blind Inference of Eigenvector Centrality Rankings
• Mixed Membership Graph Clustering via Systematic Edge Query
• Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation
• Blind Extraction of Equitable Partitions from Graph Signals
• Sparse Partial Least Squares for Coarse Noisy Graph Alignment
• Untrained Graph Neural Networks for Denoising