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

Cong LI; Xinsheng JI; Ushuxin LI; Jinsong LI; Haitao LI

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

您当前的位置：

首页 >

文章列表页 >

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

Papers | 更新时间：2024-06-03

- Link prediction method for dynamic networks based on matching degree of nodes
- Chinese Journal of Network and Information Security Vol. 8, Issue 4, Pages: 131-143(2022)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2022053
  CLC： TP393
- Online First：2022-08，
  
  Published：15 August 2022
- 稿件说明：
移动端阅览
Cong LI, Xinsheng JI, Ushuxin LI, 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.
DOI：

Cong LI, Xinsheng JI, Ushuxin LI, 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. DOI： 10.11959/j.issn.2096-109x.2022053.

摘要

现实世界存在众多真实网络，研究真实网络中的动态演化趋势和时序性特征是热点问题。链路预测技术作为网络科学领域重要研究工具可通过挖掘历史连边信息推测网络演化规律，进而对未来连边进行预测。通过分析动态真实网络中的拓扑结构演化，发现通过分析网络拓扑中节点间的交互性和匹配度问题能够更充分捕捉网络的动态特征，提出一种基于节点匹配度的动态网络链路预测方法。该方法对网络节点的属性特征进行分析，定义基于原生影响力和次生影响力的节点重要性量化方法；引入时间衰减因子，刻画不同时刻网络拓扑对连边形成的影响程度；结合节点重要性和时间衰减因子定义动态节点匹配度（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.

关键词

Keywords

references

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

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 .

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

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 .

刘树新 , 季新生 , 刘彩霞 , 等 . 一种信息传播促进网络增长的网络演化模型 [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 .

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 .

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 .

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

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 .

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

吕琳媛 . 复杂网络链路预测 [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 .

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 .

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

吕琳媛 , 任晓龙 , 周涛 . 网络链路预测:概念与前沿 [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 .

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

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 .

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 .

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

陈敏 , 崔大方 , 黄平 , 等 . 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 .

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 .

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

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

苗会强 , 刘会平 , 范九生 , 等 . 汶川地震次生灾害的成因、成灾与治理 [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 .

陈嘉颖 , 于炯 , 杨兴耀 , 等 . 基于复杂网络节点重要性的链路预测算法 [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 .

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 .

杨育捷 . 复杂网络下基于拓扑相似性的链路预测研究 [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 .

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

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

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 .

刘树新 , 李星 , 陈鸿昶 , 等 . 基于资源传输匹配度的复杂网络链路预测方法 [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 .

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

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

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

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 .

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 .

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 .

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

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

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 .

Views

134

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Hypernetwork link prediction method based on the SCL-CMM model

Deep learning-based method for mobile social networks with strong sparsity for link prediction

Link prediction methods based on generalized common neighbor in directed network

Link prediction method based on complex network dynamics model

New method for link prediction in directed networks based on triad patterns

Related Author

WANG Kai

LIU Shuxin

MA Hong

REN Yuyuan

LIU Linfeng

HE Yadi

Xuelei ZHAO

Yu ZHAO

Related Institution

Information Engineering University

School of Computer Science, Nanjing University of Posts and Telecommunications

⁰