Compressive Network Analysis.
Compressive Network Analysis.
复制标题
压缩网络分析
DOI：
10.1109/tac.2014.2351712
复制
发表时间：
2014-11
影响因子：
6.8
通讯作者：
Guibas L
中科院分区：
文献类型：
--
作者：
Jiang X;Yao Y;Liu H;Guibas L
现代数据采集通常会产生大量网络数据。尽管已经提出了许多方法和模型来分析此类数据，但网络数据的研究在很大程度上与统计学习和信号处理的经典理论脱节。在本文中，我们提出了一种用于建模网络数据的新框架，它连接了两个看似不同的领域：网络数据分析和压缩感知。从非参数的角度来看，我们使用大字典对观察到的网络进行建模。特别是，我们考虑了网络派系检测问题，并展示了我们的公式与新代数工具（即同质空间中的随机基追寻）之间的联系。这种连接使我们能够识别派系检测问题的严格恢复条件。尽管本文主要是概念性的，但我们还开发了用于解决经验问题的实用近似算法，并证明了它们在现实世界数据集上的有用性。
Modern data acquisition routinely produces massive amounts of network data. Though many methods and models have been proposed to analyze such data, the research of network data is largely disconnected with the classical theory of statistical learning and signal processing. In this paper, we present a new framework for modeling network data, which connects two seemingly different areas: network data analysis and compressed sensing. From a nonparametric perspective, we model an observed network using a large dictionary. In particular, we consider the network clique detection problem and show connections between our formulation with a new algebraic tool, namely Randon basis pursuit in homogeneous spaces. Such a connection allows us to identify rigorous recovery conditions for clique detection problems. Though this paper is mainly conceptual, we also develop practical approximation algorithms for solving empirical problems and demonstrate their usefulness on real-world datasets.