一種基于線性規(guī)劃的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)方法
doi: 10.11999/JEIT190731
-
1.
中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450001
-
2.
清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 北京 100084
A Link Prediction Method in Directed Networks Via Linear Programming
-
1.
Information Engineering University, People’s Liberation Army Strategic Support Force, Zhengzhou 450001, China
-
2.
Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
-
摘要: 大多數(shù)有向網(wǎng)絡(luò)鏈路預(yù)測(cè)方法在計(jì)算節(jié)點(diǎn)相似性時(shí)沒有充分考慮有向網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn),未區(qū)分不同有向鄰居對(duì)連邊形成具有的貢獻(xiàn)差異,導(dǎo)致預(yù)測(cè)性能受到局限。鑒于此,該文提出一種基于線性規(guī)劃的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)方法。該方法對(duì)3種有向鄰居的信息貢獻(xiàn)進(jìn)行量化分析,結(jié)合結(jié)構(gòu)特點(diǎn)建立線性規(guī)劃模型,進(jìn)而通過求解貢獻(xiàn)矩陣的最優(yōu)解構(gòu)建相似性指標(biāo)。9個(gè)真實(shí)有向網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果表明,所提方法相比于9種現(xiàn)有方法在兩種衡量標(biāo)準(zhǔn)下表現(xiàn)出較高的預(yù)測(cè)性能與良好的魯棒性。
-
關(guān)鍵詞:
- 有向網(wǎng)絡(luò) /
- 鏈路預(yù)測(cè) /
- 節(jié)點(diǎn)相似性 /
- 線性規(guī)劃
Abstract: Most existing link prediction methods in directed networks fail to consider the structural properties of directed networks when calculating node similarity, nor do they differentiate the contributions of directed neighbors on link formation, resulting in the limitation on prediction performance. To solve these problems, a novel link prediction method in directed networks based on linear programming is proposed. The contributions of three types of directed neighbors are quantified, then the linear programming problem is established based on network topological property. The similarity index is deduced by solving the optimal solution of the linear programming problem. Experimental results on nine real-world directed networks show that the proposed method outperforms nine benchmarks on both accuracy and robustness under two evaluation metrics.-
Key words:
- Directed network /
- Link prediction /
- Node similarity /
- Linear programming
-
表 1 網(wǎng)絡(luò)數(shù)據(jù)基本統(tǒng)計(jì)參數(shù)
序號(hào) 名稱 類型 $N$ $M$ $\left\langle k \right\rangle $ $\rho $(%) $C$ $\left\langle d \right\rangle $ $\gamma $ $\kappa $ (1) ADO 社交網(wǎng)絡(luò) 2,539 12,969 10.22 38.8 14.2 5.30 0.251 8.25 (2) HIG 社交網(wǎng)絡(luò) 70 366 10.46 50.3 40.4 3.51 0.083 4.38 (3) RES 社交網(wǎng)絡(luò) 217 2,672 24.63 62.4 30.4 2.79 0.096 6.32 (4) EMA 信息網(wǎng)絡(luò) 1,005 25,571 50.89 71.1 25.7 3.01 –0.014 2.80 (5) USA 交通網(wǎng)絡(luò) 1,574 28,236 35.88 78.1 38.4 3.85 –0.113 1.85 (6) OF 交通網(wǎng)絡(luò) 2,939 30,501 20.76 97.2 25.5 5.19 0.051 1.74 (7) CELE 生物網(wǎng)絡(luò) 453 4,596 20.29 16.8 12.4 3.03 –0.226 2.62 (8) FWFD 生態(tài)網(wǎng)絡(luò) 128 2,137 33.39 2.9 31.4 1.88 –0.104 5.02 (9) LAK 生態(tài)網(wǎng)絡(luò) 183 2,494 27.26 4.09 33.2 2.65 –0.266 2.99 下載: 導(dǎo)出CSV
表 2 AUC結(jié)果對(duì)比
預(yù)測(cè)指標(biāo) ADO HIG RES EMA USA OF CELE FWFD LAK DCN 0.716 0.860 0.889 0.949 0.969 0.968 0.804 0.745 0.942 DAA 0.714 0.862 0.895 0.953 0.972 0.969 0.807 0.749 0.940 DRA 0.716 0.861 0.895 0.956 0.973 0.971 0.811 0.752 0.939 DPA 0.680 0.621 0.650 0.887 0.953 0.924 0.810 0.854 0.946 Bifan 0.770 0.826 0.859 0.932 0.964 0.965 0.888 0.920 0.988 LP-0.001 0.781 0.882 0.899 0.954 0.976 0.984 0.860 0.769 0.964 Katz-0.001 0.877 0.883 0.898 0.954 0.976 0.984 0.874 0.778 0.970 MFI 0.872 0.845 0.792 0.772 0.908 0.975 0.836 0.734 0.947 LO-0.01 0.678 0.830 0.888 0.949 0.967 0.971 0.889 0.972 0.995 LO-0.001 0.679 0.830 0.868 0.956 0.977 0.974 0.892 0.934 0.990 LPD-0.01-1 0.803 0.898 0.917 0.956 0.984 0.991 0.899 0.956 0.994 LPD-0.001-1 0.812 0.883 0.902 0.969 0.968 0.990 0.886 0.907 0.988 LPD-max 0.814 0.898 0.919 0.969 0.984 0.993 0.907 0.973 0.996 下載: 導(dǎo)出CSV
-
REN Zhuoming, ZENG An, and ZHANG Yicheng. Structure-oriented prediction in complex networks[J]. Physics Reports, 2018, 750: 1–51. doi: 10.1016/J.PHYSREP.2018.05.002 Lü Linyuan and ZHOU Tao. Link prediction in complex networks: A survey[J]. Physica A: Statistical Mechanics and its Applications, 2011, 390(6): 1150–1170. doi: 10.1016/J.PHYSA.2010.11.027 王凱, 李星, 蘭巨龍, 等. 一種基于資源傳輸路徑拓?fù)溆行缘逆溌奉A(yù)測(cè)方法[J]. 電子與信息學(xué)報(bào), 2020, 42(3): 653–660. doi: 10.11999/JEIT190333WANG Kai, LI Xing, LAN Julong, 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. doi: 10.11999/JEIT190333 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 AGHABOZORGI F and KHAYYAMBASHI M R. A new similarity measure for link prediction based on local structures in social networks[J]. Physica A: Statistical Mechanics and its Applications, 2018, 501: 12–23. doi: 10.1016/J.PHYSA.2018.02.010 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 王凱, 劉樹新, 陳鴻昶, 等. 一種基于節(jié)點(diǎn)間資源承載度的鏈路預(yù)測(cè)方法[J]. 電子與信息學(xué)報(bào), 2019, 41(5): 1225–1234. doi: 10.11999/JEIT180553WANG 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 KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39–43. doi: 10.1007/BF02289026 CHEBOTAREV P and SHAMIS E. The matrix-forest theorem and measuring relations in small social groups[J]. Automation and Remote Control, 1997, 58(9): 1505–1514. 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 LI Jinsong, PENG Jianhua, LIU Shuxin, et al. Link prediction in directed networks utilizing the role of reciprocal links[J]. IEEE Access, 2020, 8: 28668–28680. doi: 10.1109/ACCESS.2020.2972072 ZHANG Xue, ZHAO Chengli, WANG Xiaojie, et al. Identifying missing and spurious interactions in directed networks[J]. International Journal of Distributed Sensor Networks, 2015, 11(9): 507386. doi: 10.1155/2015/507386 WANG Xiaojie, ZHANG Xue, ZHAO Chengli, et al. Predicting link directions using local directed path[J]. Physica A: Statistical Mechanics and its Applications, 2015, 419: 260–267. doi: 10.1016/J.PHYSA.2014.10.007 BüTüN E and KAYA M. A pattern based supervised link prediction in directed complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2019, 525: 1136–1145. doi: 10.1016/J.PHYSA.2019.04.015 SALHA G, LIMNIOS S, HENNEQUIN R, et al. Gravity-inspired graph autoencoders for directed link prediction[C]. The 28th ACM International Conference on Information and Knowledge Management, Beijing, China, 2019: 589–598. doi: 10.1145/3357384.3358023. GUNDALA L A and SPEZZANO F. Estimating node indirect interaction duration to enhance link prediction[J]. Social Network Analysis and Mining, 2019, 9(1): 17. doi: 10.1007/s13278-019-0561-2 PECH R, HAO D, LEE Y L, et al. Link prediction via linear optimization[J]. Physica A: Statistical Mechanics and Its Applications, 2019, 528: e121319. doi: 10.1016/j.physa.2019.121319 ZHANG Qianming, Lü Linyuan, WANG Wenqiang, et al. Potential theory for directed networks[J]. PLoS One, 2013, 8(2): e55437. doi: 10.1371/JOURNAL.PONE.0055437 KUNEGIS J. KONECT network dataset[EB/OL]. http://konect.uni-koblenz.de/networks/, 2017. -