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

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

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.

CLC Number:

TP391

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.

Figures/Tables 7

方法名称	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$
注：粗体显示的值均表明其所对应的模型性能良好。

方法名称	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$
注：粗体显示的值均表明其所对应的模型性能良好。

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

Metrics

Recommended 0

No Suggested Reading articles found!

网络名称	节点个数/个	边数/条	平均路径	平均度	凝聚系数
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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 22

Related Articles 15

Metrics

Recommended 0

[1]	Yanfei SUN, Jiazheng YIN, Jin QI, Xiaoxuan HU, Mengting CHEN, Zhenjiang DONG. Topology control based on dynamic graph embedding in Internet of vehicles [J]. Journal on Communications, 2022, 43(6): 133-142.
[2]	Rong QIAN, Jianting XU, Kejun ZHANG, Hongyu DONG, Fangyuan XING. Research on HMM based link prediction method in heterogeneous network [J]. Journal on Communications, 2022, 43(5): 214-225.
[3]	Jian SHU, Qining WANG, Linlan LIU. UAV ad hoc network link prediction based on deep graph embedding [J]. Journal on Communications, 2021, 42(7): 137-149.
[4]	Qiuyang GU, Bao WU, Zhaoyang SUN, Renyong CHI. Key node identification algorithm for complex network based on improved grey wolf optimization [J]. Journal on Communications, 2021, 42(6): 72-83.
[5]	Jinkang ZHU, Mingyang CHAI, Wuyang ZHOU. Three-three-three network architecture and learning optimization mechanism for B5G/6G [J]. Journal on Communications, 2021, 42(4): 62-75.
[6]	Tao HAN, Wei HE, Jun DAI, Yong ZUO, Yang YANG, Xiaohu GE. Connectivity analysis of IoV based on scale-free network [J]. Journal on Communications, 2021, 42(4): 100-108.
[7]	Xiaojuan ZHAO, Yan JIA, Aiping LI, Kai CHEN. Research on link prediction model based on hierarchical attention mechanism [J]. Journal on Communications, 2021, 42(3): 36-44.
[8]	Sheng ZHANG,Weikai DAI,Feng WU,Wenxiang LAN. Global efficiency estimation method of complex network based on fractal property [J]. Journal on Communications, 2020, 41(7): 204-212.
[9]	Yiteng WU,Hongtao YU,Ruiyang HUANG,Huawei LI. Theoretical limit of link prediction using a combination method [J]. Journal on Communications, 2020, 41(6): 34-50.
[10]	Shuxin LIU,Xing LI,Hongchang CHEN,Kai WANG. Link prediction method based on matching degree of resource transmission for complex network [J]. Journal on Communications, 2020, 41(6): 70-79.
[11]	Qiuyang GU, Chunhua JU, Gongxing WU. Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm [J]. Journal on Communications, 2020, 41(12): 21-35.
[12]	Yingzhuo XIANG,Zhengguo XU,Ling YOU. Instruction flow mining algorithm based on the temporal sequence of node communication actions [J]. Journal on Communications, 2019, 40(9): 51-60.
[13]	Fenghua LI,Tianzhu CHEN,Zhen WANG,Linjie ZHANG,Guozhen SHI,Yunchuan GUO. Cross-network access control mechanism for complex network environment [J]. Journal on Communications, 2018, 39(2): 1-10.
[14]	Kun DENG,Wen-ping LI,Fa-hong YU,Jian-pei ZHANG. Overlapping community detection in complex networks based on multi kernel label propagation [J]. Journal on Communications, 2017, 38(2): 53-66.
[15]	Jun LIU,Jian-zhong QIAO. Research on relevance between k-core and clustering coefficient in complex network [J]. Journal on Communications, 2015, 36(1): 224-229.