基于高阶路径相似度的复杂网络链路预测方法

doi:10.11959/j.issn.1000-436x.2021055

通信学报 ›› 2021, Vol. 42 ›› Issue (7): 61-69.doi: 10.11959/j.issn.1000-436x.2021055

基于高阶路径相似度的复杂网络链路预测方法

顾秋阳¹^,², 吴宝¹^,², 池仁勇¹^,²

¹ 浙江工业大学管理学院，浙江杭州 310023
² 浙江工业大学中国中小企业研究院，浙江杭州 310023

修回日期:2021-01-27 出版日期:2021-07-25 发布日期:2021-07-01
作者简介:顾秋阳（1995− ），男，浙江杭州人，浙江工业大学博士生，主要研究方向为智能信息处理、数据挖掘、中小企业高质量发展等
吴宝（1979− ），男，浙江金华人，博士，浙江工业大学研究员、博士生导师，主要研究方向为复杂网络链路预测、金融信用风险控制与中小企业发展
池仁勇（1959− ），男，浙江温州人，博士，浙江工业大学教授、博士生导师，主要研究方向为复杂网络链路预测、中小企业智能信息管理与创新创业
基金资助:
国家自然科学基金资助项目(71173194);国家社科基金资助项目(20VYJ073);国家社科基金资助项目(17ZDA088);浙江省社科规划重点基金资助项目(20NDJC10Z)

Link prediction method based on the similarity of high path

Qiuyang GU¹^,², Bao WU¹^,², Renyong CHI¹^,²

¹ School of Management, Zhejiang University of Technology, Hangzhou 310023, China
² China Institute for Small and Medium Enterprises, Zhejiang University of Technology, Hangzhou 310023, China

Revised:2021-01-27 Online:2021-07-25 Published:2021-07-01
Supported by:
The National Natural Science Foundation of China(71173194);The National Social Science Foundation of China(20VYJ073);The National Social Science Foundation of China(17ZDA088);The Social Science Planning Key Foundation of Zhejiang Province(20NDJC10Z)

摘要/Abstract

摘要：

针对目前链路预测方法普遍存在精度不高、效率低等问题，提出了基于高阶路径相似度的复杂网络链路预测方法。首先，利用路径作为判别特征对复杂网络中的缺失链接进行预测，以实现资源的有效分配，并通过惩罚公共近邻对信息泄露进行限制。其次，将高阶路径作为判别特征，对种子节点对间的可用长路径实施惩罚。最后，利用多个真实复杂网络数据集进行数值算例。实验结果表明，与其他基线方法相比，所提方法具有更优的精度与效率。

关键词: 高阶路径相似度, 复杂网络, 链路预测, 相似性度量, 公共近邻

Abstract:

For the problem that the existing link prediction method has many problems, including low accuracy and low efficiency, a method of high-order path similarity link prediction was proposed.Firstly, the path was used as the judging feature to predict missing links in complex networks, which could make resource allocation more effective and restricts information leakage by punishing public neighbor pairs.Secondly, by using high order paths as judging features, the available long paths between seed nodes would be punished.Finally, several real complex network datasets were used for numerical examples calculation.Experimental results show that the proposed algorithm is more accurate and efficient than other baseline methods.

中图分类号:

TP391

顾秋阳, 吴宝, 池仁勇. 基于高阶路径相似度的复杂网络链路预测方法[J]. 通信学报, 2021, 42(7): 61-69.

Qiuyang GU, Bao WU, Renyong CHI. Link prediction method based on the similarity of high path[J]. Journal on Communications, 2021, 42(7): 61-69.

图/表 7

表1

表2

各数据集在不同方法中的曲线下面积值"

方法名称	Facebook	Twitter	新浪微博	Dolphins	SmaGri	Netscience	hep-ph	astro-ph	dblp-collab
LP	0.944	0.932	0.935	0.728	0.849	0.905	$0 . 977$	0.936	0.811
N2V	0.864	0.873	0.918	0.791	0.759	0.875	0.956	0.830	0.719
ERA	0.836	0.892	9.835	0.823	0.817	0.795	0.932	0.912	0.802
PIC	0.874	0.951	0.856	0.846	0.832	0.846	0.913	0.868	0.831
Propflow	0.814	0.823	0.864	0.873	0.866	0.834	0.9431	0.895	0.854
HPS-LP	$0 . 969$	$0 . 964$	$0 . 956$	$0 . 844$	$0 . 938$	$0 . 970$	0.954	$0 . 954$	$0 . 889$
注：粗体显示的值均表明其所对应的模型性能良好。

表2

表3

各数据集在不同方法中的平均精度值"

方法名称	Facebook	Twitter	新浪微博	Dolphins	SmaGri	Netscience	hep-ph	astro-ph	dblp-collab
LP	0.349	0.297	0.082	0.074	0.074	0.473	$0 . 539$	0.075	0.385
N2V	0.146	0.192	0.075	0.059	0.255	0.110	0.122	0.128	0.218
ERA	0.228	0.251	0.134	0.175	0.318	0.393	0.435	0.214	0.283
PIC	0.212	0.202	0.201	0.162	0.285	0.264	0.334	0.248	0.229
Propflow	0.241	0.284	0.139	0.192	0.263	0.255	0.268	0.252	0.134
HPS-LP	$0 . 346$	$0 . 419$	$0 . 539$	$0 . 368$	$0 . 474$	$0 . 469$	0.472	$0 . 694$	$0 . 519$
注：粗体显示的值均表明其所对应的模型性能良好。

表3

图1

图2

表4

图3

参考文献 22

[1]	王凯, 李星, 兰巨龙 ,等. 一种基于资源传输路径拓扑有效性的链路预测方法[J]. 电子与信息学报, 2020,42(3): 653-660.
	WANG K , LI X , LAN J L ,et al. A new link prediction method for complex networks based on topological effectiveness of resource transmission paths[J]. Journal of Electronics ＆ Information Technology, 2020,42(3): 653-660.
[2]	胡钢, 高浩, 徐翔 ,等. 基于重要度传输矩阵的复杂网络节点重要性辨识方法[J]. 电子学报, 2020,48(12): 2402-2408.
	HU G , GAO H , XU X ,et al. Importance identification method of complex network nodes based on importance transfer matrix[J]. Acta Electronica Sinica, 2020,48(12): 2402-2408.
[3]	IMTIAZ Z B , MANZOOR A , ISLAM S U ,et al. Discovering communities from disjoint complex networks using Multi-Layer Ant Colony Optimization[J]. Future Generation Computer Systems, 2021,115: 659-670.
[4]	AN C , O'MALLEY A J ,, ROCKMORE D N . Towards intelligent complex networks:the space and prediction of information walks[J]. Applied Network Science, 2019,4(1): 35.
[5]	舒坚, 张学佩, 刘琳岚 ,等. 基于深度卷积神经网络的多节点间链路预测方法[J]. 电子学报, 2018,46(12): 2970-2977.
	SHU J , ZHANG X P , LIU L L ,et al. Multi-nodes link prediction method based on deep convolution neural networks[J]. Acta Electronica Sinica, 2018,46(12): 2970-2977.
[6]	JACCARD P . Distribution de la Flore Alpine dans le Bassin des Dranses et dans quelques régions voisines[J]. Bulletin De La Societe Vaudoise Des Sciences Naturelles, 1901,37(140): 241-272.
[7]	郭丽媛, 王智强, 梁吉业 . 基于边重要度的矩阵分解链路预测算法[J]. 模式识别与人工智能, 2018,31(2): 150-157.
	GUO L Y , WANG Z Q , LIANG J Y . Link prediction algorithm by matrix factorization based on importance of edges[J]. Pattern Recognition and Artificial Intelligence, 2018,31(2): 150-157.
[8]	ZHOU T , LU L , ZHANG Y C . Predicting missing links via local information[J]. European Physical Journal B, 2009,71(4): 623-630.
[9]	王智强, 梁吉业, 李茹 . 基于信息融合的概率矩阵分解链路预测方法[J]. 计算机研究与发展, 2019,56(2): 306-318.
	WANG Z Q , LIANG J Y , LI R . Probability matrix factorization for link prediction based on information fusion[J]. Journal of Computer Research and Development, 2019,56(2): 306-318.
[10]	IMTIAZ Z B , MANZOOR A , ISLAM S U ,et al. Discovering communities from disjoint complex networks using Multi-Layer Ant Colony Optimization[J]. Future Generation Computer Systems, 2021,115: 659-670.
[11]	刘树新, 李星, 陈鸿昶 ,等. 基于资源传输匹配度的复杂网络链路预测方法[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.
[12]	翟东升, 刘鹤, 张杰 ,等. 一种基于链路预测的技术机会挖掘方法[J]. 情报学报, 2016,35(10): 1090-1100.
	ZHAI D S , LIU H , ZHANG J ,et al. Approach to mining technology opportunity based on link prediction[J]. Journal of the China Society for Scientific and Technical Information, 2016,35(10): 1090-1100.
[13]	WU Z H , LIN Y F , WANG J ,et al. Link prediction with node clustering coefficient[J]. Physica A:Statistical Mechanics and Its Applications, 2016,452: 1-8.
[14]	RAHIMI F , REZAEI H . An event-triggered recursive state estimation approach for time-varying nonlinear complex networks with quantization effects[J]. Neurocomputing, 2021,426: 104-113.
[15]	KUMAR A , SINGH S S , SINGH K ,et al. Level-2 node clustering coefficient-based link prediction[J]. Applied Intelligence, 2019,49(7): 2762-2779.
[16]	吴翼腾, 于洪涛, 黄瑞阳 ,等. 采用组合方法进行链路预测的理论极限研究[J]. 通信学报, 2020,41(6): 34-50.
	WU Y T , YU H T , HUANG R Y ,et al. Theoretical limit of link prediction using a combination method[J]. Journal on Communications, 2020,41(6): 34-50.
[17]	李永立, 罗鹏, 张书瑞 . 基于决策分析的社交网络链路预测方法[J]. 管理科学学报, 2017,20(1): 64-74.
	LI Y L , LUO P , ZHANG S R . Link prediction in social networks based on decision analysis[J]. Journal of Management Sciences in China, 2017,20(1): 64-74.
[18]	孟绪颖, 张琦佳, 张瀚文 ,等. 社交网络链路预测的个性化隐私保护方法[J]. 计算机研究与发展, 2019,56(6): 1244-1251.
	MENG X Y , ZHANG Q J , ZHANG H W ,et al. Personalized privacy preserving link prediction in social networks[J]. Journal of Computer Research and Development, 2019,56(6): 1244-1251.
[19]	WANG Z Q , LIANG J Y , LI R . A fusion probability matrix factorization framework for link prediction[J]. Knowledge-Based Systems, 2018,159: 72-85.
[20]	刘留, 王煜尧, 倪琦瑄 ,等. 一种基于博弈论的时序网络链路预测方法[J]. 计算机研究与发展, 2019,56(9): 1953-1964.
	LIU L , WANG Y Y , NI Q X ,et al. A link prediction approach in temporal networks based on game theory[J]. Journal of Computer Research and Development, 2019,56(9): 1953-1964.
[21]	林原, 王凯巧, 刘海峰 ,等. 网络表示学习在学者科研合作预测中的应用研究[J]. 情报学报, 2020,39(4): 367-373.
	LIN Y , WANG K Q , LIU H F ,et al. Application of network representation learning in the prediction of scholar academic cooperation[J]. Journal of the China Society for Scientific and Technical Information, 2020,39(4): 367-373.
[22]	LI X , LIU S X , CHEN H C ,et al. A potential information capacity index for link prediction of complex networks based on the cannikin law[J]. Entropy, 2019,21(9): 863.

网络名称	节点个数/个	边数/条	平均路径	平均度	凝聚系数
Facebook	32 849	554 830	3.910	45.432	0.032
Twitter	39 491	673 922	4.398	39.029	0.005
新浪微博	40 393	784 994	5.343	68.934	0.046
Dolphins	31 929	493 809	4.285	40.293	0.001
SmaGri	1 365	5 943	2.911	12.045	0.047
Netscience	2 149	5 390	4.377	3.091	0.027
hep-ph	15 393	239 840	2.301	13.621	0.031
astro-ph	15 393	493 208	3.293	12.389	0.008
dblp-collab	392 801	3 102 930	4.390	9.286	0.001

指标名称	链路数量	Facebook	Twitter	新浪微博	Dolphins	SmaGri	Netscience	hep-ph	astro-ph	dblp-collab
ROC曲线下面积	短路径	0.954	0.949	0.930	0.825	0.757	0.980	0.983	0.948	0.839
	长路径	0.977	0.961	0.984	0.914	0.779	0.989	0.993	0.959	0.880
平均精度	短路径	0.343	0.176	0.130	0.154	0.041	0.079	0.387	0.040	0.034
	长路径	0.305	0.154	0.119	0.190	0.043	0.076	0.390	0.038	0.045

基于高阶路径相似度的复杂网络链路预测方法

Link prediction method based on the similarity of high path

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 22

相关文章 15

Metrics

推荐阅读 0

[1]	孙雁飞, 尹嘉峥, 亓晋, 胡筱旋, 陈梦婷, 董振江. 基于动态图嵌入的车联网拓扑控制[J]. 通信学报, 2022, 43(6): 133-142.
[2]	舒坚, 王启宁, 刘琳岚. 基于深度图嵌入的无人机自组网链路预测[J]. 通信学报, 2021, 42(7): 137-149.
[3]	顾秋阳, 吴宝, 孙兆洋, 池仁勇. 基于改进灰狼优化的复杂网络重要节点识别算法[J]. 通信学报, 2021, 42(6): 72-83.
[4]	朱近康, 柴名扬, 周武旸. 面向B5G/6G的三三三网络体系架构和优化学习机制[J]. 通信学报, 2021, 42(4): 62-75.
[5]	韩涛, 贺威, 代俊, 左勇, 杨旸, 葛晓虎. 基于无标度网络的车联网连通性研究[J]. 通信学报, 2021, 42(4): 100-108.
[6]	张胜,戴维凯,吴锋,蓝文祥. 基于分形特性的复杂网络全局效率估计方法[J]. 通信学报, 2020, 41(7): 204-212.
[7]	吴翼腾,于洪涛,黄瑞阳,李华巍. 采用组合方法进行链路预测的理论极限研究[J]. 通信学报, 2020, 41(6): 34-50.
[8]	刘树新,李星,陈鸿昶,王凯. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020, 41(6): 70-79.
[9]	顾秋阳, 琚春华, 吴功兴. 基于子图演化与改进蚁群优化算法的社交网络链路预测方法[J]. 通信学报, 2020, 41(12): 21-35.
[10]	项英倬,徐正国,游凌. 基于节点通信行为时序的指控信息流挖掘算法[J]. 通信学报, 2019, 40(9): 51-60.
[11]	李凤华,陈天柱,王震,张林杰,史国振,郭云川. 复杂网络环境下跨网访问控制机制[J]. 通信学报, 2018, 39(2): 1-10.
[12]	邓琨,李文平,余法红,张健沛. 基于多核心标签传播的复杂网络重叠社区识别方法[J]. 通信学报, 2017, 38(2): 53-66.
[13]	张洛什,王大伟,薛一波. 基于流感知的复杂网络应用识别模型[J]. 通信学报, 2015, 36(3): 161-169.
[14]	刘君,乔建志. 复杂网络中k-核与网络聚集系数的关联性研究[J]. 通信学报, 2015, 36(1): 224-229.
[15]	牛建伟,戴彬,童超,霍冠英,彭井. 基于Laplace矩阵Jordan型的复杂网络聚类算法[J]. 通信学报, 2014, 35(3): 11-21.