A Link Prediction Method in Directed Networks Via Linear Programming

Jinsong LI; Jianhua PENG; Shuxin LIU; Xinsheng JI

doi:10.11999/JEIT190731

Volume 42 Issue 10

Oct. 2020

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2020 > 42(10): 2394-2402

Jinsong LI, Jianhua PENG, Shuxin LIU, Xinsheng JI. A Link Prediction Method in Directed Networks Via Linear Programming[J]. Journal of Electronics & Information Technology, 2020, 42(10): 2394-2402. doi: 10.11999/JEIT190731

Citation:

Jinsong LI, Jianhua PENG, Shuxin LIU, Xinsheng JI. A Link Prediction Method in Directed Networks Via Linear Programming[J]. Journal of Electronics & Information Technology, 2020, 42(10): 2394-2402. doi: 10.11999/JEIT190731

Citation:

PDF( 3240 KB)

A Link Prediction Method in Directed Networks Via Linear Programming

doi: 10.11999/JEIT190731

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

Funds: The National Natural Science Foundation of China (61803384)

Received Date: 2019-09-20
Rev Recd Date: 2020-05-25

Available Online: 2020-06-01

Publish Date: 2020-10-13

Abstract

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.
- Directed network,
- Link prediction,
- Node similarity,
- Linear programming

FullText(HTML)

References(19)

References

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

王凯, 李星, 兰巨龙, 等. 一种基于资源传输路径拓扑有效性的链路预测方法[J]. 电子与信息学报, 2020, 42(3): 653–660. doi: 10.11999/JEIT190333

WANG 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

王凯, 刘树新, 陈鸿昶, 等. 一种基于节点间资源承载度的链路预测方法[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

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.

Relative Articles

Supplements(0)

Cited By

Proportional views