Blind Community Detection from Low-rank Excitations of a Graph Filter
arXiv:1809.01485
Abstract
This paper considers a new framework to detect communities in a graph from the observation of signals at its nodes. We model the observed signals as noisy outputs of an unknown network process, represented as a graph filter that is excited by a set of unknown low-rank inputs/excitations. Application scenarios of this model include diffusion dynamics, pricing experiments, and opinion dynamics. Rather than learning the precise parameters of the graph itself, we aim at retrieving the community structure directly. The paper shows that communities can be detected by applying a spectral method to the covariance matrix of graph signals. Our analysis indicates that the community detection performance depends on a `low-pass' property of the graph filter. We also show that the performance can be improved via a low-rank matrix plus sparse decomposition method when the latent parameter vectors are known. Numerical experiments demonstrate that our approach is effective.
arXiv commentSingle column format, 32 pages, 9 figures
References in corpus (18)
- Community detection in graphs
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Discrete Signal Processing on Graphs
- Social Structure of Facebook Networks
- Discrete Signal Processing on Graphs: Sampling Theory
- Sampling of graph signals with successive local aggregations
- Learning with Structured Sparsity
- Autoregressive Moving Average Graph Filtering
- Kernel-based Reconstruction of Graph Signals
- Reconstruction of Graph Signals through Percolation from Seeding Nodes
- Kernel-Based Structural Equation Models for Topology Identification of Directed Networks
- Blind Identification of Graph Filters
- Active Sensing of Social Networks
- Compressive Spectral Clustering
- A variational approach to stable principal component pursuit
- Spectral Clustering via the Power Method -- Provably
- Graph Signal Processing: Overview, Challenges and Applications
- RIDS: Robust Identification of Sparse Gene Regulatory Networks from Perturbation Experiments