Blind Community Detection From Low-Rank Excitations of a Graph Filter
- 20 December 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 68 (1053587X), 436-451
- https://doi.org/10.1109/tsp.2019.2961296
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 an intrinsic ‘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 results demonstrate that our approach is effective.Keywords
Funding Information
- NSF (1714672)
- MIT IDSS Seed Fund
- Spanish MINECO (TEC2013-41604-R)
This publication has 43 references indexed in Scilit:
- Inference of Gene Regulatory Networks with Sparse Structural Equation Models Exploiting Genetic PerturbationsPLoS Computational Biology, 2013
- A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable RegularizersStatistical Science, 2012
- Wisdom of crowds for robust gene network inferenceNature Methods, 2012
- Social structure of Facebook networksPhysica A: Statistical Mechanics and its Applications, 2011
- User-Friendly Tail Bounds for Sums of Random MatricesFoundations of Computational Mathematics, 2011
- Community detection in graphsPhysics Reports, 2009
- Sparse inverse covariance estimation with the graphical lassoBiostatistics, 2007
- Stochastic blockmodels: First stepsSocial Networks, 1983
- Reaching a ConsensusJournal of the American Statistical Association, 1974
- Perturbation bounds in connection with singular value decompositionBIT Numerical Mathematics, 1972