一種基于資源傳輸路徑拓撲有效性的鏈路預測方法

王凱; 李星; 蘭巨龍; 衛(wèi)紅權; 劉樹新

doi:10.11999/JEIT190333

一種基于資源傳輸路徑拓撲有效性的鏈路預測方法

doi: 10.11999/JEIT190333 cstr: 32379.14.JEIT190333

國家數(shù)字交換系統(tǒng)工程技術研究中心鄭州 450002

基金項目: 國家自然科學基金(61803384)，國家自然科學基金創(chuàng)新研究群體項目(61521003)

詳細信息

作者簡介:
王凱：男，1980年生，副研究員，博士生，研究方向為鏈路預測、社會網(wǎng)絡分析

李星：男，1987年生，助理研究員，博士生，研究方向為鏈路預測

蘭巨龍：男，1962年生，教授，博士生導師，研究方向為新型網(wǎng)絡體系，網(wǎng)絡動力學

衛(wèi)紅權：男，1970年生，副研究員，碩士生導師，研究方向為社團發(fā)現(xiàn)

劉樹新：男，1987年生，助理研究員，博士，研究方向為復雜網(wǎng)絡演化、鏈路預測

通訊作者:
劉樹新　liushuxin11@126.com, liushuxin11@gmail.com

中圖分類號: TN915, TP391
計量
- 文章訪問數(shù): 2322
- HTML全文瀏覽量: 978
- PDF下載量: 98
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-05-13
- 修回日期: 2019-09-10
- 網(wǎng)絡出版日期: 2019-09-19
- 刊出日期: 2020-03-19

A New Link Prediction Method for Complex Networks Based onTopological Effectiveness of Resource Transmission Paths

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

Funds: The National Natural Science Foundation of China (61803384), The National Natural Science Foundation Innovation Research Group Project of China (61521003)

摘要

摘要:
鏈路預測旨在利用網(wǎng)絡中已有的拓撲結構或其他信息，預測未連邊節(jié)點間存在連接的可能性。資源分配指標具有較低復雜度的同時取得了較好的預測效果，但在資源傳輸過程的描述中缺少對路徑有效性的刻畫。資源傳輸過程是網(wǎng)絡演化連邊產(chǎn)生的重要內(nèi)在動力，通過分析節(jié)點間資源傳輸路徑周圍拓撲的有效性，該文提出一種基于資源傳輸路徑有效性的鏈路預測方法。該方法首先分析了節(jié)點間潛在的資源傳輸路徑對資源傳輸量的影響，提出資源傳輸路徑有效性的量化方法。然后，基于資源傳輸路徑的有效性，通過對雙向資源傳輸量進行刻畫，提出了節(jié)點間傳輸路徑的有效性指標。在12個實際網(wǎng)絡數(shù)據(jù)集上的實驗測試表明，相比其他基于相似性的鏈路預測方法，該方法在AUC和Precision衡量標準下能夠取得更好的效果。
- 復雜網(wǎng)絡 /
- 鏈路預測 /
- 資源傳輸路徑 /
- 有效性
Abstract:
Link prediction considers to discover the unknown or missing links of complex networks by using the existing topology or other information. Resource Allocation index can achieve a good performance with low complexity. However, it ignores the path effectiveness of resource transmission process. The resource transmission process is an important internal driving force for the evolution of the network. By analyzing the effectiveness of the topology around the resource transmission path between nodes, a link prediction method based on topological effectiveness of resource transmission paths is proposed. Firstly, the influence of potential resource transmission paths between nodes on resource transmission is analyzed, and a quantitative method for resource transmission path effectiveness is proposed. Then, based on the effectiveness of the resource transmission path, after studying the two-way resource transmission amount between two nodes, the transmission path effectiveness index is proposed. The experimental results of 12 real networks show that compared with other link prediction methods, the proposed method can achieve higher prediction accuracy under the AUC and Precision metrics.
- Complex network /
- Link prediction /
- Resource transmission path /
- Effectiveness

HTML全文

圖 1 網(wǎng)絡中節(jié)點間多路徑傳輸示意圖

下載: 全尺寸圖片幻燈片

圖 2 網(wǎng)絡拓撲結構與路徑傳輸有效性的關系示意圖

下載: 全尺寸圖片幻燈片

圖 3 不同網(wǎng)絡結構下路徑數(shù)目對比分析

下載: 全尺寸圖片幻燈片

圖 4 不同網(wǎng)絡結構下路徑有效性對比分析

下載: 全尺寸圖片幻燈片

圖 5 存在直接連接的兩點之間路徑有效性的量化

下載: 全尺寸圖片幻燈片

圖 6 未直接連接的兩點之間路徑有效性的量化

下載: 全尺寸圖片幻燈片

圖 7 節(jié)點x到y傳輸路徑有效性量化舉例

下載: 全尺寸圖片幻燈片

圖 8 節(jié)點y到x傳輸路徑有效性量化舉例

下載: 全尺寸圖片幻燈片

圖 9 調(diào)節(jié)參數(shù)對AUC結果的影響曲線圖

下載: 全尺寸圖片幻燈片

圖 10 強度參數(shù)對Pre結果影響曲線圖

下載: 全尺寸圖片幻燈片

表 1 網(wǎng)絡數(shù)據(jù)特征參數(shù)

網(wǎng)絡	AIDS	FWEW	HS	Figeys	UC	Metbolic
節(jié)點數(shù)	146	69	1858	2239	1899	453
邊數(shù)	180	880	12534	6432	13838	2025
集聚系數(shù)	2.47	25.51	13.49	5.76	14.57	8.94
平均度	3.42	1.64	3.39	3.98	3.06	2.66
平均路徑	–0.725	–0.298	–0.085	–0.331	–0.188	–0.226
匹配系數(shù)	0.052	0.552	0.0904	0.04	0.109	0.647

下載: 導出CSV

表 2 AUC結果對比分析

方法	AIDS	FWEW	HS	Figeys	UC	Metbolic
CN	0.599	0.684	0.812	0.566	0.781	0.921
RA	0.609	0.702	0.816	0.570	0.787	0.959
AA	0.609	0.695	0.815	0.569	0.787	0.955
CAR	0.599	0.685	0.812	0.567	0.783	0.920
LP^(a)	0.836	0.702	0.933	0.888	0.893	0.920
LP^(b)	0.833	0.728	0.940	0.903	0.903	0.921
Katz^(a)	0.854	0.704	0.933	0.887	0.893	0.920
Katz^(b)	0.852	0.734	0.937	0.898	0.903	0.920
ACT	0.954	0.779	0.868	0.917	0.896	0.767
Cos+	0.591	0.510	0.960	0.844	0.869	0.904
本文方法	0.961	0.827	0.971	0.952	0.929	0.964
^(a)可調(diào)參數(shù)$\alpha {\rm{ = 0}}{\rm{.001}}$ ^(b)可調(diào)參數(shù)$\alpha {\rm{ = 0}}{\rm{.01}}$

下載: 導出CSV

表 3 Pre結果對比

方法	AIDS	FWEW	HS	Figeys	UC	Metbolic
CN	0.019	0.143	0.017	0.011	0.034	0.202
RA	0.028	0.165	0.008	0.012	0.026	0.319
AA	0.028	0.152	0.012	0.012	0.033	0.252
CAR	0.019	0.137	0.033	0.025	0.064	0.193
LP^(a)	0.055	0.153	0.021	0.011	0.034	0.202
LP^(b)	0.055	0.180	0.055	0.012	0.053	0.200
Katz^(a)	0.055	0.153	0.021	0.010	0.034	0.202
Katz^(b)	0.055	0.183	0.071	0.011	0.054	0.198
ACT	0.000	0.128	0.000	0.000	0.000	0.000
Cos+	0.000	0.000	0.015	0.005	0.010	0.097
本文方法	0.068	0.344	0.107	0.130	0.093	0.374
^(a)可調(diào)參數(shù)$\alpha {\rm{ = 0}}{\rm{.001}}$ ^(b)可調(diào)參數(shù)$\alpha {\rm{ = 0}}{\rm{.01}}$

下載: 導出CSV

參考文獻(26)

WANG Minggang, ZHAO Longfeng, DU Ruijin, et al. A novel hybrid method of forecasting crude oil prices using complex network science and artificial intelligence algorithms[J]. Applied Energy, 2018, 220: 480–495. doi: 10.1016/j.apenergy.2018.03.148

GOSAK M, MARKOVI? R, DOLEN?EK J, et al. Network science of biological systems at different scales: A review[J]. Physics of Life Reviews, 2018, 24: 118–135. doi: 10.1016/j.plrev.2017.11.003

DU Wenbo, ZHANG Mingyuan, YING Wen, et al. The networked evolutionary algorithm: A network science perspective[J]. Applied Mathematics and Computation, 2018, 338: 33–43. doi: 10.1016/j.amc.2018.06.002

CHEN Zhenhao, WU Jiajing, XIA Yongxiang, et al. Robustness of interdependent power grids and communication networks: A complex network perspective[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2018, 65(1): 115–119. doi: 10.1109/TCSII.2017.2705758

王凱, 劉樹新, 陳鴻昶, 等. 一種基于節(jié)點間資源承載度的鏈路預測方法[J]. 電子與信息學報, 2019, 41(5): 1225–1234. doi: 10.11999/JEIT180553

WANG Kai, LIU Shuxin, CHEN Hongchang, et al. A new link prediction method for complex networks based on resources carrying capacity between nodes[J]. Journal of Electronics &Information Technology, 2019, 41(5): 1225–1234. doi: 10.11999/JEIT180553

BENSON A R, ABEBE R, SCHAUB M T, et al. Simplicial closure and higher-order link prediction[J]. The National Academy of Sciences of the United States of America, 2018, 115(48): E11221–E11230. doi: 10.1073/pnas.1800683115

LIU Shuxin, JI Xinsheng, LIU Caixia, 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): 1650254. doi: 10.1142/S0217979216502544

LORRAIN F and WHITE H C. Structural Equivalence of Individuals in Social Networks[M]. LEINHARDT S. Social Networks: A Developing Paradigm. Lausanne: Academic Press, 1977: 67-98. doi: 10.1080/0022250X.1971.9989788.

ZHOU Tao, Lü Linyuan, and ZHANG Yicheng. Predicting missing links via local information[J]. The European Physical Journal B, 2009, 71(4): 623–630. doi: 10.1140/epjb/e2009-00335-8

ADAMIC L A and ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211–230. doi: 10.1016/S0378-8733(03)00009-1

CANNISTRACI C V, ALANIS-LOBATO G, and 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. doi: 10.1038/srep01613

XIE Yanbo, ZHOU Tao, and WANG Binhong. Scale-free networks without growth[J]. Physica A: Statistical Mechanics and its Applications, 2008, 387(7): 1683–1688. doi: 10.1016/j.physa.2007.11.005

SALTON G and MCGILL M J. Introduction to Modern Information Retrieval[M]. New York: McGraw-Hill, 1986.

Lü Linyuan, JIN Cihang, and ZHOU Tao. Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, 2009, 80(4): 046122. doi: 10.1103/PhysRevE.80.046122

LIU Shuxin, JI Xinsheng, LIU Caixia, et al. Extended resource allocation index for link prediction of complex network[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 479: 174–183. doi: 10.1016/j.physa.2017.02.078

KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39–43. doi: 10.1007/BF02289026

KLEIN D J and RANDI? M. Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12(1): 81–95. doi: 10.1007/BF01164627

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. doi: 10.1109/tkde.2007.46

BRIN S and PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1/7): 107–117. doi: 10.1016/s0169-7552(98)00110-x

YANG Dingda, LIAO Xiangwen, SHEN Huawei, et al. Dynamic node immunization for restraint of harmful information diffusion in social networks[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 503: 640–649. doi: 10.1016/j.physa.2018.02.128

劉樹新, 季新生, 劉彩霞, 等. 一種信息傳播促進網(wǎng)絡增長的網(wǎng)絡演化模型[J]. 物理學報, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902

LIU Shuxin, JI Xinsheng, LIU Caixia, et al. A complex network evolution model for network growth promoted by information transmission[J]. Acta Physica Sinica, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902

YAO Yabing, ZHANG Ruisheng, YANG Fan, et al. Link prediction in complex networks based on the interactions among paths[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 510: 52–67. doi: 10.1016/j.physa.2018.06.051

LIU Liang, QU Bo, CHEN Bin, et al. Modelling of information diffusion on social networks with applications to WeChat[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 496: 318–329. doi: 10.1016/j.physa.2017.12.026

SATHIYAKUMARI K and VIJAYA M S. Identification of Subgroups in a Directed Social Network Using Edge Betweenness and Random Walks[M]. SATAPATHY S C, BHATEJA V, and DAS S. Smart Computing and Informatics. Singapore: Springer, 2018: 115-125. doi: 10.1007/978-981-10-5544-7_12.

WU Yiteng, YU Hongtao, ZHANG Jianpeng, 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. doi: 10.3233/IDA-173400

CHUAN P M, SON L H, ALI M, et al. Link prediction in co-authorship networks based on hybrid content similarity metric[J]. Applied Intelligence, 2018, 48(8): 2470–2486. doi: 10.1007/s10489-017-1086-x

施引文獻

資源附件(0)

訪問統(tǒng)計