Link Prediction in Networks with Core-Fringe Data
Link Prediction in Networks with Core-Fringe Data
复制标题
DOI：
10.1145/3308558.3313626
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Austin R. Benson;J. Kleinberg
中科院分区：
文献类型：
--
作者：
Austin R. Benson;J. Kleinberg
数据收集通常涉及对更大系统的部分测量。收集网络数据时出现了一个常见的例子：我们通常通过记录一小部分核心节点之间的所有交互来获得网络数据集，从而最终得到由这些核心节点以及潜在地更大的具有到核心的链接的边缘节点集组成的网络的测量结果。鉴于这种收集网络数据的过程无处不在，理解这种“核心-边缘”结构的作用至关重要。在这里，我们研究边缘节点的包含如何影响网络链接预测的标准任务。最初，人们可能认为包含任何附加数据是有用的，因此包含所有可用的条纹节点应该是有益的。然而，我们发现这不是真的；事实上，用于预测的条纹节点的值有很大的可变性。一旦选择了算法，在某些数据集中，包括来自条纹的任何额外数据实际上会损害预测性能；在其他数据集中，在预测性能饱和甚至下降之前，包括一定量的条纹信息是有用的；在其他情况下，包括整个条纹将导致最佳性能。虽然这样的变化可能看起来令人惊讶，但我们证明了这些行为是通过简单的随机图模型来展示的。
Data collection often involves the partial measurement of a larger system. A common example arises in collecting network data: we often obtain network datasets by recording all of the interactions among a small set of core nodes, so that we end up with a measurement of the network consisting of these core nodes along with a potentially much larger set of fringe nodes that have links to the core. Given the ubiquity of this process for assembling network data, it is crucial to understand the role of such a “core-fringe” structure. Here we study how the inclusion of fringe nodes affects the standard task of network link prediction. One might initially think the inclusion of any additional data is useful, and hence that it should be beneficial to include all fringe nodes that are available. However, we find that this is not true; in fact, there is substantial variability in the value of the fringe nodes for prediction. Once an algorithm is selected, in some datasets, including any additional data from the fringe can actually hurt prediction performance; in other datasets, including some amount of fringe information is useful before prediction performance saturates or even declines; and in further cases, including the entire fringe leads to the best performance. While such variety might seem surprising, we show that these behaviors are exhibited by simple random graph models.