英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
不同社交网络和网络度量指标下的链路预测方法及其准确性
Fei Gao, Katarzyna Musial, Colin Cooper, and Sophia Tsoka
目前，我们正在经历基于社交的在线系统数量的快速增长。当我们在尝试分析在这些系统中收集到数据的可用性时，它带来了面临的新挑战。其中一个深入研究的主题是用户之间社交关系的预测。虽然已经做了很多努力来开发新的预测方法，但是现有方法尚未得到全面分析。在本文中，我们研究了网络指标和不同预测方法的准确性之间的相关性。我们选择了六个时间戳真实社交网络和十个最广泛使用的链路预测方法。实验结果表明，某些方法的性能和某些网络指标具有很强的相关性。我们设法区分了“预测友好”网络，其中大多数预测方法都能提供良好的性能，以及“预测不友好”的网络，其中大多数方法导致高预测误差。网络度量与预测方法预测准确性之间的相关性分析可以作为评估系统的基础，在这个系统中，基于网络特性，它将能够为给定网络推荐正确的预测方法。
- 简介
网络结构已经研究了很多年。最先这方面的研究可以追溯到1736年欧拉定义并解决了Konigsberg的七桥问题[1]。从那以后，长期以来，网络主要由数学家研究，这导致了一个非常突出的研究领域，如今已被称为图论。在复杂网络研究领域，并没有太多突破性的发展，直到20世纪60年代，鄂尔多斯-仁义随机图模型（ER模型）被引入[2,3]。这个是最简单的复杂网络模型。由于这个事实缺乏大量的现实世界数据，大多数工作都是在对网络结构中存在的现象进行理论分析（例如，相变）。
多年来，数据收集技术显着提高了我们存储大量异构网络数据的能力。在引入ER模型的过程中，社会学家在研究现实世界的人际关系方面也取得了进展[4,5]。Watts和Strogatz发表了一系列新研究，他们发表了一篇关于1998年小世界影响的论文[6]，并在一年后引入了Barabasi和Albert的无标度网络模型[7]。
随着数据库系统和Internet的可访问性不断增长，越来越多的真实网络数据集可用。有关人员及其活动的可用信息比以往任何时候都更加丰富和复杂。复杂的网络概念是各种现实世界网络的抽象形式，例如生物网络中的蛋白质相互作用网络，新陈代谢网络[8,9]，人类网络和疾病传播[10-13]，科学合作网络[14,15]和在线社交网络[16-19]。
复杂网络中的链路预测是一个热门的研究课题。大多数研究人员关注的是链接预测问题[20]，这对于解决实际问题非常有意义。通常，预测问题主要从两个角度进行研究：（i）网络结构和（ii）节点和连接的属性。结构是指组成网络的节点互连的方式。 它反映了有关网络拓扑的信息。数学家和物理学家已经在基于结构的预测领域取得了大部分进展。一些众所周知的基于结构的预测方法是Common Neighbor，Jaccards Index，Adamic / Adar Index，Katz等（有关这些方法的综述，请参阅[21]）。
从网络属性信息的角度研究了链路预测问题。属性信息是指节点特征的描述。这些信息难以直接在网络图中显示。例如，它可以通过标记节点来完成；例如，1表示代表女性的节点，2表示代表男性的节点。大多数基于属性的预测方法遵循机器学习方法;也就是说，他们使用基于分类的方法进行预测。广泛使用的方法包括决策树，支持向量机（SVM）和Naiuml;ve Bayes[22,23]。在[24-26]中，作者报告说，当使用机器学习方法时，链接预测的性能会提高。但是，这是使用并非始终可用的其他网络信息来完成的。我们想强调的是，在我们的工作中，我们对仅需要基本网络结构信息的方法感兴趣，因此我们在研究中不包括机器学习方法。
然而，尽管已经做了很多努力，但仍然没有可以提供令人满意的性能的显着预测方法。 因此，仍然存在需要解决的巨大研究差距。
1.1研究动机
在网络预测领域，已经在探索可以提供更好性能的新预测方法方面做了许多努力。然而，大多数研究中提出的方法仅改善了研究中使用的网络的预测结果。缺乏系统的研究能够揭示出这些方法在某些网络中是好的预测因子的原因，但在考虑其他网络时非常糟糕。
本文通过探索网络度量与不同方法的预测精度之间的相关性来解决这个问题。我们期望这种方法能够找出方法性能在不同网络上变化的原因。除了对预测方法有进一步的了解外，该研究对于开发新的预测方法也具有重要的理论基础。这可能与许多学科有关。预测方法可以帮助找到由于相互作用复杂性而可能不容易直接观察到的蛋白质之间的关系。例如，可以从现有的已知交互网络[27,28]推断出新的交互，这显示出比纯粹偶然预测更好的性能。在线市场定位也可能受益于已经应用于实际行业的网络预测。例如，谷歌和亚马逊向客户推荐他们可能感兴趣的潜在商品和服务，这是一种预测客户和产品之间联系的链接预测。
除此之外，分析时间序列方法中的链接预测问题可以帮助研究人员更好地理解网络的演化。已经做了很多工作来研究复杂网络的动态[29-31]。网络预测分析的实现有助于解释网络演化的机制。
1.2贡献
我们研究的主要贡献是我们将链路预测视为时间序列问题，并系统地分析了网络指标与方法准确性之间的相关性。此外，在我们的实验中，我们还发现，对于某些网络，大多数预测方法可以提供良好的性能，而对于其他一些网络，大多数方法相对无能为力。我们将它们分别命名为“预测友好”网络和“预测不友好”网络。
该论文的结构如下：第2节介绍了我们实验中使用的预测方法和性能指标。第3节介绍了如何选择和处理数据集。在第4节和第5节中，我们介绍了实验设计并提供了获得的结果。 我们在第6节中总结了这篇论文。
- 链路预测算法问题
链路预测问题已经被复杂网络社区的成员广泛研究。Liben-Nowell和Kleinberg通过以下方式正式确定了[20]中的链路预测问题。
设?（?，?）是?[?，?1]时间段内的网络，其中?代表节点集，?代表链接集。对于下一个时间段?（?1，?2），网络可能会发生变化。链路预测的重点是如何预测链路的演变，即?[?，?1]与?（?1，?2）的区别。
具有物理和数学背景的研究人员通常通过关注网络的拓扑信息来处理该问题。具有机器学习和数据挖掘背景的研究人员倾向于通过考虑节点的属性信息来解决问题。如图1所示，有三种类型的链路预测问题：我们可以考虑（i）仅添加到现有网络的链路，（ii）仅从现有结构中删除链接，以及（iii）同时添加和删除链接。
添加链接。添加链接（图1（a））意味着在下一个时间窗口中将在现有节点之间创建新链接。可以有一个或多个新创建的链接。
删除链接。删除链接（图1（b））意味着链接将在下一个时间窗口中消失。与添加新链接的情况类似，可以在一个时间步骤中删除一个或多个链接。
添加和删除链接。此问题是前面描述的两个问题的组合。它意味着从一个时间窗口到另一个时间窗口，可以预测链接的出现和消失（图1（c））。
在这项研究中，我们将只关注第一类链接预测问题，其目的仅在于预测链接的外观。主要原因是现实世界数据的绝大多数现有方法都集中在这个问题上，因此它意味着我们有足够的基础来进行相关分析。
图1 链路预测问题（a.添加链接 b.删除链接 c.添加和删除链接）
2.1预测方法
我们选择并简要介绍了在预测过程中使用网络拓扑信息的十种常用预测方法。在本节中，符号?，?表示节点，?表示网络中的节点数，?是平均度。Gamma;（?）和Gamma;（?）表示这些节点的邻居集，??和?y分别表示节点?和y的度数。
共同邻居。该方法基于以下假设：具有许多共同邻居的两个节点未来会连接。两个用户拥有的邻居越多，他们之间的关系出现的概率就越高。作为一种基本而直观的方法，通常使用Common Neighbors方法作为判断其他方法性能的基线[17,20,21,40]。[41]中介绍的这种方法的复杂性是?（??2）。
（1）
Jaccard的系数。Jaccard系数，也称为Jaccard指数或Jaccard相似系数，是用于比较样本集的相似性的统计量度。它通常表示为?（?，?），其中?和?代表网络中的两个不同节点。在链路预测中，节点的所有邻居被视为一组，并且通过计算和排序每个节点对的邻居集的相似性来完成预测。该方法基于Common Neighbors方法，其复杂度也是?（??2）。该方法的数学表达式如下[20]：
（2）
优先连接。由于假设高度节点更有可能获得新链接[42]，因此引入优先连接作为预测方法。该预测需要考虑一对中的两个节点的度。与共同邻居一样，这也是一种基本的预测方法，通常用作衡量其他预测方法性能的基线。该方法将计算网络内每对节点的相似度分值，而不仅仅是节点的邻居; 因此，优先连接的复杂性是?（?2?2）。这种方法可以表示为：
（3）
Adamic / Adar指数。它最初设计用于衡量个人主页之间的关系。如（4）所示，朋友?越多，分配的分数越低。因此，具有较少邻居的一对节点的共同邻居对于Adamic / Adar得分（AA）值的贡献大于具有大量关系的那个。在现实世界的社交网络中，它可以被解释如下：如果不相识的两人的共同好友有更多的朋友，那么比起他只有很少的朋友的情况，他不太可能将两个人介绍给彼此。根据个人主页和维基百科协作图，它在预测友谊方面表现出良好的效果，但在预测作者协作的实验中，它表现出较差的准确性预测[16]。这是另一种基于共同邻居的方法; 复杂性也是?（??2）。它的计算方法是：
（4）
其中?是节点?和节点y的公共邻居。
????beta;。该方法考虑了每对节点之间所有路径的长度[43]。根据（5），计算节点?和节点y之间的路径数量，长度为?（写为|），然后乘以因子beta;?。通过将路径长度为1到infin;的给定两个节点的所有结果相加，得到节点对（?，?）的预测分数。Katz是一种基于整个网络拓扑的预测方法，因此其计算比本节中的其他方法更复杂。复杂性主要由矩阵求逆算子决定，即?（?3）[41,44]：
（5）
如（5）所示，参数beta;用于调整不同长度的路径权重。当选择极小的beta;时，较长的路径与较短的路径相比对分数的贡献较小，因此其结果将接近共同邻居。
它是预测方法之一，正如它将在其他部分中所示，在许多实验中实现高预测精度。
余弦相似性。该方法的思想基于两个向量的点积。它通常用于比较文本挖掘中的文档[21]。在网络预测问题中，该方法表示为：
（6）
对于具有共同高度的每对节点，该方法将执行向量乘法，因此复杂度为?（??3）。
Sorenson指标。该指标[45]用于比较两个样本的相似性，最初用于分析植物社会学。该方法的复杂性为?（??2）。它被定义为：
（7）
大度节点有利指标。HPI用于分析新陈代谢网络，如[46]所示。该索引的属性是与集线器相邻的链路可能获得更高的相似性分值。该方法的复杂性为?（??2）。它表示为：
（8）
大度节点不利指标。以与HPI完全不同的方式使用集线器概念的方法是大度节点不利指标（HDI）。它为节点附近的链接提供了较低的分值。其复杂程度与大度节点有利指标相同为?（??2）。它被定义为：
（9）
LHN-Ⅰ指标。提出LHN-I [47]来量化网络中节点的相似性。它基于这样的概念：如果网络中的直接邻居本身相似，则两个节点是相似的。作为另一种基于常见邻居的方法，其复杂度为?（??2）。定义为：
（10）
本节中介绍的所有方法都遵循类似的方法。每种方法所需的输入是邻接矩阵，表示只有0和1的网络（当两个给定节点之间没有链接时为0，当两个给定节点之间存在链接时为1）。每种方法的输出是相似性矩阵，其中每个元素表示网络中一对节点的相似性得分，并且根据给定方法中使用的等式计算。
2.2预测结果指标
为了测量预测方法的性能，我们需要使用历史网络数据。链接预测是与时间相关的活动；因此，我们应该使用带时间戳的数据集，并根据时间戳将数据分成两组，??，?1（?，?1）作为预测方法的训练集，??1，?2（?，?2）作为未知未来用于测试的网络，其中 ? lt;?1lt;?2。这两个网络必须由同一组节点组成。由?表示的可能链路数是|?| *（|?| -1）/2。原则上，链接预测方法为每个不存在的链接（?-?1）提供相似性分值，对于大多数方法，得分越高，表明该链接在未来出现的可能性越高。通过对此分值列表进行排序并选择具有最高得分的顶部?链接来完成最终预测。
在我们的工作中，AUC用于量化预测方法的准确性。它是接收器工作特性曲线下的面积[4
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[19821]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
