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

doi:10.11959/j.issn.2096-109x.2022053

摘要/Abstract

摘要：

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

关键词: 动态网络, 链路预测, 节点匹配度, 节点重要性, 时间衰减因子

Abstract:

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.

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

中图分类号:

TP393

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

Cong LI, Xinsheng JI, Ushuxin LI, Jinsong LI, Haitao LI. 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.

图/表 11

图1

图2

图3

图4

表1

图5

图6

图7

图8

图9

图10

参考文献 38

[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[D]. 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.

数据集名称	节点数	连边数	平均度	起始日期	结束日期	总时长	网络快照时长	网络快照数	窗口长度
DNC	2 029	39 264	19.35	2016/4/25	2016/5/23	29天	1天	29	10
MAN	167	82 927	496.57	2010/1/3	2010/9/27	268天	7天	39	10
LEM	485	196 364	809.75	1979/4/1	2004/6/1	302月	6月	50	10
EEC1	309	34 041	60546	1970/1/1	1971/6/9	525天	7天	75	10
EEC2	162	46 272	554.17	1970/3/17	1971/6/8	524天	7天	75	10