A quest to unravel the metric structure behind perturbed networks
A quest to unravel the metric structure behind perturbed networks
复制标题
寻求解开扰动网络背后的度量结构
DOI：
10.4230/lipics.socg.2017.53
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Yusu Wang
中科院分区：
文献类型：
--
作者：
S. Parthasarathy;David J Sivakoff;Minghao Tian;Yusu Wang
图形和网络数据在科学和应用领域的广泛范围内无处不在。通常在实践中，输入图可以被认为是（潜在地）
连续）隐藏域或过程。随后的分析、处理和推断是在这个观察到的图上进行的。在本文中，我们主张观察图通常是隐藏域的某些离散化1-骨架的噪声版本，具体来说，我们将考虑以下自然网络模型：我们假设存在真图G^*，它是从隐藏域X采样的点的某种邻近图;而观察图G是G^* 的Erdos-Renyi型扰动版本。
我们的网络模型与Watts和Strogatz最初提出的著名的小世界网络模型有关，并略有推广。然而，我们要回答的主要问题与通常的网络模型研究（通常侧重于描述/预测真实网络的行为和属性）是正交的。具体来说，我们的目标是从观察图G中恢复G^* 的度量结构（这反映了隐藏空间X的度量结构，我们将在下文中展示）。我们的主要结果是，基于Jaccard指数的简单过滤过程可以在我们的网络模型下在乘法因子2内恢复此度量。我们的工作使一个步骤的一般性问题推断结构的隐藏空间从其观察到的嘈杂的图形表示。此外，我们的研究结果也提供了一个理论上的理解Jaccard指数为基础的去噪方法。
Graphs and network data are ubiquitous across a wide spectrum of scientific and application domains. Often in practice, an input graph can be considered as an observed snapshot of a (potentially
continuous) hidden domain or process. Subsequent analysis, processing, and inferences are then performed on this observed graph. In this paper we advocate the perspective that an observed graph is often a noisy version of some discretized 1-skeleton of a hidden domain, and specifically we will consider the following natural network model: We assume that there is a true graph G^* which is a certain proximity graph for points sampled from a hidden domain X; while the observed graph G is an Erdos-Renyi type perturbed version of G^*.
Our network model is related to, and slightly generalizes, the much-celebrated small-world network model originally proposed by Watts and Strogatz. However, the main question we aim to answer is orthogonal to the usual studies of network models (which often focuses on characterizing / predicting behaviors and properties of real-world networks). Specifically, we aim to recover the metric structure of G^* (which reflects that of the hidden space X as we will show) from the observed graph G. Our main result is that a simple filtering process based on the Jaccard index can recover this metric within a multiplicative factor of 2 under our network model. Our work makes one step towards the general question of inferring structure of a hidden space from its observed noisy graph representation. In addition, our results also provide a theoretical understanding for Jaccard-Index-based denoising approaches.