使用基于时间的关系加权标准来改善社交网络中的链接预测

使用基于时间的关系加权标准来改善社交网络中的链接预测

关键词：链接预测，社交网络，加权图。

 

摘要：近年来，对复杂网络中链路预测（LP）问题的研究引起了相当多的关注。此问题试图预测网络中两个未互连节点之间出现未来关联的可能性。已经开发了各种方法来解决这个问题。其中一些计算连接节点之间的兼容性程度（链接强度），并应用非连接节点之间的相似性度量以识别潜在链接。然而，尽管时间数据对LP问题的重要性得到公认，但很少有举措研究使用这种信息来表示链接强度。在本文中，我们提出了一个权重标准，它将交互频率和关于它们的时间信息结合起来，以便定义连接节点对之间的链接强度。我们在10个共同作者网络中使用传统加权相似性度量的实验结果证实了我们的假设，即基于时间信息的加权链接事实上可以改进链接预测。拟议的标准制定，实验程序和所进行的实验结果进行了详细讨论。

1. 引言

近年来，社会网络分析受到了科学界和工业界的高度关注（Wang et al。，2015）。 它试图了解大规模社交网络的结构如何演变。 例如，预测未来一对节点是否会连接是一个重要的网络分析任务，称为链路预测（LP）问题（Liben-Nowell和Kleinberg，2007）。 已经开发了各种方法来预测社会网络中的链接（Adamic和Adar，2003）（Barabasi等，2001）（Choudhary等，2013），（Liben-Nowell和Kleinberg，2007）（Munasinghe和Ichise，2012年 ），（Valverde-Rebaza等，2015），（Lu¨和Zhou，2010），（Murata和Moriyasu，2007），（Soares和Prudencio，2011），（Zhu and Xia，2016）。 根据（王等人，2015），这些方法分为两种方法：

（1）监督 - 这种方法将原始图转换为二元分类问题，并使用决策树和神经网络等学习算法来构建分类模型（Hasan等，2006）。

（2）无监督 - 来自这种方法的方法基于相似性度量，该度量计算分数以表达在非连接节点对之间的某种兼容性程度（例如，同源性，关系，分离程度等）。然后获得一个按照得分降序排列的列表，并且来自列表顶部的对的节点更可能连接（Liben-Nowell和Kleinberg，2007）。公共的邻居（CN）和Adamic-Adar索引（AA）的数量是在计分计算中经常使用的基于拓扑的相似性度量的典型示例（Wang et al。，2015）。

节点连接时也可以考虑兼容程度。在这种情况下，它被称为节点之间的链接强度，并由分配给表示相应连接的边的数字权重组成。链路强度值越高（低或越低），表示节点强烈（或弱）链接。从无监督方法到LP问题的大多数举措都没有考虑到链接强度。然而，这些信息可能被用来为链接预测提供有用的见解。例如，与其共同邻居强联系的两个非联结节点比联结其共同邻居的联结更可能连接。

很少有关于LP问题的无监督方法的研究评估了连接节点之间链接强度的使用（Murata and Moriyasu，2007），（Lu¨和Zhou，2010）（Soares和Prudencio，2011）（Zhao et al。， （Taha，2007），（Zhu and Xia，2016），（Dunlavy et al。，2011）。他们采用了一些加权标准来计算链接强度3。在几乎所有这些标准中，所采用的权重标准是节点（Fi）（村田和Moriyasu，2007），（Lu和Zhou，2010），（Soares和Prudencio，2011），夏，2016）。基于Fi，频繁交互的节点之间的链接强度高于偶尔连接的链接强度。虽然有趣，但这个标准并没有考虑到互动发生的时间。因此，新旧交互在体重定义上具有相同的影响力。这一特征并不能满足弱关系的社会理论（Granovetter，1973）。根据这种理论，最近的相互作用倾向于刺激网络中新的相互作用的发生。因此，最近的连接应该在链路强度计算中有更高的影响，并因此在链路预测中有更大的影响。

我们的假设是基于交互频率和时间信息的组合加权链接可以改善链接预测。 为了说明这一点，在本文中，我们提出了一个权重标准（称为FTi），它将交互频率和关于它们的时间信息相结合，以提高链接强度的质量，从而提高社交网络中LP的性能。 在实验中，我们运行FTi和Fi来分析每个网络的权重。 此后，我们比较了WCN和WAA应用于所有加权网络的性能。 两种指标在应用于FTi标准加权的网络时表现出更好的性能，证实了我们的假设。

该文本包含其他五个部分。 第2节介绍一些关于链接预测的背景知识。 在第3节中，我们描述了建议的加权标准。 关于实验结果的细节在第4节中给出。结论和未来的工作在第5节中提出。

2. 背景

给定在时间ti和相似性度量d（d：VxV→R）上的齐次归属多图G（V，E）的快照，通过以下步骤描述无监督方法对LP的一般过程（Liben-Nowell 和Kleinberg，2007年）：

（1）Graph分区 - 这个步骤将G（V，E）分成两个子图：GTraining（V，EOld）和GTest（V，ENew）。 GTraining包含直到ti为止创建的所有边（即，e.t≤ti且e∈EOld）。 类似地，GTest包含在ti之后创建的所有边e（即，e.t> ti和e∈∈ew）

（2）Graph加权 - 首先，它在GTraining中连接的节点之间建立人工边界。 然后它计算每个边的权重。 权重计算遵循特定标准（例如，相应节点之间的原始边缘的数量）。 图1说明了这个过程。

 

图1：人工加权图的例子。 原始图形中存在由连续线表示的边线。 用虚线表示的那些是为了LP目的而人为创建的。 加权标准定义了虚线的权重。

 

（3）核心标识 - 该步骤负责过滤活动节点vi，即在GTraining中至少有k个原始边缘和至少k个GTest中的原始边缘的节点。参数k由用户定义，通常取决于 网络中发生交互的平均频率。 活动节点比很少与其他节点交互的节点更可能连接。 Core，G中所有活动节点的集合就是这一步的输出。

（4）4分值计算 - 它使用d来为每对属于核心的节点vi和v j分配一个分数d（vi，v j），并且在GTraining中没有连接。

（5）性能评估 - 此步骤按d（vi，v j）（排名表中第一位较高的分数d（vi，v j））对配对（vi，v j）进行排序。排名列表中的Top-N对（vi，v j）被选为具有最高可能性的节点在t之后进行连接。 N是未在GTraining中连接但在GTest中连接的活动节点对的数量（见公式1）。最后，这一步将d的性能与基线随机预测器的性能进行比较。随机预测器只是简单地预测在GTraining中没有连接的随机选择的节点对。随机预测正确的概率仅由| ENew |之间的比率表示和可能的正确预测的数量（（核心） - | Eold |）。公式2输出相对于随机预测器的相似性度量的改进因子，其中Ecorrect是进程正确预测的链接数量。这个因素是传统上用来比较LP中相似性度量的性能的评估度量（Liben-Nowell和Kleinberg，2007）。

 

关于上面介绍的无监督方法有一些重点需要强调：

（6）过去几年，对LP的非监督方法进行了深入的研究（Liben-Nowell和Kleinberg，2007），（Lu和Zhou，2010），（Li等，2012），（Kuo等，2013）。 基本上，相关工作在构思相似性指标的方式和用于生成分数的信息种类方面有所不同。

（7）虽然图形加权步骤不属于（Liben-Nowell和Kleinberg，2007）提出的原始过程，但它经常被考虑到连接节点的链接强度以预测新的连接。

（8）相似性度量的选择是无监督方法的一个重要决策。 （Murata和Moriyasu，2007）是第一个提出图表加权步骤和相似性度量的加权版本（如常见邻居和Adamic-Adar索引）的工作。 有关这些指标的原始版本和加权版本，请参阅表1。 加权度量不考虑图的原始边。 对于这些度量标准，分数计算仅限于图形加权步骤构建的仿真边。）

表1：在LP中使用得分计算方法的例子 - 原始版本和加权版本。

 

3.提出的权重标准

本节介绍了在LP的无监督方法的图加权步骤中使用的建议加权标准（FTi）。 受到弱关系社会理论的启发，FTi标准的构想是将相互作用的频率与关于它们的时间信息相结合，以便最近的相互作用在预测新的关联方面比旧关系具有更高的影响。

等式3定义了FTi标准。 它应用于加权图的每个人造边缘并包含两个因素：

 

（1）第一个函数（NoI（u，v））返回节点u和v之间交互（原始边）的数量（频率）。

（2）受（Munasinghe和Ichise，2012）提出的时间分数度量的启发，第二个（βCT-max（t（u，v）））是一个阻尼因子（即需要考虑时间）。 最近交互的连接节点之间的权重高于最近一次交互发生在过去的那些节点之间的权重。 CT表示当前时间。 函数max（t（u，v））返回u和v之间边中最近的时间戳。因此，CT_max（t（u，v））返回最近一次u 和v到当前时间。 β是属于区间[0,1]的参数，分析人员使用它来校准加权过程中最近相互作用年龄的重要性。 β的较高（或较低）值在加权定义中增强（或衰减）时间的影响。

考虑如图1所示的例子。将权重标准限制为互动的次数（Fi）（Murata和Moriyasu，2007）（Lu¨和Zhou，2010），（Soares和Prudencio，2011），（ Zhao等人，2015），（Taha，2007），（Zhu and Xia，2016），（Dunlavy et al。，2011），所有三对节点的权重是相同的（权重（A，D） =权重（B，D）=权重（C，D）= 3）。 因此，他们的联系在分数计算中具有同样的重要性，因此在链接预测中也是如此。 例如，WCN相似性度量将针对三个可能的新链接（WCN（A，B）= WCN（A，C）=WCN（B，C）= 3）呈现相同得分，表明它们在链接预测中没有偏好。

另一方面，如果按照FTi准则的规定考虑了时间信息，那么最近的相互作用会导致更高的权重，并因此在链路预测中更多地受到影响（根据弱关系理论）。 在该示例中，使用CT= 2016并且β= 0.8的FTi准则，权重将是：

 

虽然，三对节点呈现相同的交互频率（每个三个连接），但与FTi相比，最近交互的节点获得了更高的权重。相互作用的频率随着每对节点之间最近相互作用的年龄而衰减。 （A，D）对的权重最高。事实上，由于节点在当前时间内互动（2016年），A和D之间的交互频率没有受到衰减。另一方面，对（B，D）和（C，D）的节点之间的相互作用的频率确实遭受了一些衰减。节点C和节点D之间的最后一次互动发生在2014年（年份差= 2岁）。 B和D最后在2015年互动（年份差= 1年）。因此，（C，D）的权重高于（B，D）的权重。

考虑到FTi提出的权重，WCN相似性度量将为三个可能的新链接提供不同的评分 (WCN(A, B) =2.7; WCN(A,C) = 2.5; WCN(B,C) = 2.2)。根据这个度量标准，配对（A，B）比其他配对更可能连接。两个节点（A和B）最近与其共同邻居（D）交互，而不是其他对。强调这一结果符合弱关系理论是非常重要的。事实上，根据这个理论，那些最近的交互会刺激网络中出现新的交互，很可能在节点A和B之间。

4.实验

4.1数据集

我们选择了两个版本（Liben-Nowell和Kleinberg，2007）使用相同的五个共工作者网络来执行我们的实验。 第一版（1994年至1999年的论文）覆盖了（Liben-Nowell和Kleinberg，2007年）使用的相同时间间隔。 这对帮助我们验证我们的实施非常重要。 第二版（2000年至2005年的论文）涵盖了（Munasinghe和Ichise，2012年）使用的同一时期。 所有网络都是从arXiv API9中提取的。

这两种版本的网络都是同质的多图，其中节点和边分别代表作者和论文。 所有网络在边缘都包含一个属性：论文的发表年份。

4.2实验过程

我们的实验遵循了第2节中描述的相同步骤。关于每一步的具体内容如下：

•图表分区 - 我们将每个网络分为两个三年的时间段。因此，从1994年到1999年的每篇论文都被划分为GTraining [1994,1996]和GTest [1997,1999]。同样，2000年至2005年的论文网络分为GTraining [2000,2002]和GTest [2003,2005]。

•图加权 - 我们在GTraining中连接的节点之间创建了人造边。然后我们计算出每个人工边缘的十个权重值。 Fi是用于计算第一个权重的权重标准。 FTi被用来计算

其他九个权重。我们将阻尼因子β的值从0.1变化到0.9。 β的每个值都导致九个权重之一。

•核心识别 - 为了识别属于核心组的节点，我们考虑了k = 3。因此，核心组成员包括所有在训练集至少写过3篇文章的活跃作者，以及至少3篇文章测试集。有三个原因指导了这种选择：（a）所有网络的训练和测试周期的长度为三年; （b）我们认为一年可能是纸张出版的合理频率间隔; （c）这与（Liben-Nowell和Kleinberg，2007）中定义的相同的值，其中进行了类似的实验。

•分数计算 - 此步骤执行每个网络中每个仿真边缘的相似性度量（WCN和WAA）。 为了更好地呈现结果，我们使用首字母缩略词WCNFi和WAAFi来表示用Fi标准产生的权重计算的相似性度量。 首字母缩略词WCNFTi（β）和WAAFTi（β）用于表示用所提出的权重标准产生的权重计算的相似性度量。

•性能评估 - 将WCNFi，WAAFi，WCNFTi（β）和WAAFTi（β）的性能与随机预测器的性能进行比较。 它们代表随机预测变量相应度量的改进因子。

4.3结果

表2和表3提供了识别核心步骤后的网络的一些统计数据。

 

表2：关于实验中使用的第一版网络的统计数据 - 1994年至1999年的论文。

 

图2和图3显示了每个网络上每个度量在随机预测器上的改进因子的性能。 整体分析显示，在所有网络和时段中，没有任何指标超过所有其他指标。 尽管如此，仔细分析可以看出一些有趣的结果。

 

在衡量标准的两两比较中，WCNFTi和WAAFTi分别在六个网络（60％）和七个网络（70％）中表现优于WCNFi和WAAFi。 同样重要的是强调WCNFTi和WAAFTi分别在第二版的五个网络中的四个（80％）和五个（100％）中表现优于WCNFi和WAAFi。 我们认为，这是由于这些网络更近（2000年至2005年），因此比第一版（1994年至1999年）更完整和更新。

 

在加权标准的两两比较中，FTi在十个网络中的六个（60％）中表现优于Fi。这六个网络中的五个属于第二个版本，加强了我们关于该组网络完整性的理论。在两个网络中，两个标准都导致了可比的结果。 Fi仅在两个网络中跑赢了FTi。

所有上述结果证实了弱关系理论和我们的假设，即基于时间信息的加权链接可以改善链接预测。

 

图4和5显示了两个网络版本中相似性度量WCN和WAA中的FTi参数（阻尼因子）获得的平均性能。对于网络的第一个版本，对于两个相似性指标，β= 0.4时达到最佳性能。第二版WCN的最佳性能是在β= 0.2时达到的，而WAA是在β= 0.6时达到的。

最后，我们的结果还显示，WAA在所有网络中几乎总是跑赢WCN。事实上，FTi和Fi标准并没有改变这种情况。它表明，无论加权标准如何，次要的和主要的共同邻居可能会比用主要共同邻居产生更好的结果有用。

5. 结论

 

预测未来一对节点是否将连接是一项重要的网络分析任务，称为链路预测（LP）问题。已经开发了各种方法来预测社交方法中的联系。其中一些计算连接节点之间的兼容性程度（链接强度），以获得LP的有用见解。然而，尽管时间数据对LP问题的重要性，但很少有举措调查了使用这种信息来表达链接强度及其在链接预测中的相应结果。

受到弱关系社会理论的启发，在本文中，我们提出了一个权重标准，它将关于它们的交互频率和时间信息（FTi）相结合，以便定义社交网络中连接节点对之间的权重（链接强度）。根据FTi，最近的互动在权重计算方面比旧的互动有更大的影响，在LP中。我们的实验是由许多有关LP的研究以前使用的十个共工作者网络完成的。我们比较了传统相似度量加权公共邻居（WCN）和加权亚当 - 阿达尔（WAA）产生的性能，并结合两个加权标准：一个是提出的标准（FTi），另一个是最先进的加权标准，仅基于交互频率（Fi）。结果表明，在大多数网络中，WCN和WAA联合FTi优于WCN和WAA联合Fi，证实了我们的假设，即基于时间信息的加权链路可以改善链路预测。

作为未来的工作，我们考虑制定一个同时结合时间，拓扑和背景数据的加权标准。评估我们的基于时间的加权标准对LP问题的监督方法的影响也是有趣的。我们的标准与联合作者背景下的网络实验也是可取的。对于更多的网络，我们还计划检查加权标准获得的结果之间的统计显着性差异。