Online Network Topology Inference with Partial Connectivity Informatio
Online Network Topology Inference with Partial Connectivity Informatio
复制标题
使用部分连接信息进行在线网络拓扑推断
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
G. Mateos
中科院分区：
文献类型：
--
作者：
Rasoul Shafipour;G. Mateos
我们开发了从流节点观测和部分连通性信息进行在线拓扑推断的算法;即，如在链路预测问题中一样，关于存在或不存在一些边缘的先验知识是可用的。观测被建模为由未知网络上的局部扩散动力学产生的静止图信号。所述平稳性假设意味着观测的协方差矩阵和所谓的图移位算子（GSO）（这里是所寻找的图的邻接矩阵）的同时对角化。当GSO特征向量是完美地从合奏协方差，我们研究的结构的可行的邻接矩阵集和它的依赖于现有的连接信息。在实践中，人们只能形成一个经验估计的协方差矩阵，所以我们开发了一个交替的算法来找到一个稀疏的GSO给定其不完美的估计特征向量。当在流媒体设置中感测到新的扩散观测时，我们有效地更新特征向量并仅执行所提出的算法的一个（或几个）在线迭代，直到观察到新的数据。数值试验表明，新的批处理和在线算法在恢复现实世界的图形的有效性。
We develop algorithms for online topology inference from streaming nodal observations and partial connectivity information; i.e., a priori knowledge on the presence or absence of a few edges may be available as in the link prediction problem. The observations are modeled as stationary graph signals generated by local diffusion dynamics on the unknown network. Said stationarity assumption implies the simultaneous diagonalization of the observations' covariance matrix and the so-called graph shift operator (GSO), here the adjacency matrix of the sought graph. When the GSO eigenvectors are perfectly obtained from the ensemble covariance, we examine the structure of the feasible set of adjacency matrices and its dependency on the prior connectivity information available. In practice one can only form an empirical estimate of the covariance matrix, so we develop an alternating algorithm to find a sparse GSO given its imperfectly estimated eigenvectors. Upon sensing new diffused observations in the streaming setting, we efficiently update eigenvectors and perform only one (or a few) online iteration(s) of the proposed algorithm until a new datum is observed. Numerical tests showcase the effectiveness of the novel batch and online algorithms in recovering real-world graphs.
从流式固定图信号进行在线拓扑推断
DOI：
10.1109/dsw.2019.8755560
发表时间：
2019
期刊：
2019 IEEE Data Science Workshop (DSW
影响因子：
--
作者：
Shafipour, Rasoul;Hashemi, Abolfazl;Mateos, Gonzalo;Vikalo, Haris
通讯作者：
Vikalo, Haris
影响因子：
14.9
作者：
Mateos, Gonzalo;Segarra, Santiago;Ribeiro, Alejandro
通讯作者：
Ribeiro, Alejandro
影响因子：
2.8
作者：
Rasoul Shafipour;Santiago Segarra;A. Marques;G. Mateos
通讯作者：
Rasoul Shafipour;Santiago Segarra;A. Marques;G. Mateos