基于神经网络的链路预测算法

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

网络与信息安全学报 ›› 2018, Vol. 4 ›› Issue (7): 30-38.doi: 10.11959/j.issn.2096-109x.2018049

基于神经网络的链路预测算法

潘永昊,于洪涛,刘树新

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

修回日期:2018-06-01 出版日期:2018-07-01 发布日期:2018-09-10
作者简介:潘永昊（1992-），男，甘肃金昌人，国家数字交换系统工程技术研究中心硕士生，主要研究方向为复杂网络、链路预测。|于洪涛（1970-），男，辽宁丹东人，博士，国家数字交换系统工程技术研究中心研究员，主要研究方向为网络大数据分析与处理。|刘树新（1987-），男，山东潍坊人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为复杂网络、网络信息挖掘。
基金资助:
国家自然科学基金创新研究群体基金资助项目(61521003);国家自然科学基金资助项目(61601513)

Neural network-based link prediction algorithm

Yonghao PAN,Hongtao YU,Shuxin LIU

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

Revised:2018-06-01 Online:2018-07-01 Published:2018-09-10
Supported by:
The Innovative Research Groups of the National Natural Science Foundation of China(61521003);The National Natural Science Foundation of China(61601513)

摘要/Abstract

摘要：

针对当前基于网络拓扑结构相似性的链路预测算法普遍存在精确度较低且适应性不强的问题，研究发现融合算法能够有效改善这些问题。提出了一种基于神经网络的融合链路预测算法，主要通过神经网络对不同链路预测相似性指标进行融合。该算法使用神经网络对不同相似性指标的数值特征进行学习，同时采用标准粒子群算法对神经网络进行了优化，并通过优化学习后的神经网络模型计算出融合指标。多个真实网络数据集上实验表明，该算法的预测精度明显高于融合之前的各项指标，并且优于现有融合方法的精度。

关键词: 复杂网络, 链路预测, 神经网络, BP算法

Abstract:

To improve the difference existed in the link prediction accuracy and adaptability of different topology structure similarity based methods,a neural network-based link prediction algorithm,which fused similarity indices by neural network was proposed.The algorithm uses neural network to study the numerical characteristics of different similarity indices,and uses particle swarm optimization to optimize the neural network,and calculates the fusion index by the optimized neural network model.The experiment on the real network data set shows that the prediction accuracy of the algorithm is obviously higher than that before the fusion,and the accuracy is better than the existing methods.

Key words: complex network, link prediction, neural network, back propagation algorithm

中图分类号:

潘永昊,于洪涛,刘树新. 基于神经网络的链路预测算法[J]. 网络与信息安全学报, 2018, 4(7): 30-38.

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.

图/表 6

表1

表2

NNLP算法和各结构相似性指标在数据集中的AUC值"

算法	AUC值
算法	NS	PB	USAir	CE	Jazz	Yeast
CN	0.9657	0.9225	0.9581	0.8248	0.9514	0.9082
PA	0.7400	0.9093	0.9260	0.7507	0.7674	0.8649
AA	0.9658	0.9238	0.9689	0.8408	0.9591	0.9084
Katz	0.9800	0.9329	0.9506	0.8493	0.9409	0.9697
NNLP	$0 . 9998$	$0 . 9453$	$0 . 9807$	$0 . 9024$	$0 . 9766$	$0 . 9814$

表2

表3

NNLP算法和各结构相似性指标在数据集中的precision值"

算法	precision值
算法	NS	PB	USAir	CE	Jazz	Yeast
CN	0.495	0.178	0.389	0.101	0.507	0.151
PA	0.039	0.066	0.328	0.062	0.135	0.095
AA	0.508	0.177	0.404	0.103	0.522	0.175
Katz	0.478	0.176	0.381	0.105	0.446	0.256
NNLP	$0 . 516$	$0 . 185$	$0 . 413$	$0 . 134$	$0 . 543$	$0 . 265$

表3

表4

NNLP算法、LPEOWA算法和各指标在数据集中的AUC值"

算法	AUC值
算法	NS	PB	UsAir	CE	Jazz	Yeast
CN	0.969 1	0.919 1	0.950 7	0.829 7	0.952 5	0.909 8
PA	0.737 6	0.911 6	0.918 3	0.752 8	0.766 5	0.866 4
AA	0.969 6	0.922 4	0.956 7	0.845 8	0.946 4	0.911 2
Katz	0.980 8	0.930 4	0.950 9	0.855 6	0.938 7	0.970 6
LPE_OWA	0.981 9	0.941 7	0.966 7	0.867 9	0.960 8	0.972 9
NNLP	0.999 8	0.945 3	0.980 7	0.902 4	0.975 3	$0 . 9814$

表4

表5

表6

参考文献 24

[1]	Lü 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-1613.
[3]	KOSSINETS G . Effects of missing data in social network[J]. Social Networks, 2006,28(3): 247-268.
[4]	ESSLIMAMI I , BRUN A , BOYER A . Densifying a behavioral recommender system by social networks link prediction methods[J]. Social Network Analysis and Mining, 2011,1(3): 159-172.
[5]	刘树新, 季新生, 刘彩霞 ,等. 一种信息传播促进网络增长的网络演化模型[J]. 物理学报, 2014,63(15).
	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).
[6]	刘树新, 季新生, 刘彩霞 ,等. 局部拓扑信息耦合促进网络演化[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.
[7]	ZHOU C , MOTTER A E , KURTHS J . Universality in the synchronization of weighted random networks[J]. Physical Review Letters, 2006,96(3):034101.
[8]	FIRTUNATO S . Community detection in graph[J]. Physics Reports, 2010,486(3): 75-174.
[9]	黄立威, 李德毅, 马于涛 ,等. 一种基于元路径的异质信息网络链路预测模型[J]. 计算机学报, 2014,37(4): 848-858.
	HUANG L W , LI D Y , MA Y T ,et al. A meta path-based link prediction model for heterogeneous information networks[J]. Chinese Journal of Computers, 2014,37(4): 848-858.
[10]	王守辉, 于洪涛, 黄瑞阳 ,等. 基于模体演化的时序链路预测方法[J]. 自动化学报, 2016,42(5): 735-745.
	WANG S H , YU H T , HUANG R Y ,et al. A temporal link prediction method based on motifevolution[J]. Acta Automatica Sinica, 2016,42(5): 735-745.
[11]	MITZENMACHER M . A brief history of generative models for power law and lognormal distributions[J]. Internet Mathematics, 2004,1(2): 226-251.
[12]	ADAMIC L A , Adar E . Friends and neighbors on the Web[J]. Social Networks, 2003,25(3): 211-230.
[13]	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, 2007,75(2).
[14]	BARABáSI A L , Albert R . Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512.
[15]	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.
[16]	KATZ L . A new status index derived from sociometric index[J]. Psychometrika, 1953,18(1): 39-43.
[17]	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.
[18]	HE Y , LIU J N K , HU Y ,et al. OWA operator based link prediction ensemble for social network[J]. Expert Systems with Applications, 2015,42(1): 21-50.
[19]	GAO F , MUSIAL K , COOPER C ,et al. Link prediction methods and their accuracy for different social networks and network metrics[J]. Scientific Programming, 2014,501: 172879.
[20]	吴祖峰, 梁棋, 刘峤 ,等. 基于 AdaBoost 的链路预测优化算法[J]. 通信学报, 2014,35(3): 116-123.
	WU Z F , LIANG Q , LIU Q ,et al. Modified link prediction algorithm based on AdaBoost[J]. Journal on Communications, 2014,35(3): 116-123.
[21]	YU H T , WANG S H , MA Q Q . Link prediction algorithm based on the Choquet fuzzy integral[J]. Journal on Communications, 2016,20(4): 809-824.
[22]	吕琳媛, 周涛 . 链路预测[M]. 北京: 高等教育出版社, 2013: 46-47.
	LYU L Y , ZHOU T . Link prediction[M]. Beijing: High Education Press, 2013.
[23]	BRITS R , ENGELBRECHT A P ,et al. A niching particle swarm optimizer[C]// The 4th Asia-Pacific conference on simulated evolution and learning,Singapore, 2002, 692-696.
[24]	HECHT-NIELSEN R , . Theory of the backpropagation neural network[C]// International Joint Conference on Neural Networks, 1989,1(1): 593-605.

网络	\|V\|	\|E\|	<k>	<d>	C	r	H
NS	1461	2742	3.75	5.82	0.878	0.461	1.85
PB	1222	16717	27.36	2.51	0.360	?0.221	2.970
Jazz	198	2742	27.7	2.24	0.633	0.02	1.4
CE	453	2025	8.94	2.66	0.655	?0.225	4.49
USAir	332	2128	12.81	2.74	0.749	?0.208	3.36
Yeast	2 370	10 904	9.2	5.16	0.378	0.469	3.35

基于神经网络的链路预测算法

Neural network-based link prediction algorithm

在线阅读

pdf下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 24

相关文章 15

Metrics

推荐阅读 0

[1]	陈立全, 朱宇航, 王宇, 秦中元, 马旸. 基于混沌神经网络和C-MD结构的带密钥哈希函数[J]. 网络与信息安全学报, 2023, 9(3): 1-15.
[2]	冯冠云, 付才, 吕建强, 韩兰胜. 基于操作注意力和数据增强的内部威胁检测[J]. 网络与信息安全学报, 2023, 9(3): 102-112.
[3]	蔡召, 荆涛, 任爽. 以太坊钓鱼诈骗检测技术综述[J]. 网络与信息安全学报, 2023, 9(2): 21-32.
[4]	侯泽洲, 任炯炯, 陈少真. 基于神经网络区分器的SIMON-like算法参数安全性评估[J]. 网络与信息安全学报, 2023, 9(2): 154-163.
[5]	朱宇航, 吉立新, 李英乐, 李海涛, 刘树新. 基于社团多特征融合嵌入表示的时序链路预测方法[J]. 网络与信息安全学报, 2023, 9(1): 67-82.
[6]	谢绒娜, 马铸鸿, 李宗俞, 田野. 基于卷积神经网络的加密流量分类方法[J]. 网络与信息安全学报, 2022, 8(6): 84-91.
[7]	单棣斌, 杜学绘, 王文娟, 刘敖迪, 王娜. 基于GNN双源学习的访问控制关系预测方法[J]. 网络与信息安全学报, 2022, 8(5): 40-55.
[8]	陈浩, 王锋, 张卫明, 俞能海. 载体独立的深度光照水印算法[J]. 网络与信息安全学报, 2022, 8(4): 110-118.
[9]	李聪, 季新生, 刘树新, 李劲松, 李海涛. 基于节点匹配度的动态网络链路预测方法[J]. 网络与信息安全学报, 2022, 8(4): 131-143.
[10]	林点, 潘理, 易平. 面向图像识别的卷积神经网络鲁棒性研究进展[J]. 网络与信息安全学报, 2022, 8(3): 111-122.
[11]	王馨雅, 华光, 江昊, 张海剑. 深度学习模型的版权保护研究综述[J]. 网络与信息安全学报, 2022, 8(2): 1-14.
[12]	石灏苒, 吉立新, 刘树新, 王庚润. 基于半局部结构的异常连边识别算法[J]. 网络与信息安全学报, 2022, 8(1): 63-72.
[13]	乔通, 姚宏伟, 潘彬民, 徐明, 陈艳利. 基于深度学习的数字图像取证技术研究进展[J]. 网络与信息安全学报, 2021, 7(5): 13-28.
[14]	王正龙, 张保稳. 生成对抗网络研究综述[J]. 网络与信息安全学报, 2021, 7(4): 68-85.
[15]	李炳龙, 佟金龙, 张宇, 孙怡峰, 王清贤, 常朝稳. 基于TensorFlow的恶意代码片段自动取证检测算法[J]. 网络与信息安全学报, 2021, 7(4): 154-163.