Exact Blind Community Detection from Signals on Multiple Graphs

Abstract

Networks and data supported on graphs have become ubiquitous in the sciences and engineering. This paper studies the 'blind' community detection problem, where we seek to infer the community structure of a graph model given the observation of independent graph signals on a set of nodes whose connections are unknown. We model each observation as filtered white noise, where the underlying network structure varies with every observation. These varying network structures are modeled as independent realizations of a latent planted partition model (PPM), justifying our assumption of a constant underlying community structure over all observations. Under certain conditions on the graph filter and PPM parameters, we propose algorithms for determining (i) the number of latent communities and (ii) the associated partitions of the PPM. We then prove statistical guarantees in the asymptotic and non-asymptotic sampling cases. Numerical experiments on real and synthetic data demonstrate the efficacy of our algorithms.

13 pages, 3 figures

References in corpus (5)

• Modularity and community structure in networks
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Covariance regularization by thresholding
• Mixture models and exploratory analysis in networks

Cited by in corpus (6)

• Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis
• Blind Inference of Eigenvector Centrality Rankings
• Blind Extraction of Equitable Partitions from Graph Signals
• Community Structure Recovery and Interaction Probability Estimation for Gossip Opinion Dynamics
• Sparse Partial Least Squares for Coarse Noisy Graph Alignment
• Community Detection for Gossip Dynamics with Stubborn Agents