Found Graph Data and Planted Vertex Covers
Found Graph Data and Planted Vertex Covers
复制标题
DOI：
--
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Austin R. Benson;J. Kleinberg
中科院分区：
文献类型：
--
作者：
Austin R. Benson;J. Kleinberg
记录网络数据的一种典型方法是测量一组指定核心节点之间的所有交互；这将生成一个包含该核心以及可能更大的边缘节点集的图，这些边缘节点具有到核心的链接。然而，条纹中对节点之间的相互作用不被这个过程记录，因此不存在于结果图数据中。例如，电话服务提供商可能只拥有至少有一个参与者是客户的电话记录；这可以包括客户和非客户之间的呼叫，但不包括非客户对之间的呼叫。了解哪些节点属于核心是一个重要的元数据，对于解释网络数据集至关重要。但是在许多情况下，这些元数据是不可用的，要么是因为由于数据来源困难而丢失，要么是因为网络由在反监视等设置中获得的发现数据组成。这就引出了一个自然的算法问题，即核心集的恢复问题。由于核心集形成了图的顶点覆盖，我们本质上有一个种植的顶点覆盖问题，但是有一个任意的底层图。我们开发了一个理论框架来分析这种种植顶点覆盖问题，基于固定参数可追溯性理论的结果，以及恢复核心的算法。我们的算法快速，易于实现，并且在各种实际数据集上优于基于网络核心-外围结构的几种方法。
A typical way in which network data is recorded is to measure all the interactions among a specified set of core nodes; this produces a graph containing this core together with a potentially larger set of fringe nodes that have links to the core. Interactions between pairs of nodes in the fringe, however, are not recorded by this process, and hence not present in the resulting graph data. For example, a phone service provider may only have records of calls in which at least one of the participants is a customer; this can include calls between a customer and a non-customer, but not between pairs of non-customers. Knowledge of which nodes belong to the core is an important piece of metadata that is crucial for interpreting the network dataset. But in many cases, this metadata is not available, either because it has been lost due to difficulties in data provenance, or because the network consists of found data obtained in settings such as counter-surveillance. This leads to a natural algorithmic problem, namely the recovery of the core set. Since the core set forms a vertex cover of the graph, we essentially have a planted vertex cover problem, but with an arbitrary underlying graph. We develop a theoretical framework for analyzing this planted vertex cover problem, based on results in the theory of fixed-parameter tractability, together with algorithms for recovering the core. Our algorithms are fast, simple to implement, and out-perform several methods based on network core-periphery structure on various real-world datasets.