融合用户行为同步指标的链路预测研究

王 曦，许 爽，许小可

(大连民族大学信息与通信工程学院 辽宁 大连 116600)

真实世界存在各种复杂系统，如果将复杂系统的主要元素抽象为节点和连边，就可将其抽象为复杂网络，如科学家合作网络[1]、万维网络[2]、社交网络[3]和交通网络[4]等。当网络的某些结构信息缺失时，可应用链路预测[5]方法来分析节点之间不确定的或潜在的链接关系[6]。如在线社交服务中，链路预测可以挖掘社交用户的兴趣并挖掘用户之间的潜在关系，为用户推荐感兴趣的朋友[7]。在蛋白质新陈代谢网络中，链路预测可推断蛋白质之间的交互作用，从而有针对性地进行实验来节约成本[8]。在科学家合作网络中，可以预测科学家的合作模式和强度，对理解科研合作的组织方式具有重要的作用[9]。

链路预测研究中，最经典的方法是节点局部结构的相似性，如共同邻居(common neighbors, CN)、Adamic-Adar 指标[10]、资源分配指标(resource allocation, RA)[11]、局部路径相似性指标[12]及局部随机游走的相似性指标[13]等，但通常不考虑节点之间链接的权重大小。真实复杂系统中元素之间的交互强度往往也蕴含着关键信息，可将其抽象为加权网络进行分析，因此链路预测研究开始重视如何充分利用网络连边的权重信息。文献[14]提出了基于加权共同邻居指标(weighted common neighbors,WCN)、加权Adamic-Adar 指数(weighted Adamic-Adar, WAA)及加权资源分配指标(weighted resource allocation, WRA)等链路预测方法，通过对多个实证网络的研究发现了加权链路预测中“弱链接的强作用”。文献[15]提出了一种基于可靠线路的链路预测方法(rWCN, rWAA, rWRA)，通过对可靠路线赋予更高权重来达到更鲁棒的预测性能。文献[16]提出了一种局部加权路径指标，精细利用路径的权重特征来实现准确预测。文献[17]改进了结构算法使其更适用于有向加权网络的链路预测，如改进的共同邻居算法(modified common neighbors,MCN)、改进的Jaccard 系数(MJC)、改进的Adamic Adar 算法(modified Adamic Adar, MAA)和改进的优先链接算法(modified preferentialattach, MPA)。文献[18]设计了一种高效共同邻居指标，该指标通过分析共同邻居节点的拓扑有效性对连边端点两侧资源分配过程的影响来刻画节点间相似性，在15 个实际网络数据实验中表明，该方法具有较高的预测精度。文献[19]提出了一种链路权重预测的无监督混合方法，结合网络的权重一致性和节点的链路权重潜在特征可有效解决链路权重预测问题。文献[20]通过对网络中真实存在的连边进行异常度排名，将链路预测应用在大规模瘫痪状态下的电力系统的恢复，该方法不仅可以快速连通电源发电机，也能及时恢复重要线路。文献[21]提出了基于链路线形的危险链路预测模型，对新加入交通网络的链路进行预测，从而在碰撞发生之前进行相应的整治，该模型可有效准确地对危险链路进行预测。

虽然上述研究相对于无权链路预测方法都取得了更好的性能，但是这些方法仅仅是使用连边的权重信息，没有考虑挖掘该连边权重形成的时序信息。在很多加权网络尤其是社会网络中，连边的权重是由该连边连接的两个节点多次互动形成的，这种互动行为具有一定的时间特性，也是人类动力学研究的重要内容[22]。经过研究发现，两个节点行为的时间同步性往往是由于两个节点存在链接造成的[23]，因此可利用两个节点的行为同步性来反推它们之间是否存在链接关系。目前该类方法已经广泛应用于网络结构的重构研究中[24]。文献[25]提出检测嘈杂实验数据中相位同步的方法，实验发现该方法可有效衡量网络群体中个体的同步程度，并探究了同步性如何影响个体之间的关系。文献[26]利用鸽子飞行轨迹的时序相关性，在成员之间重构了完整明确的网络层次结构。文献[27]分析了时间滞后衰减作用对于网络重构的潜在影响，取得了较好的网络重构效果。文献[28]通过对具有同步和异步动态特性的网络进行研究，揭示了机器学习方法可以重构交互网络并识别网络内在的动力学特征。文献[29]根据由个人状态的时间序列组成的传播数据，重建了人与人之间牢固关系的主干，并成功地将该方法整合到了有针对性的免疫策略中。上述研究都是将节点行为同步信息应用在网络重构中，目前将此类信息应用于链路预测的研究还很少见。

网络重构和链路预测通常采用不同的研究范式和算法，本文尝试将节点同步性信息这一经典网络重构的方法引入到链路预测领域，提出一种网络拓扑结构上融合节点行为同步指数的链路预测方法。该方法将节点局域结构相似性(共同邻居指标)和节点行为在时间上的相似性(行为同步指数)相融合，充分利用节点之间的拓扑结构域和行为时间域特征。相对于仅使用网络域基于结构和权重的主流方法，其链路预测效果更显著。同时，为了探究局域结构和同步指数对链路预测的共同关系，尝试使用一个可变参数调整两者的融合比率，实验表明可变参数在较大范围内都不会影响链路预测的结果，说明了本文所提方法具有较好的鲁棒性。

1 问题描述与评价指标

1.1 问题描述

定义加权网络G=(V,E,W)，其中 V是所有节点的集合， E是网络中连边的集合， W是网络中连边权重的集合。定义 T为网络中最大与最小时间戳的差值，将时间进行相对时间处理后基于[0,T]将整个数据划分为两段时间间隔[0,Tn]和[Tn+1,T]。将[0,Tn]时间上数据的连边集合作为训练集 ET，将[Tn+1,T]时间上的连边集合作为测试集 EP。这两个边集之间的关系为：ET∪EP=E ，ET∩EP=φ，且训练集 ET与测试集 EP的样本为9∶1。在科学家合作网络中，时效信息按年计。在短信网络中时效信息按秒计。在本研究中，待分析的所有节点既在一个周期内存在，也在第二个周期内存在，即[Tn+1,T]中出现的所有节点都是[0,Tn]上已经存在的节点。对于仅在[0,Tn]和[Tn+1,T]中出现的节点本文做了删除处理。

1.2 评价指标

Precision 只关注前L 条高分连边的性能，根据出现连边可能性的分数值从大到小排序，如果有m 条边是属于存在边集合，那么Precision 定义为：

由该式可知，m 越大则Precision 值越高，预测越准确。

2 链路预测方法

2.1 基于共同邻居的相似性指标

1) CN 指标

共同邻居(CN)指标是通过计算两个节点共同邻居的数量来判断节点相似性。定义节点x的邻居集合Γ(x)，节点y的邻居集合为Γ(y)，共同邻居指标定义为：

一般来说，节点x和节点y之间的共同邻居越多，连边的分数值越大，节点的相似性越大。

2) AA 指标

在共同邻居的基础上，考虑两端节点度的影响，则演变为AA 指标。AA 指标的思想是度小的共同邻居节点贡献大于度大的共同邻居节点。该方法通过共同邻居的度，为每个节点附上一个权重值。这个值为该节点度的对数的倒数，定义为：

式中， kz表示x和 y的共同邻居节点z的度。

3) RA 指标

RA 与AA 相似，都对节点度大的共同邻居的贡献进行抑制，即节点度越小，对网络连接产生的贡献就越大，RA 指标的抑制程度相对更大。因此，当网络的节点的度都较小时，两者区别不大。而当网络节点中存在较大度时，因为对度大节点有更高的抑制性，所以RA 展现出相对较好的预测性能[11]。RA 指标定义如下：

2.2 基于共同邻居的加权相似性指标

加权网络进行链路预测时，不仅要考虑网络的拓扑结构，也要考虑连边的权重，才能取得较好的预测效果。将CN、AA、RA 扩展到加权的形式，就可以将连边权重的信息应用到加权网络的链路预测中。常用的3 种加权指标WCN、WAA 和WRA的定义为如下形式：

1) WCN 指标：

式中，W(x,z)为两节点x 和z的连边权重；W(z,y)为两节点z和y 的连边权重。

2) WAA 指标：

式中， s(z)表示邻居节点z的强度；WAA 根据每个共同邻居的强度值进行了加权。

3) WRA 指标：

式中，WRA 是WCN 的另一种权重赋予方式，分母不再采用强度的对数，而直接采用节点强度进行了加权。

2.3 基于可靠路线的加权相似性指标

在加权网络链路预测中，如何利用权重信息是研究重点。在通信网络中，信息的传输往往需要依赖最可靠的线路将数据包从源节点传输到目标节点，以保证数据传输过程中不被损坏。受通信网络的启发，文献[15]提出了可靠路线加权指标的链路预测方法，假设所有连边的权重都是独立的，通过连边权重的乘积计算两个节点连边的相似性得分，定义如下：

1) 加权可靠路线CN 指标(rWCN)：

2) 加权可靠路线AA 指标(rWAA)：

3) 加权可靠路线RA 指标(rWRA)：

上述3 种指标利用了可靠路径的计算思路，改进了WCN、WAA、WRA 指标，并且在没有提高计算复杂度的前提下，对可靠路线赋予了更高的权重，从而提高了链路预测的准确性。

2.4 基于行为同步指数的相似性指标

在很多真实社会网络中，通过两个节点多次互动形成的权重是普遍存在的，并且这种互动行为往往具有一定的时间特性，该时间特性会通过两个节点的链接而产生[22]，因此可利用这两个节点时间上的同步性来推断它们之间的潜在链接关系。

从链路预测的角度分析，网络中节点之间的互动存在时间上的延迟，这种时间特性可以作为一种同步现象来衡量节点的行为同步性。如果节点之间存在链接，它们之间的交互时间间隔越短，则这两个节点的行为将越趋于同步，以此可推断他们未来存在链接的概率就越大。如节点x给节点y 发消息，节点y每次都立即回复，说明两个节点产生链接的可能性极大。如果节点x给节点z 发消息，节点z经常不回复或是时间间隔很长才回复，那么这两个节点产生链接的可能性就较小。因此，在不知道两个节点之间是否存在链接的情况下，观察两个节点之间的行为同步性可以推断他们之间是否存在联系。

图1 用户同步指数的计算过程图

式中， Θxy是时间序列 Sx和 Sy的平均距离； Dxy是节点x到节点y的时间距离； Dyx是节点y到节点x的时间距离； Ox是节点x邻居节点的集合； Oy是节点y邻居节点的集合； Nx是节点x与其他节点信息交互的次数； Ny是节点y与其他节点信息交互的次数。本文将平均距离作为衡量两个节点时间序列相似性的标准并应用于链路预测，平均距离越短则时间序列相似性越强，产生连边的可能性越大[30]。式中的Dxy和 Dyx不仅可以取所有距离的平均值，也可以取所有距离的最小值，此时距离定义为：

2.5 融合结构和行为同步指数的相似性指标

本文提出的融合结构和行为同步指数指标是同时计算两个节点之间的共同邻居信息和行为同步指数。事件交互对应消息的发送或接收，因此定义节点发送消息的融合行为同步指数指标STCN，其中S 表示发送，T 表示时间序列，CN 为共同邻居数量。定义接受消息的融合行为同步指数指标RTCN，其中R 表示接收，则STCN 和RTCN 的具体公式为：

式中，CN 为两节点的共同邻居数；由于事件交互对应消息的发送或接收，所以STCN 中， Θs是时间序列 Sx与时间序列 Sy发送消息的时间序列相似性；RTCN 中， Θr是时间序列 Sx与时间序列Sy接收消息的时间序列相似性。融合行为同步指数的相似性指标包含两部分，一部分是以CN 为主的结构信息，一部分是以行为时效信息为主的同步指数。

为了探究局域结构和同步指数对链路预测的共同关系，本文使用一个可变参数 α来调整两者的融合比率，并分析本文所提方法的鲁棒性和两类指标的相关关系，具体公式为：

式中， α取值范围为[0,1]。当 α=0 时，此时公式中只有结构信息的存在； α=1 时，公式中只有用户同步性存在；在两者之间时，公式中既有结构信息的存在，也有行为同步性存在，并且在0～1之间可变参数的取值可以改变两部分信息在预测中的比例。

3 实证分析

3.1 数据说明

本文使用了两类实证数据，一类是3 种科学家合作网络数据[31]，其中节点表示从事研究的科学家，连边代表两个科学家有合作研究的关系，连边的权重代表科学家合作的次数，连边时间代表科学家之间的合作时间。另一类是由运营商提供的某城市某月的3 种短信数据，其中节点代表用户，连边代表用户之间的短信往来，连边的权重代表用户之间短信网络的次数，连边的时间代表用户之间短信往来的时间。为了保护隐私，所有的电话号码被隐藏，没有任何信息能表明用户身份。

1) JIS 数据网络是以两本期刊Journal of Informetrics、Scientometrics 作为研究对象，从Web of Science 数据库下载了2013-2017 年的文章记录。包括Article、Review、和Proceeding paper 这3 种类型。该网络包含3 540 个节点，6 413 条连边。

2) BMJ 网络是以期刊《英国医学期刊》(BMJ)作为研究对象，从Web of Science 数据库下载了2013-2018 年的所有论文。该网络包含4 389 个节点，4 335 条连边。

3) Nature 网络是以期刊《自然》(Nature)作为研究对象，从Web of Science 数据库下载了2010-2018 年的所有论文。该网络包含21 060 个节点，21 259 条连边。

4) SD01 网络：包含某运营商一个月内44 430个用户节点，和68 834 条短信记录。

5) SD02 网络：包含某运营商一个月内72 146 个用户节点，100 974 条短信记录。

6) SD03 短信网络：包含某运营商一个月内14 433个用户节点，23 285 条短信记录。

3.2 预测结果分析

本文使用上述两类实证网络，每一类有3 种真实数据集。每个网络按时间截点划分数据集，训练集与测试集比例为9∶1。从不存在的边中抽取负样本，让测试集中正负样本的比例为1∶1。

表1 为6 种网络中，融合行为同步指数指标与基于局部信息相似性指标、加权局部信息相似性指标、可靠路线相似性指标的Precision 结果比较。

表1 6 种实证网络链路预测Precision 值比较

可以看出，本文提出的融合行为同步指数的链路预测方法的预测精度最好，其预测准确率比共同邻居、加权共同邻居、可靠路线策Precision 指标提高了15.3%～68.2%。

计算融合行为同步指数指标时分别给出了行为同步指数取最小值及平均值的实验结果。每种数据中最高的预测性能加粗表示。表1 中可发现行为同步指数总是取得最佳的性能，虽然取最小值及平均值在不同网络中预测结果有些不同，在BMJ 网络中，行为同步指数取最小值预测更准确。而在SD01、SD02、SD03、Nature 和JIS 网络中，取平均值预测性能更好。

除了行为同步指数的取值影响算法精度外，时间序列的方向(如发送和接收)同样也影响着预测精度。有些网络利用发送消息计算同步指数能取得更好的预测结果，有些网络中用接收消息计算同步指数能取得更好的预测结果。表1 中，SD01、SD02、SD03 网络在行为同步指数取平均值的情况下，接受消息的RTCN (mean)的预测结果更高。而在Nature、JIS 和BMJ 科学家合作网络的预测中，发送消息的STCN (mean)预测效果更好。在短信网络中接收消息更能有效挖掘网络节点之间的预测关系。而在科学家合作网络中，发送消息更能有效挖掘网络节点之间的预测关系。

基于局部结构共同邻居数量演化出来的一系列相似性指标，预测结构没有明显变化，因此它们相互之间的性能波动较小。而当局部结构信息加入了行为同步指数之后，预测结果得到了大幅提升，这说明这两类信息具有很强的互补性。如在SD03 网络中，基于局部结构特征的Precision值最高为0.498，加入行为同步指数之后，Precision值为0.811，相对提高了62.8%。因此，节点的行为同步指数不仅能用于网络重构中，还可以应用在链路预测上。无论是在科学家合作网还是在短信交互网中，生成网络连边权重的时效信息都是不能忽略的重要特征，由时效信息演变的同步效果都是普遍存在的，融合同步指数的链路预测方法性能更具有优势。

3.3 融合比例变化对预测结果的影响

实验中利用可变参数 α改变网络结构信息和时效信息的融合 α值，同时观察该值对预测性能的影响。两类网络中各选一种，以科学家合作网Nature 和短信网络SD03 为例进行分析，每一类中其他网络的结果与本文呈现的该类网络结果是相似的。

图2a 是Nature 网络特征融合比例变化的性能曲线图。纵轴是预测结果的Precision 值，横轴是以0.1 为跨度的α值。预测结果显示，不管是STCN方法还是RTCN 方法， α取0 是单一结构信息的预测结果，此时并不能达到一个较好的预测性能。α=1时是单一同步指数的预测结果，而预测效果却是最不理想的，甚至要低于单一结构特征预测。尤其是接收消息的RTCN 特征，比单一结构信息的Precision 值下降了48.9%。当0<α<1时，无论 α取何值都能取得较高的预测性能，说明本文的方法具有很好的鲁棒性。综上所述，对于Nature 等科学家合作网络来说，科学家的共同邻居数量与行为同步性共同影响着合作网络中链路的出现和动态演化。

图2b 是SD03 短信交互网络特征融合比例变化的性能曲线图。纵轴是预测结果的Precision值，横轴是以0.1 为跨度的 α值。在4 种特征的预测下，预测精度最低时对应的 α等于0，此时是结构信息的单一预测结果，说明短信交互网络中只用结构信息不足以挖掘网络的潜在链接信息。预测精度最高时对应0<α<1，此时为结构信息和行为同步指数共同的预测结果。 α在一定范围内取值，预测性能都没有显著变化，说明了本文所提方法具有很好的鲁棒性。当α=1时，图2b 中没有出现预测值明显下跌的情况，结果与0<α<1时的Precision 值相差无几，此时是行为同步指数单一预测结果。综上所述，SD03 网络用单一同步指数预测也会出现很好的精度，用户之间的行为同步性可以在不依赖结构信息的情况下，实现单一特征预测并且达到较好的预测精度。

图2 特征融合比例对预测性能的影响

考虑到科学家合作网络和短信网络的形成机制不同，科学家合作网络因为n 个合作者连成完全图，所以共同邻居指数很重要。这里假设同步性在合作网络中起的作用实际上只能在CN 值相同的时候提高区分度，因此将科学家合作网和短信网络的预测参数 α值调节到一个非常小的值( α=0.001)，再调节到一个非常接近1 的值( α=0.999)，实验结果如图3 所示。

图3 是Nature 期刊科学家合作网络在 α=0.001和 α=0.999 的预测结果，并将该结果与 α取0 和1的预测结果做对比。在科学家合作网络之中， α=0.001 就可以达到一个提升预测性能的作用，并且与α=0.999 并无差别。说明此时同步性指标的作用类似于局域性指标里面的高阶项，因此预测的过程中以CN 为主，同步性可以辅助CN 达到提高预测分辨率的效果。

图4 是短信交互网络SD03 在α=0.001 和α=0.999的预测结果，并将该结果与α取0 和1 的预测结果做对比。短信网络的实验结果中可以看出CN 指标作用很小，而同步性无论在 α=0.001 还是 α=0.999都可以达到良好的预测精度。本文统计了6 种网络的平均聚类系数，结果如表2 所示。

图3 Nature 网络预测结果

图4 SD03 网络预测结果

从表2 中可以看出，3 个短信网络的平均聚类系数都很小，说明短信网络的结构都十分松散，因此预测过程中邻域结构信息的价值很小，这也导致了 α=1 时图2b 中SD03 网络没有出现预测值明显下跌的情况。而合作网络的平均聚类系数相对较大，也说明了科学家合作网络的共同朋友结构信息明显，对CN 的依赖性较大，同步信息仅起到提高更好分辨率的作用。

表2 6 种实证网络平均聚类系数

4 结 束 语

本文将用户行为同步性信息这一网络重构的方法引入到链路预测领域，提出一种网络拓扑相似性上融合节点行为同步指数的链路预测方法。通过对该方法在真实社会时效网络上与局部结构相似性指标、加权局部结构相似性指标、可靠路线相似性指标进行对比分析，发现该方法可有效提高网络的链路预测性能。相对于经典方法，本文方法在Precision指标上提高了15.3%～68.2%。

本文方法不仅可提高链路预测的性能，也可揭示加权网络的内在结构特征和行为同步指数对链路预测的相互作用与共同影响。研究发现，在科学家合作网络中，需要结构信息和同步指数共同作用，才会得到良好的预测效果。而在短消息交互网络中，结构相似性指标的预测性能较差，而仅仅使用行为同步指数就可以接近最优的预测性能。在以后的工作中，将采取更优的方式将节点行为同步指标融合与网络结构相似特性进行融合，并且对结构信息的时效性展开更深入研究，以达到更优的链路预测性能。同时，也将对短信网络和科学家合作网络的细节机制做更深入分析，包括发送短信的模式、群发和短时间频繁发送等，以根据其结构特点来设计链路预测方法。本文所提方法可以拓展到社团检测、信息传播等其他网络科学领域的实际应用中。