基于资源传输匹配度的复杂网络链路预测方法

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

通信学报 ›› 2020, Vol. 41 ›› Issue (6): 70-79.doi: 10.11959/j.issn.1000-436x.2020124

基于资源传输匹配度的复杂网络链路预测方法

刘树新^1,²,李星^1,²,陈鸿昶^1,²,王凯^1,²

¹ 信息工程大学信息技术研究所，河南郑州 450002
² 国家数字交换系统工程技术研究中心，河南郑州 450002

修回日期:2020-03-11 出版日期:2020-06-25 发布日期:2020-07-04
作者简介:刘树新（1987- ），男，山东临朐人，博士，信息工程大学助理研究员，主要研究方向为链路预测、通信网络安全|李星（1987- ），男，河南新乡人，博士，信息工程大学助理研究员，主要研究方向为链路预测、社团挖掘|陈鸿昶（1964- ），男，河南郑州人，信息工程大学教授、博士生导师，主要研究方向为通信与信息系统、数据科学与人工智能|王凯（1980- ），男，河南许昌人，博士，信息工程大学副研究员，主要研究方向为链路预测、社会网络分析
基金资助:
国家自然科学基金资助项目(61803384)

Link prediction method based on matching degree of resource transmission for complex network

Shuxin LIU^1,²,Xing LI^1,²,Hongchang CHEN^1,²,Kai WANG^1,²

¹ Information Technology Institute,Information Engineering University,Zhengzhou 450002,China
² National Digital Switching System ＆Engineering Technology Research Center,Zhengzhou 450002,China

Revised:2020-03-11 Online:2020-06-25 Published:2020-07-04
Supported by:
The National Natural Science Foundation of China(61803384)

摘要/Abstract

摘要：

为了解决基于资源传输的链路预测方法忽略节点间匹配度对资源传输过程影响的问题，提出了一种基于资源传输匹配度的复杂网络链路预测方法。首先，对资源传输路径上的2个端点进行详细分析，提出任意节点间匹配度的量化方法；然后，为了刻画匹配度对于节点间资源传输过程的影响程度，定义了资源传输匹配度；最后，基于资源传输匹配度，考虑节点间双向传输的资源量，提出资源传输匹配度指标。在9个实际网络数据集上的实验测试表明，相比其他基于相似性指标，所提方法在AUC和Precision衡量标准下能够取得更好的效果。

关键词: 复杂网络, 链路预测, 资源传输, 匹配度

Abstract:

In order to solve the problem that many existing resource-transmission-based methods ignore the important influence of the matching degree of two endpoints on resource transmission,a link prediction method was proposed based on matching degree of resource transmission for complex networks.Firstly,by analyzing the two endpoints on the resource transmission path in detail,the method of quantifying the matching degree between two nodes was proposed.Then,in order to describe the influence of matching degree on resource transmission process between nodes,the matching degree of resource transmission was defined.Finally,based on the matching degree of resource transmission,a resource transmission matching index was proposed considering the resource amount of bidirectional transmission between nodes.The experimental results of nine datasets show that compared with other similarity indices,the proposed index can achieve higher prediction accuracy under the AUC and Precision metrics.

Key words: complex network, link prediction, resource transmission, matching degree

中图分类号:

TP391

刘树新,李星,陈鸿昶,王凯. 基于资源传输匹配度的复杂网络链路预测方法[J]. 通信学报, 2020, 41(6): 70-79.

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.

图/表 13

图1

图2

图3

图4

图5

图6

图7

图8

表1

图9

图10

图11

图12

参考文献 32

[1]	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.
[2]	SHANMUKHAPPA T , IVAN W H , CHI K T . Spatial analysis of bus transport networks using network theory[J]. Physica A:Statistical Mechanics and Its Applications, 2018,502: 295-314.
[3]	CHENG Y , TAO F , XU L ,et al. Advanced manufacturing systems:supply–demand matching of manufacturing resource based on complex networks and Internet of Things[J]. Enterprise Information Systems, 2018,12(7): 780-797.
[4]	KIM J , HASTAK M . Social network analysis[J]. International Journal of Information Management:The Journal for Information Professionals, 2018,38(1): 86-96.
[5]	刘树新, 季新生, 刘彩霞 ,等. 一种信息传播促进网络增长的网络演化模型[J]. 物理学报, 2014,63(15): 1-11.
	LIU S H , 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):158902.
[6]	王凯, 刘树新, 陈鸿昶 ,等. 一种基于节点间资源承载度的链路预测方法[J]. 电子与信息学报, 2019,41(5): 1225-1234.
	WANG K , LIU S X , CHEN H C ,et al. A new link prediction method for complex networks based on resources carrying capacity between nodes[J]. Journal of Electronics and Information Technology, 2019,41(5): 1225-1234.
[7]	刘树新, 季新生, 刘彩霞 ,等. 局部拓扑信息耦合促进网络演化[J]. 电子与信息学报, 2016,38(9): 2180-2187.
	LIU S H , JI X S , LIU C X ,et al. Information coupling of local topology promoting the network evolution[J]. Journal of Electronics and Information Technology, 2016,38(9): 2180-2187.
[8]	VON M 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(1): 433-437.
[9]	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. New York:ACM Press, 2011: 1046-1054.
[10]	HOLLAND P W , LASKEY K B , LEINHARDT S . Stochastic blockmodels:first steps[J]. Social Networks, 1983,5(2): 109-137.
[11]	LORRAIN F , WHITE H C . Structural equivalence of individuals in social networks[J]. Social Networks, 1977,1(1): 67-98.
[12]	ADAMIC L A , ADAR E . Friends and neighbors on the Web[J]. Social Networks, 2003,25(3): 211-230.
[13]	CANNISTRACI C V , ALANIS-LOBATO G , RAVASI T . From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Scientific Reports, 2013(3):1613.
[14]	ZHOU T,Lü L Y , ZHANG Y C . Predicting missing links via local information[J]. The European Physical Journal B, 2009,71(4): 623-630.
[15]	LYU L , JIN C H , ZHOU T . Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, 2009,80(4):046122.
[16]	LIU S H , JI X S , LIU C X ,et al. Extended resource allocation index for link prediction of complex network[J]. Physica A:Statistical Mechanics and its Applications, 2017,479: 174-183.
[17]	LI X , LIU S X , CHEN H C ,et al. A potential information capacity index for link prediction of complex networks based on the cannikinlaw[J]. Entropy, 2019,21(9):863.
[18]	KATZ L . A new status index derived from sociometric analysis[J]. Psychometrika, 1953,18(1): 39-43.
[19]	KLEIN D J , RANDI? M . Resistance distance[J]. Journal of Mathematical Chemistry, 1993,12(1): 81-95.
[20]	FOUSS F , PIROTTE A , RENDERS J M ,et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2007,19(3): 355-369.
[21]	MELAMED D , HARRELL A , SIMPSON B . Cooperation,clustering,and assortative mixing in dynamic networks[J]. Proceedings of the National Academy of Sciences, 2018,115(5): 951-956.
[22]	WU Y , YU H , ZHANG J ,et al. USI-AUC:an evaluation criterion of community detection based on a novel link-prediction method[J]. Intelligent Data Analysis, 2018,22(2): 439-462.
[23]	CHUAN P M , ALI M , KHANG T D ,et al. Link prediction in co-authorship networks based on hybrid content similarity metric[J]. Applied Intelligence, 2018,48(8): 2470-2486.
[24]	GOPAL S . The evolving social geography of blogs[M]. Berlin: SpringerPress, 2007: 275-293.
[25]	ULANOWICZ R E , DEANGELIS D L . Network analysis of trophic dynamics in South Florida ecosystems[J]. US Geological Survey Program on the South Florida Ecosystem, 2005,114: 45-47.
[26]	WATTS D J , STROGATZ S H . Collective dynamics of ‘small-world’ Networks[J]. Nature, 1998,393(6684):440
[27]	GUIMERA R , DANON L , DIAZ-GUILERA A ,et al. Self-similar Community structure in a network of human interactions[J]. Physical Review E, 2003,68(6):065103.
[28]	ADAMIC L A , GLANCE N . The political blogosphere and the 2004 US election:divided they blog[C]// Proceedings of the 3rd International Workshop on Link Discovery. New York:ACM Press, 2005: 36-43.
[29]	BATAGELJ V , MRVAR A . Pajek-program for large network analysis[J]. Connections, 1998,21(2): 47-57.
[30]	LYU L Y , PAN L M , ZHOU T ,et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences, 2015,112(8): 2325-2330.
[31]	ISELLA L , STEHLé J , BARRAT A ,et al. What's in a crowd? analysis of face-to-face behavioral networks[J]. Journal of Theoretical Biology, 2011,271(1): 166-180.
[32]	GUIMERA R , AMARAL L A N . Functional cartography of complex metabolic networks[J]. Nature, 2005,433(7028):895.

数据集	\|V\|	\|E\|	<k>	<d>	r	C
AIDS	146	180	2.47	3.42	-0.725	0.052
FW	128	2 075	32.42	1.78	-0.112	0.335
CE	297	2 148	14.46	2.46	-0.163	0.308
EM	167	5 784	69.26	1.87	-0.295	0.541
PB	1 222	16 717	27.36	2.74	-0.221	0.361
USAir	332	2 128	12.81	2.74	-0.208	0.749
HS	1 858	12 534	13.49	3.39	-0.085	0.090
Infec	410	2 765	5.76	3.98	-0.331	0.04
Met	453	2 025	8.94	2.66	-0.226	0.647

基于资源传输匹配度的复杂网络链路预测方法

Link prediction method based on matching degree of resource transmission for complex network

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 32

相关文章 15

Metrics

推荐阅读 0

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