Neighborhood and PageRank methods for pairwise link prediction
Neighborhood and PageRank methods for pairwise link prediction
复制标题
DOI：
10.1007/s13278-020-00671-6
复制
发表时间：
2020-07-30
影响因子：
2.8
通讯作者：
Gleich, David F.
中科院分区：
文献类型：
--
作者：
Nassar, Huda;Benson, Austin R.;Gleich, David F.
链接预测是网络科学中的一个常见问题，它跨越了许多学科。目标是预测新链接的出现或找到网络中丢失的链接。用于链路预测的典型方法使用网络的拓扑来预测一对节点之间最可能的未来或丢失的连接。然而，网络演化通常是由涉及多对节点的高阶结构介导的;例如，三个节点上的集团（也称为三角形）是社交网络结构的关键，但标准的链接预测框架不能直接预测这些结构。为了解决这一差距，在最近的工作中，我们提出了一个新的链接预测任务，称为“成对链接预测”，它直接针对新三角形的预测，其中一个任务是找出哪些节点最有可能形成具有给定边的三角形。我们在这篇手稿中扩展了这项工作，我们评估了各种自然扩展链接预测方法，包括邻域和基于PageRank的方法。与我们以前的工作的一个关键区别是边缘邻域的定义，这对经验性能有着惊人的影响。我们在各种网络上的实验表明，基于扩散的方法对所使用的图形类型不太敏感，并且其结果更加一致。我们还展示了我们的成对链接预测框架如何在标准链接预测评估的背景下获得更好的预测。
Link prediction is a common problem in network science that cuts across many disciplines. The goal is to forecast the appearance of new links or to find links missing in the network. Typical methods for link prediction use the topology of the network to predict the most likely future or missing connections between a pair of nodes. However, network evolution is often mediated by higher-order structures involving more than pairs of nodes; for example, cliques on three nodes (also called triangles) are key to the structure of social networks, but the standard link prediction framework does not directly predict these structures. To address this gap, in recent work, we propose a new link prediction task called "pairwise link prediction" that directly targets the prediction of new triangles, where one is tasked with finding which nodes are most likely to form a triangle with a given edge. We extend this work in this manuscript, and we evaluate a variety of natural extensions to link prediction methods including neighborhood and PageRank-based methods. A key difference from our previous work is the definition of the neighborhood of an edge, which has a surprisingly large impact on the empirical performance. Our experiments on a variety of networks show that diffusion-based methods are less sensitive to the type of graphs used and more consistent in their results. We also show how our pairwise link prediction framework can be used to get better predictions within the context of standard link prediction evaluation.