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

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

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 11

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

数据集名称	节点数	连边数	平均度	起始日期	结束日期	总时长	网络快照时长	网络快照数	窗口长度
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

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

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 38

Related Articles 5

Metrics

Recommended 0

[1]	Yuhang ZHU, Lixin JI, Yingle LI, Haitao LI, Shuxin LIU. Temporal link prediction method based on community multi-features fusion and embedded representation [J]. Chinese Journal of Network and Information Security, 2023, 9(1): 67-82.
[2]	Xuelei ZHAO,Xinsheng JI,Shuxin LIU,Yu ZHAO. Link prediction methods based on generalized common neighbor in directed network [J]. Chinese Journal of Network and Information Security, 2020, 6(5): 89-100.
[3]	Yonghao PAN,Hongtao YU,Yiteng WU. Link prediction method based on complex network dynamics model [J]. Chinese Journal of Network and Information Security, 2019, 5(6): 67-74.
[4]	Sheng CHANG, Hong MA, Shuxin LIU. New method for link prediction in directed networks based on triad patterns [J]. Chinese Journal of Network and Information Security, 2019, 5(5): 39-47.
[5]	Yonghao PAN,Hongtao YU,Shuxin LIU. Neural network-based link prediction algorithm [J]. Chinese Journal of Network and Information Security, 2018, 4(7): 30-38.