基于节点匹配度的动态网络链路预测方法

李聪，季新生，刘树新，李劲松，李海涛

基于节点匹配度的动态网络链路预测方法

李聪，季新生，刘树新，李劲松，李海涛

（信息工程大学，河南 郑州 450001）

现实世界存在众多真实网络，研究真实网络中的动态演化趋势和时序性特征是热点问题。链路预测技术作为网络科学领域重要研究工具可通过挖掘历史连边信息推测网络演化规律，进而对未来连边进行预测。通过分析动态真实网络中的拓扑结构演化，发现通过分析网络拓扑中节点间的交互性和匹配度问题能够更充分捕捉网络的动态特征，提出一种基于节点匹配度的动态网络链路预测方法。该方法对网络节点的属性特征进行分析，定义基于原生影响力和次生影响力的节点重要性量化方法；引入时间衰减因子，刻画不同时刻网络拓扑对连边形成的影响程度；结合节点重要性和时间衰减因子定义动态节点匹配度（TMDN，temporal matching degree of nodes）方法，用于衡量节点对之间未来形成连边的可能性。在5个真实动态网络数据集中的实验结果表明，相比现有3类主流动态网络链路预测方法，所提方法在AUC和Ranking Score两种评价标准下均取得更优的预测性能，预测结果最高提升42%，证明了节点间存在着交互匹配优先级，同时证实了节点原生影响力和次生影响力的有效性。

动态网络；链路预测；节点匹配度；节点重要性；时间衰减因子

0 引言

随着社会学[1]、生物学[2]、医学[3]以及互联网技术[4]的飞速发展，复杂网络[5]被广泛应用于复杂系统的抽象化表示、形式化分析与深度挖掘等，极大地推动了网络科学的蓬勃发展。复杂系统[6]中的个体，如人类、细胞、基站、路由器等可以看成实体，在网络拓扑中用节点表示，节点之间的连边用来描述实体之间的关系[7]。链路预测作为研究复杂科学的重要技术之一，已成为近年来的研究热点问题[8-11]。链路预测技术旨在利用复杂系统中已观测的结构信息、属性信息等，发现网络拓扑结构中的缺失连边，以及推测未来可能形成的连边[12]。链路预测为生物学、医学、计算机网络、社会科学等领域的研究提供了强大的技术支持。通过对大量节点之间复杂关系的挖掘可清晰地分析网络结构，发现网络中连边的演化趋势[13]，实现对未来连边的预测。例如，通过分析社交群体近期的社交活动，利用链路预测技术寻找未来可能发生的诈骗、推销等异常行为。

近年来，社交网络分析在各行各业中引起了相当大的关注，被广泛应用于市场营销、业务流程建模及传染病模型。链路预测作为社交网络分析的重要手段能够捕捉社交网络信息，及时发现新的节点和连接。现实中的社交网络由个体及个体间复杂关系组成，是一个高度动态变化的网络。通过链路预测从已知的网络结构中寻找和检测隐藏的连边和节点，可进行异常节点挖掘、重要连边预测等，映射到真实社交网络中可识别诈骗信息。当前，对于静态网络的链路预测技术研究已经相当成熟，文献[14]详细对比分析了各种方法，将其在局部和全局两个维度进行归类。对于动态网络的研究也在近几年发展迅速。Ahmed等[15]提出一种通过集成网络中的时间信息、社区结构和节点中心性进行动态网络链预测的方法，通过节点在社区中的交互情况构造特征向量来预测节点未来的重要性。Günes等[16]提出了一种演进网络的链路预测方法，先计算过去不同时间段的网络结构中不同节点的相似性得分，再通过时间序列预测模型ARIMA来预测未来节点的连边情况。Ahmed等[17]提出了一种针对时间不确定网络的链路方法，首先将不确定网络中的链路预测问题转化为确定网络的随机游走问题，然后在子图中计算节点与邻居之间的相似性分数。针对异构网络，Sett等[18]结合多域拓扑特征和时间维度，提出一种TMLP算法，利用二元交互情况和图拓扑特征变化情况，结合时间序列模型进行预测。但上述方法通过转化成静态图或考虑局部特征，容易丢失动态网络中重要拓扑信息，影响预测精度。

本文通过捕捉历史拓扑特征，并将其作为节点相似度的依据，提出一种基于节点匹配度的动态网络链路预测方法。该方法根据节点原生重要性和次生重要性定义节点匹配度，用于衡量节点间未来产生交互的可能性。进而结合网络拓扑的历史变化特征及时间影响力，捕捉网络拓扑的动态信息。实验结果表明，本文所提方法在动态网络链路预测方面相比现有方法取得更优的效果。

1 相关工作

1) 任意节点不能形成自闭环；

2) 任意节点之间最多只能含有一条边；

3) 节点间的交互无方向；

4) 连边只代表节点之间关系的存在。

2 方法介绍

原生能力[19]与次生能力[20]在现实生活中无处不在，大到生态系统，小至单一细胞，近些年频发的自然灾害也会造成原生灾难[21]和次生灾难[22]。例如，在社交网络中，有些个体天生擅长某些事物，称之为原生能力；个体具备依托已存关系而带动新关系形成的能力，此能力建立在原生能力的基础上，称之为次生能力。复杂网络作为真实网络的抽象，需准确刻画真实网络的网络特性及个体属性。在网络拓扑中描述实体的节点应反映出实体的原生能力和次生能力。度是衡量节点重要性[23]的指标，是真实网络中实体原生能力在复杂网络中的抽象表现，在网络拓扑中可作为节点原生能力的体现。例如，在社交网络中，节点度高的节点之间更容易形成连接；在食物链网络中，节点度高象征着在食物链中的等级高，这部分节点更倾向于与节点度低的实体形成连边。在网络拓扑中，节点的度是由节点自身性质决定的，而连边是在节点度的基础上产生的，两者是真实系统中原生与次生逻辑关系的抽象。作为节点的次生产物[24]，连边影响力被多次提起。连边具有带动新连边形成的能力，此能力决定于节点本身，这正是真实网络中次生能力的抽象，在网络拓扑中，称之为节点的次生能力。本文根据节点原生能力和次生能力定义节点原生重要性和次生重要性，并结合两者提出节点匹配度的概念。

2.1 节点重要性

对于节点重要性的衡量可从节点自身和邻域拓扑两个角度加以考察。连边是基于节点性质而形成的，可看作节点的次生产物。在复杂网络中，节点度可用于衡量节点在网络中的重要性程度，其可以解释为节点周围连边贡献的和[25]。然而，节点度将每条边的贡献程度设为1，无法区分不同边的连接能力[25]，因此，本文用连边连接能力刻画该贡献程度，定义节点次生重要性。

下面讨论连边连接能力的量化问题。通常情况下，复杂网络中连边的形成不是随机的，而是具有特定倾向性。该倾向性在无标度网络中通常可用“优先连接（PA，preferential attachment）[26]”机制解释。该机制描述了复杂网络中“富者越富，强者越强”的现象。对于一条连边而言，可利用优先连接机制刻画其连接能力。传统PA方法只考虑端节点度的乘积，对网络中三角形结构具有的贡献能力未做区分。

三角形结构[27]稳定性强，结构不容易发生改变，是复杂网络中最为稳定的局部结构之一。稳定性强则意味着结构不容易发生改变，在动态网络中则意味着连边不会随时间的变化而轻易消失。

图1 不同时刻网络拓扑图示例1

Figure 1 Example of network topology diagram 1 at different times

图2 不同时刻网络拓扑图示例2

Figure 2 Example of network topology diagram 2 at different times

图3 第时刻网络拓扑子图

基于上述分析，本文考虑三角形结构与非三角形结构的贡献区别，基于PA指标定义连边的连接能力，如下：

图3中通过上述方法可计算得出

图4 第时刻网络拓扑子图

在图4中，有

上述定义考虑了节点原生重要性和节点次生重要性，并对节点间单个节点重要性进行量化，因而对节点重要性的刻画更加合理。在图4所示的拓扑子图中可以看到，通过此方法计算得到的节点重要性数值为

2.2 节点匹配度

节点重要性决定节点的影响力，在实际网络中，影响力大的个体捕获资源和信息的能力更强。Wang等[28]提出，在电网中，每个电站都具有有限负载和有限容量，而节点的承载能力决定了电站的负载和容量，重要的节点会承载更多的负载，与其他节点的匹配能力[29]会更强。综合以上情形，给出节点匹配度的定义，用于刻画拓扑结构中节点间产生连边的概率。

2.3 时间衰减因子

结合衰减因子，节点匹配度的定义如下。

3 衡量标准及数据集

3.1 对比方法介绍

（1）传统方法

共同邻居（CN，common nodes）方法[31]：以两节点之间共同邻居数量为衡量标准，数学公式表示为

Adamic-Adar（AA）方法[32]：此方法是建立在共同邻居的基础上的，即两节点的共同邻居度越大，则两节点之间的相似性分数越高，数学公式表示为

资源分配（RA，resource allocation）方法[33]：RA与AA有异曲同工之妙，两者的思想相同，只是赋予节点权重的方式不同，数学表达式为

局部路径（LP，local path）方法[34]：将三阶路径考虑进来，数学表达式为

（2）拓展方法

①基于时间序列的拓展方法

首先将在时刻观察到的网络划分成多个时间分段的快照，然后定义一个预测窗口，将这些时间快照按照窗口长度进行划分。

利用相似性指标计算每个子图上节点对的相似性分数，构造时间序列，利用平均预测模型，得到相似性分数。预测模型为

此类拓展方法用TCN、TAA、TRA、TLP[35]表示。

②基于时间因子的拓展方法

Güneş等[16]将时间因子应用于相似性方法内，结合时间因子，网络的邻接矩阵表示为

相应的拓展方法为

3.2 算法评价标准

RS对所有未连边按照相似分值大小排序，得到测试集的边在最终排序中的位置，测试集连边排名越高，排序分值越小时，说明该算法具有越好预测性能。以为未连边的集合（测试集中和不存在边集的集合），网络中某条测试边的RS为

整个网络的平均RS可通过遍历求和得到，计算方式如下。

3.3 数据集

通过调研近两年文献，发现多数文献选择邮件数据集进行算法性能对比。为验证所提方法的性能，使其更具有说服力，本文选用5个来自不同领域的真实动态网络数据集进行实验。5个真实数据集的基本特征参数如表1所示。以下详细介绍各数据集的具体信息。

（1）DNC emails（DNC）[36]：由 2016 年美国民主党全国委员会邮件泄露事件中采集的邮件往来网络，其节点表示邮件账号，有向边表示某账号发往另一账号的邮件。

（2）Manufacturing emails（MAN）[36]：一个制造业工厂内部员工的邮件往来网络。属于动态网络，其中节点表示员工账号，有向边表示在某一时刻由员工之间发送的邮件。

（3）LevantMonths（LEM）[37]：一个由堪萨斯事件数据系统基于包含WEIS编码事件的文件夹收集的交互网络，其中包含8个国家之间的交互信息。原始数据集涵盖了1979年4月至2004年6月的事件。

（4）Email-Eu-core-temporal（EEC）[38]：一个由欧洲某大型研究机构内部邮件往来数据构成的有向网络。节点表示邮件账号，有向边表示某一账号在某时刻发往另一账号的邮件。根据数据来源，原始数据集包含若干子数据集，代表研究机构内不同部门的邮件往来。本文选用其中的email-Eu-core-temporal-Dept1（EEC1）和email-Eu- core-temporal-Dept2（EEC2）。由于原始数据集的时间戳起始于0，确切起始日期无法确定。

4 实验结果与分析

为验证所提TMDN在真实数据集中的预测效果，本文通过对比实验分析了TMDN在不同参数、时刻下AUC和RS结果，具体分析如下。

4.1 平均性能对比

4.1.1 AUC评价方法

首先研究所提TMDN方法在AUC衡量标准下的性能。图5为TMDN和现有方法在真实数据集中的AUC对比结果。可以看出，与其他指标相比，TMDN指标在5个网络中均取得了较高的预测精度。CN、TCN、TF_CN仅考虑了二阶邻居数目，在AUC评价标准下结果普遍一般，但在MAN中，CN明显高于AA、RA和全局指标LP，预测效果仅次于本文的指标，TCN也优于TAA、TRA、TLP；而加入时间因素的拓展指标性能没有展示出优势，性能表现整体不如传统指标，造成此现象的原因是MAN数据集动态特性不明显，考虑时间因素的拓展方法无法发挥性能优势。在MAN数据集中，CN指标优势明显，说明此数据集局部特征明显，局部指标可发挥出性能优势，而考虑共同邻居的AA、RA不及CN，说明该数据集共同邻居特征不明显。AA、RA及其拓展指标考虑了共同邻居节点度，也表现出了不错的预测效果，在DNC、LEM、EEC1、EEC2这4个网络中预测效果明显优于CN。而考虑全局信息的LP及其拓展方法TLP、TF_LP，在大部分网络中表现出了较高的预测精度，甚至在EEC2网络中，LP、TLP的AUC得分强于TMDN，加入时间因子，将网络的动态信息考虑进来，全局方法TF_LP明显高于局部方法TF_CN、TF_AA和TF_RA。整体而言，拓展方法表现优于传统方法，具体到数据集中表现却参差不齐，这是由于动态特性只是动态网络的一个特征，还要考虑其局部特征和全局特征等多个因素，在一些动态特性较高的网络中，会出现拓展方法低于传统方法的现象，所以，算法的普适性也是衡量指标性能的重要标准。

表1 5个真实数据集的基本特征参数

在考虑节点匹配度后，TMDN预测效果明显领先，说明现实网络连边构建中均存在一定程度的匹配倾向性。同样考虑共同邻居间存在的社团关系，TMDN在5个网络中的预测效果均优于局部相似性方法及拓展方法TCN、TF_CN、TAA、TF_AA、TRA、TF_RA，且提升精度在1%～33%。相比全局方法LP、TLP、TF_LP，在DNC、MAN、LEM中同样有较高的提升，提升比例为1%～42%，但在EEC2中，本文的方法效果不如LP和TLP。总体上，相比其他方法，TMDN方法的平均提升比率为19.3%，最高提升比例为42%。

图5 不同方法的平均AUC性能

Figure 5 Average AUC performance of different methods

4.1.2 RS评价方法

本节在RS衡量标准下对TMDN的性能进行对比分析。图6为TMDN与其他方法在5个真实网络中的RS对比结果。

图6 不同方法的平均RS性能对比

Figure 6 Comparison of average RS performance of different methods

相比其他相似性方法，本文所提TMDN在5个网络中均有较优的性能。与AUC结果不同，局部相似性方法及拓展方法在不同网络中表现各异，某些网络中CN表现较好，而在另一些网络中则表现较差。考虑共同邻居节点度的AA、RA方法，在AUC衡量标准下展现出了一定的优势，而在RS衡量标准下却表现出了较差的性能，仅在LEM中预测性能高于CN。在大部分网络中，结合时间因素的局部拓展方法性能较传统方法有所提升，这说明在动态网络中，传统方法可能会忽略网络结构的动态特性，导致预测结果不佳。而这些局部方法性能表现各异，说明共同邻居节点本身信息的利用对于刻画动态网络结构特征的贡献难以界定，像AA、RA这些考虑了邻居节点度的额外因素并非一定会起到正面促进作用。全局指标LP、TLP、TF_LP在一些网络中表现出了较为稳定的预测性能，但在MAN中LP和TLP的预测效果却最差，说明基于全局信息的方法难以概述动态网络的全部属性，导致预测性能存在未知性。

TMDN方法在5个网络中均表现出较好的性能，RS得分普遍低于其他指标。在DNC和MAN网络中性能提升明显，相比其他指标，TMDN的预测性能最高提升了49.6%，在DNC中，TF_RA展现出了不俗的预测精度，RS得分甚至低于TMDN，但也仅仅低0.01。在其他3个网络中，TMDN提升幅度不大，但RS得分低于其他任何指标，性能提升幅度在1%～27%。总体上，TMDN指标表现出了更加稳定的预测性能，RS结果平均提升幅度为16.5%，最高提升幅度为49.6%。

4.2 参数对性能的影响分析

图7 不同方法关于参数的性能曲线

图8 不同方法随时间的AUC性能曲线

图9 不同方法随时间的RS性能曲线

4.3 不同时刻t的性能对比

图8是AUC评价标准下各方法随时间变化的性能曲线；图9是RS评价标准下各方法随时间变化的性能曲线。

从不同方法随时间的AUC性能曲线中可以看出，整体而言，TMDN方法的性能优于其他拓展指标，尤其是优于基于时间序列的拓展方法。通过不同时刻的AUC对比实验中，同样考虑时间影响因素的不同方法能表现出不一致的变化趋势，这说明时间衰减因子能准确描绘时间影响特征，更验证了所提算法的普适性和全面性，不仅考虑网络拓扑的局部信息，也考虑了拓扑信息的三阶路径；而相对加入时间衰减因子的拓展指标，本文方法展现出了较好的预测性能，主要是因为本文方法更加详细和全面地考虑网络拓扑的信息。

各指标在5个网络中的性能表现不太稳定，说明这些方法虽然针对不同的网络可以表现出比较好的预测效果，但普适性和稳定性远远不如TMDN方法。在5个网络中，TMDN的RS得分最高降低了58%，在这几个网络中普遍降低3%～58%。

4.4 时间复杂度分析

其中，为方法的运行时间。

Figure 10 Comparison of time consumption of different methods

从运行时间归一化对比图可看出，本文所提TMDN指标在提升性能的同时并未增加太多运行时间。

5 结束语

动态网络上的链路预测问题近年来受到网络科学领域学者的广泛关注。针对真实网络中连边的形成存在偏好性这一现象，结合网络节点自身属性特征，本文提出一种基于节点匹配度的动态网络链路预测方法。该方法首先定义了衡量节点重要性的原生影响力和次生影响力方法；随后，将节点重要性与时间衰减因子相结合，提出用于动态网络链路预测的节点匹配度方法。在多个真实网络中的实验结果表明，所提TMDN方法相比现有方法在AUC和RS评价标准下均表现出更优的预测效果，验证了节点间匹配程度对动态网络连边形成的影响。所提方法实现简单，计算复杂度较低，可推广至超大规模动态网络上的链路预测场景。今后的研究中，可不局限于对网络拓扑的局部结构化研究，通过加入多样化的特征信息，对动态真实网络作进一步深层次分析可对更准确预测出其演化规律，具有现实研究意义。

[1] MCGLOIN J M, KIRK D S. Social network analysis[M]. Springer TMDN York, 2010.

[2] CUI Y, CAI M, DAI Y, et al. A hybrid network-based method for the detection of disease-related genes[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 389-394.

[3] SLAVIN S. Medical student mental health: challenges and opportunities[J]. Medical Science Educator, 2018, 28(1): 13-15.

[4] SHANMUKHAPPA T, HO I W H, TSE C K. Spatial analysis of bus transport networks using network theory[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 502: 295-314.

[5] 刘树新, 季新生, 刘彩霞, 等. 一种信息传播促进网络增长的网络演化模型[J]. 物理学报, 2014, 63(15): 429-439.

LIU S X, JI X S, LIU C X, et al. A complex network evolution model for network growth promoted by information transmission[J]. Acta Physica Sinica, 2014, 63(15): 429-439.

[6] ROLI A, VILLANI M, FILISETTI A, et al. Dynamical criticality: overview and open questions[J]. Journal of Systems Science and Complexity, 2018, 31(3): 647-663.

[7] SCELLATO S, NOULAS A, MASCOLO C. Exploiting place features in link prediction on location-based social networks[C]//Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 2011: 1046-1054.

[8] KERRACHE S, ALHARBI R, BENHIDOUR H. A scalable similarity-popularity link prediction method[J]. Scientific Reports, 2020, 10: 6394.

[9] WANG Y C, WANG Y, LIN X Y, et al. The influence of network structural preference on link prediction[J]. Discrete Dynamics in Nature and Society, 2020, 2020: 1-9.

[10] HISANO R. Semi-supervised graph embedding approach to dynamic link prediction[J]. CoRR, 2016, abs/1610.04351.

[11] 吕琳媛. 复杂网络链路预测[J]. 电子科技大学学报, 2010, 39(5): 651-661.

LYU L Y. Link prediction on complex networks[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(5): 651-661.

[12] VON MERING C, JENSEN L J, SNEL B, et al. STRING: known and predicted protein-protein associations, integrated and transferred across organisms[J]. Nucleic Acids Research, 2005, 33(suppl_1): D433-D437.

[13] SARKAR P, CHAKRABARTI D, JORDAN M. Nonparametric link prediction in large scale dynamic networks[J]. Electronic Journal of Statistics, 2014, 8(2): 2022–2065.

[14] 吕琳媛, 任晓龙, 周涛. 网络链路预测: 概念与前沿[J]. 中国计算机学会通讯, 2016, 12(4): 12-19.

LYU L Y, REN X L, ZHOU T. Network link prediction: concept and frontier[J]. Communications of CCF, 2016, 12(4): 12-19.

[15] AHMED N M, CHEN L. An efficient algorithm for link prediction in temporal uncertain social networks[J]. Information Sciences, 2016, 331: 120-136.

[16] GÜNEŞİ, GÜNDÜZ-ÖĞÜDÜCÜ Ş, ÇATALTEPE Z. Link prediction using time series of neighborhood-based node similarity scores[J]. Data Mining and Knowledge Discovery, 2016, 30(1): 147-180.

[17] AHMED N M, CHEN L, WANG Y L, et al. Sampling-based algorithm for link prediction in temporal networks[J]. Information Sciences, 2016, 374: 1-14.

[18] SETT N, BASU S, NANDI S, et al. Temporal link prediction in multi-relational network[J]. World Wide Web, 2018, 21(2): 395-419.

[19] 陈敏, 崔大方, 黄平, 等. 3种乡土水生植物对富营养化水体净化能力比较[J]. 安徽农业科学, 2019, 47(7): 63-65, 69.

CHEN M, CUI D F, HUANG P, et al. Comparison of purification ability of three native aquatic plants to eutrophic water bodies[J]. Journal of Anhui Agricultural Sciences, 2019, 47(7): 63-65, 69.

[20] CROMIE G, COLLINS J, LEACH D. Sequence interruptions in enterobacterial repeated elements retain their ability to encode well-folded RNA secondary structures[J]. Molecular Microbiology, 1997, 24(6): 1311-1314.

[21] 严丽军. 自然灾害的灾情信息集成：理论与实证研究[D]. 上海: 上海师范大学, 2016.

YAN L J. Disaster information integration of natural disasters: theoretical and empirical research. Shanghai: Shanghai Normal University, 2016.

[22] 苗会强, 刘会平, 范九生, 等. 汶川地震次生灾害的成因、成灾与治理[J]. 地质灾害与环境保护, 2008, 19(4): 1-5.

MIAO H Q, LIU H P, FAN J S, et al. Secondary disasters, hazard chains and the curing in Wenchuan earthquake-hit area, West China[J]. Journal of Geological Hazards and Environment Preservation, 2008, 19(4): 1-5.

[23] 陈嘉颖, 于炯, 杨兴耀, 等. 基于复杂网络节点重要性的链路预测算法[J]. 计算机应用, 2016, 36(12): 3251-3255, 3268.

CHEN J Y, YU J, YANG X Y, et al. Link prediction algorithm based on node importance in complex networks[J]. Journal of Computer Applications, 2016, 36(12): 3251-3255, 3268.

[24] LIU F X, YANG H, WANG L M, et al. Biosynthesis of the high-value plant secondary product benzyl isothiocyanate via functional expression of multiple heterologous enzymes in escherichia coli[J]. ACS Synthetic Biology, 2016, 5(12): 1557-1565.

[25] 杨育捷. 复杂网络下基于拓扑相似性的链路预测研究[D]. 北京: 北京邮电大学, 2019.

YANG Y J. Research on link prediction based on topological similarity in complex networks[D]. Beijing: Beijing University of Posts and Telecommunications, 2019.

[26] VÁZQUEZ A. Growing network with local rules: preferential attachment, clustering hierarchy, and degree correlations[J]. Physical Review E, 2003, 67(5): 056104.

[27] MUBAYI D. Structure and stability of triangle-free set systems[J]. Transactions of the American Mathematical Society, 2007, 359(1): 275-291.

[28] WANG X Y, CAO J Y, QIN X M. Study of robustness in functionally identical coupled networks against cascading failures[J]. PLoS One, 2016, 11(8): e0160545.

[29] 刘树新, 李星, 陈鸿昶, 等. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020, 41(6): 70-79.

LIU S X, LI X, CHEN H C, et al. Link prediction method based on matching degree of resource transmission for complex network[J]. Journal on Communications, 2020, 41(6): 70-79.

[30] ÖZCAN A, ÖĞÜDÜCÜ Ş G. Supervised temporal link prediction using time series of similarity measures[C]//Proceedings of 2017 Ninth International Conference on Ubiquitous and Future Networks (ICUFN). 2017: 519-521.

[31] LORRAIN F, WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology, 1971, 1(1): 49-80.

[32] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3): 211-230.

[33] OU Q, JIN Y D, ZHOU T, et al. Power-law strength-degree correlation from resource-allocation dynamics on weighted networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2007, 75(2): 021102.

[34] LYU L, JIN C H, ZHOU T. Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2009, 80(4): 046122.

[35] DA SILVA SOARES P R, PRUDÊNCIO R B C. Time series based link prediction[C]//Proceedings of 2012 International Joint Conference on Neural Networks (IJCNN). 2012: 1-7.

[36] KUNEGIS J. KONECT: the Koblenz network collection[C]// Proceedings of the 22nd International Conference on World Wide Web - WWW '13 Companion. 2013: 1343-1350.

[37] Batagelj V, Mrvar A. Pajek Datasets[EB/OL].

[38] PARANJAPE A, BENSON A R, LESKOVEC J. Motifs in temporal networks[C]//Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. 2017: 601-610.

Link prediction method for dynamic networks based on matching degree of nodes

LI Cong, JI Xinsheng, LIU shuxin, LI Jinsong, LI Haitao

Information Engineering University, Zhengzhou 450001, China

The research of dynamic evolutionary trends and temporal characteristics in real networks which are important part of the real world is a hot research issue nowadays. As a typical research tool in the field of network science, link prediction technique can be used to predict the network evolution by mining the historical edge information and then predict the future edge. The topological evolution of dynamic real networks was analyzed and it found that the interaction and matching between nodes in the network topology can capture the dynamic characteristics of the network more comprehensively. The proposed method analyzed the attribute characteristics of network nodes, and defined a node importance quantification method based on primary and secondary influences. Besides, a time decay factor was introduced to portray the influence of network topology on the formation of connected edges at different moments. Furthermore, the node importance and time decay factor were combined to define the Temporal Matching Degree of Nodes (TMDN), which was used to measure the possibility of future edge formation between node pairs. The experimental results in five real dynamic network datasets showed that the proposed method achieves better prediction performance under both AUC and Ranking Score, with a maximum improvement of 42%. It also proved the existence of interactive matching priority among nodes, and confirmed the effectiveness of both primary and secondary influence of nodes. As the future work, we will add diversified feature information to further deepen the analysis of dynamic real networks and then predict the evolution law more accurately.

dynamic networks, link prediction, matching degree of nodes, node importance, time decaying parameter

The National Natural Science Foundation of China (61803384)

李聪, 季新生, 刘树新, 等. 基于节点匹配度的动态网络链路预测方法[J]. 网络与信息安全学报, 2022, 8(4):131-143.

TP393

A

10.11959/j.issn.2096−109x.2022053

李聪（1996−），男，山东菏泽人，信息工程大学硕士生，主要研究方向为复杂网络、链路预测、网络安全。

季新生（1969−），男，河南驻马店人，信息工程大学教授、博士生导师，主要研究方向为通信网架构、内生安全、复杂网络。

刘树新（1987−），男，山东临沂人，信息工程大学助理研究员，主要研究方向为复杂网络、链路预测、社交网络分析等。

李劲松（1992−），男，山东泰安人，信息工程大学博士生，主要研究方向为复杂网络、链路预测、大数据挖掘、网络安全。

李海涛（1982−），男，山东泰安人，信息工程大学副研究员，主要研究方向通信网安全、数据处理和嵌入式设计。

2021−01−05；

2021−05−04

季新生，jixinsheng@ndsc.com.cn

国家自然科学基金（61803384）

LI C, JI X S, LIU S X, et al. Link prediction method for dynamic networks based on matching degree of nodes[J]. Chinese Journal of Network and Information Security, 2022, 8(4): 131-143.