Community Detection from Low-Rank Excitations of a Graph Filter
Community Detection from Low-Rank Excitations of a Graph Filter
复制标题
从图滤波器的低阶激励进行社区检测
DOI：
10.1109/icassp.2018.8462239
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
A. Jadbabaie
中科院分区：
文献类型：
--
作者：
Hoi;Santiago Segarra;A. Ozdaglar;A. Scaglione;A. Jadbabaie
本文考虑了从由低秩信号激励的未知图滤波器的噪声输出推断图的拓扑的问题。受这种低秩结构的限制，我们专注于解决社区发现问题，其目的是将未知图的节点集划分为具有高边密度的子集。我们建议通过在低秩输出协方差矩阵上应用谱聚类来检测社区。为了分析性能，我们证明低秩协方差产生了未知图的特征向量的草图。重要的是，我们根据所涉及的图滤波器的光谱特征，提供了该草图过程引入的误差的理论界限。最后，我们的理论发现通过数值实验得到验证。
This paper considers the problem of inferring the topology of a graph from noisy outputs of an unknown graph filter excited by low-rank signals. Limited by this low-rank structure, we focus on solving the community detection problem, whose aim is to partition the node set of the unknown graph into subsets with high edge densities. We propose to detect the communities by applying spectral clustering on the low-rank output covariance matrix. To analyze the performance, we show that the low-rank covariance yields a sketch of the eigenvectors of the unknown graph. Importantly, we provide theoretical bounds on the error introduced by this sketching procedure based on spectral features of the graph filter involved. Finally, our theoretical findings are validated via numerical experiments.