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.

arXiv comment13 pages, 3 figures

References in corpus (20)

• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• High-dimensional graphs and variable selection with the Lasso
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Covariance regularization by thresholding
• Random walks and diffusion on networks
• Mixture models and exploratory analysis in networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• An efficient and principled method for detecting communities in networks
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Kernel-Based Structural Equation Models for Topology Identification of Directed Networks
• Blind Identification of Graph Filters
• Active Sensing of Social Networks
• On the sample covariance matrix estimator of reduced effective rank population matrices, with applications to fPCA
• Network Inference from Consensus Dynamics with Unknown Parameters
• Network Inference from Consensus Dynamics
• Blind identification of stochastic block models from dynamical observations
• Spectral partitioning of time-varying networks with unobserved edges

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