基于复杂网络动力学模型的链路预测方法

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

网络与信息安全学报 ›› 2019, Vol. 5 ›› Issue (6): 67-74.doi: 10.11959/j.issn.2096-109x.2019065

基于复杂网络动力学模型的链路预测方法

潘永昊(),于洪涛,吴翼腾

国家数字交换系统工程技术研究中心，河南郑州 450002

修回日期:2019-03-20 出版日期:2019-12-15 发布日期:2019-12-14
作者简介:潘永昊（1992- ），男，甘肃金昌人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为复杂网络、链路预测|于洪涛（1970- ），男，辽宁丹东人，博士，国家数字交换系统工程技术研究中心研究员，主要研究方向为网络大数据分析与处理|吴翼腾（1992- ），男，山东乐陵人，国家数字交换系统工程技术研究中心博士生，主要研究方向为复杂网络链路预测、对抗样本等
基金资助:
国家自然科学基金资助项目(61803384)

Link prediction method based on complex network dynamics model

Yonghao PAN(),Hongtao YU,Yiteng WU

National Digital Switching System Engineering and Technological R＆D Center,Zhengzhou 450002,China

Revised:2019-03-20 Online:2019-12-15 Published:2019-12-14
Supported by:
The National Natural Science Foundation of China(61803384)

摘要/Abstract

摘要：

链路预测是复杂网络中研究缺失连边和未来形成连边的重要组成部分，当前基于网络结构的链路预测方法成果丰富，而基于复杂网络动力学模型的链路预测研究较少。针对无权无向网络，首先构建了复杂网络动力学模型，然后给出了基于复杂网络动力学模型的链路预测节点中心性的量化评价指标，最后通过给出的节点中心性量化指标，提出了由复杂网络动力学模型定义的链路预测方法。通过在真实网络数据集上进行的实验表明，提出的链路预测方法较基准方法有明显的预测精度的提升。

关键词: 复杂网络, 链路预测, 网络动力学

Abstract:

Link prediction is an important part of the study of missing links and future formations in complex networks.Currently,network structure-based link prediction methods are rich in results.Research on link prediction based on complex network dynamics model is rare.Firstly,a complex network dynamics model for unlicensed and undirected networks was constructed.Then the quantitative evaluation index of the link prediction node centrality based on the complex network dynamics model was given.Finally,the link prediction method defined by the complex network dynamics model was proposed by the given node centrality quantitative index.Experiments on real network datasets show that the proposed link prediction method has obvious prediction accuracy improvement.

Key words: complex network, link prediction, network dynamics

中图分类号:

TP393

潘永昊,于洪涛,吴翼腾. 基于复杂网络动力学模型的链路预测方法[J]. 网络与信息安全学报, 2019, 5(6): 67-74.

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.

图/表 5

表1

表2

表3

表4

表5

参考文献 28

[1]	LYU L , ZHOU T . Link prediction in complex networks:a survey[J]. Physica A:Statistical Mechanics and its Applications, 2011,390(6): 1150-1170.
[2]	CANNISTRACI C V , ALANISLOBATO G , RAVASI T . From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Scientific Reports, 2015,3(4):1613.
[3]	KOSSINETS G . Effects of missing data in social network[J]. Social Networks, 2006,28(3): 247-268.
[4]	刘树新, 季新生, 刘彩霞 ,等. 一种信息传播促进网络增长的网络演化模型[J]. 物理学报, 2014,63(15): 158902-158902.
	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 Phys.Sin, 2014,63(15): 158902-158902.
[5]	刘树新, 季新生, 刘彩霞 ,等. 局部拓扑信息耦合促进网络演化[J]. 电子与信息学报, 2016,38(9): 2180-2187.
	LIU S X , JI X S , LIU C X ,et al. Information coupling of local topology promoting the network evolution[J]. Journal of Electronics ＆ Information Technology, 2016,38(9): 2180-2187.
[6]	MITZENMACHER M . A brief history of generative models for power law and lognormal distributions[J]. Internet Mathematics, 2004,1(2): 226-251.
[7]	KATZ L . A new status index derived from sociometric index[J]. Psychometrika, 1953,18(1): 39-43.
[8]	CLAUSET A , MOORE C , NEWMAN M E . Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008,453(7191):98.
[9]	LIU S , JI X , LIU C ,et al. Extended resource allocation index for link prediction of complex network[J]. Physica A Statistical Mechanics ＆ Its Applications, 2017,479: 174-183.
[10]	YU H T , WANG S H , MA Q Q . Link prediction algorithm based on the Choquet fuzzy integral[J]. Intelligent Data Analysis, 2016,20(4): 809-824.
[11]	SAMANTA S , Pal M . Link prediction in social networks[J]. Springer Briefs in Computer Science, 2018: 246-250.
[12]	LU Y , GUO Y , KORHONEN A . Link prediction in drug-target interactions network using similarity indices[J]. Bmc Bioinformatics, 2017,18(1):39.
[13]	LIU S , JI X , LIU C ,et al. Similarity indices based on link weight assignment for link prediction of unweighted complex networks[J]. International Journal of Modern Physics B, 2017,31(2): 412-1054.
[14]	任晓龙, 吕琳媛 . 网络重要节点排序方法综述[J]. 科学通报, 2014,59(13): 1175-1197.
	REN X L , LYU L Y . Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014,59(13): 1175-1197.
[15]	ADAMIC L A , ADAR E . Friends and neighbors on the Web[J]. Social Networks, 2003,25(3): 211-230.
[16]	RAVASZ E , SOMERA A L , MONGRU D A ,et al. Hierarchical organization of modularity in metabolic networks[J]. Science, 2002,297(5586): 1551-1555.
[17]	LIU Y Y , SLOTINE J J , BARABASI A L . Controllability of complex networks[J]. Nature, 2011,473(7346): 167-173.
[18]	JIA T , BARABáSI A L . Control capacity and a random sampling method in exploring controllability of complex networks[J]. Scientific Reports, 2013,3:2354.
[19]	孔江涛, 黄健, 龚建兴 ,等. 基于复杂网络动力学模型的无向加权网络节点重要性评估[J]. 物理学报, 2018,67(9): 255-271.
	KONG J T , HUANG J , GONG J X ,et al. Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models[J]. Acta Phys Sin, 2018,67(9): 255-271.
[20]	SALTON G , MCGILL M J . Introduction to modern information retrieval[M]. Auckland: McGraw-HillPress, 1983.
[21]	ZHOU T , LYU L , ZHANG Y C . Predicting missing links via local information[J]. European Physical Journal B, 2009,71(4): 623-630.
[22]	LEICHT E A , HOLME P , NEWMAN M E . Vertex similarity in networks[J]. Physical Review E Statistical Nonlinear ＆ Soft Matter Physics, 2006,73(2):026120.
[23]	ADAMIC L A , ADAR E . Friends and neighbors on the Web[J]. Social Networks, 2003,25(3): 211-230.
[24]	PAN L , ZHOU T , LYU L ,et al. Predicting missing links and identifying spurious links via likelihood analysis[J]. Scientific Reports, 2016,6:22955.
[25]	GLEISER P M , DANON L . Community structure in Jazz[J]. Advances in complex systems, 2003,6(4): 565-573.
[26]	WATTS D J , STROGATZ S H . Collective dynamics of 'small-world' networks[J]. Nature, 1998,393(6684): 440-442.
[27]	BATAGELJ V , MRVAR A . Pajek-program for large network analysis[J]. Connections, 1998,21(2): 47-57.
[28]	ULANOWICZ R E , HEYMANS J J , EGNOTOVICH M S . Network analysis of trophic dynamics in south florida ecosystems,FY 99:the graminoid ecosystem[R]. 2000.

网络	\|V\|	\|E\|	<k>	<d>	C	r
Jazz	198	2 742	27.7	2.24	0.633	0.02
CE	453	2 025	8.94	2.66	0.655	–0.225
USAir	332	2 128	12.81	2.74	0.749	–0.208
FWFB	128	2 075	32.42	1.78	0.335	0.469

方法	Salton	S?renson	HPI	HDI	LHN-I	AA	RA
原始方法	0.968 5	0.963 5	0.954 5	0.952 5	0.905 6	0.964 7	0.978 1
基于复杂网络动力学模型的方法	0.796 3	0.868 0	0.837 0	0.874 7	0.786 6	0.967 5	0.932 9

方法	Salton	S?renson	HPI	HDI	LHN-I	AA	RA
原始方法	0.797 1	0.790 2	0.807 9	0.781 6	0.727 4	0.863 6	0.868 6
基于复杂网络动力学模型的方法	0.862 7	0.852 5	0.862 7	0.847 2	0.851 3	0.862 6	0.867 1

方法	Salton	S?renson	HPI	HDI	LHN-I	AA	RA
原始方法	0.918 9	0.905 6	0.875 9	0.900 2	0.764 5	0.958 4	0.964 8
基于复杂网络动力学模型的方法	0.943 7	0.941 6	0.947 2	0.942 3	0.943 7	0.947 7	0.961 3

方法	Salton	S?renson	HPI	HDI	LHN-I	AA	RA
原始方法	0.517 7	0.514 5	0.523 8	0.515 9	0.393 7	0.601 6	0.603 3
基于复杂网络动力学模型的方法	0.612 7	0.611 2	0.606 3	0.697 3	0.623 2	0.607 2	0.607 9

基于复杂网络动力学模型的链路预测方法

Link prediction method based on complex network dynamics model

在线阅读

pdf下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 28

相关文章 8

Metrics

推荐阅读 0

[1]	朱宇航, 吉立新, 李英乐, 李海涛, 刘树新. 基于社团多特征融合嵌入表示的时序链路预测方法[J]. 网络与信息安全学报, 2023, 9(1): 67-82.
[2]	李聪, 季新生, 刘树新, 李劲松, 李海涛. 基于节点匹配度的动态网络链路预测方法[J]. 网络与信息安全学报, 2022, 8(4): 131-143.
[3]	石灏苒, 吉立新, 刘树新, 王庚润. 基于半局部结构的异常连边识别算法[J]. 网络与信息安全学报, 2022, 8(1): 63-72.
[4]	赵学磊,季新生,刘树新,赵宇. 基于广义共同邻居的有向网络链路预测方法[J]. 网络与信息安全学报, 2020, 6(5): 89-100.
[5]	常圣, 马宏, 刘树新. 基于三元组结构的有向网链路预测方法[J]. 网络与信息安全学报, 2019, 5(5): 39-47.
[6]	吕芳,张新琳,王巍,黄俊恒,王佰玲. 银行账户交易复杂网络特性分析[J]. 网络与信息安全学报, 2019, 5(4): 99-107.
[7]	潘永昊,于洪涛,刘树新. 基于神经网络的链路预测算法[J]. 网络与信息安全学报, 2018, 4(7): 30-38.
[8]	徐欣欣,胡风,仲明,王潮. 基于社会计算的科研合作网络信任图研究[J]. 网络与信息安全学报, 2017, 3(4): 39-50.