Link prediction based on random walks

被引：0

作者：

Li, Li ^{[1
]}

Feng, Weisi ^{[1
]}

Jing, Chenyang ^{[1
]}

Tan, Feng ^{[1
]}

He, Ping ^{[1
]}

Wang, Jing ^{[1
]}

机构：

[1] Faculty of Computer and Information Science, Southwest University, Chongqing

来源：

Journal of Computational Information Systems | 2015年 / 11卷 / 05期

基金：

中国国家自然科学基金;

关键词：

Complex network; Link prediction; Random walk;

D O I：

10.12733/jcis13436

中图分类号：

学科分类号：

摘要：

Link prediction in complex networks has been an attractive problem. Generally, when we obtained a snapshot of a network, we would like to infer which interactions are most likely to occur among the existing members in the future. This kind of problem has been extensively studied both from academia and industry. However, link prediction is challenging in practice. To address this issue. In this paper, we focused on the topology structure of the networks for link prediction. Two algorithms CN-LRW and CN-RWR are proposed based on local random walk and random walk with restart, respectively. We evaluate our approaches on three real data sets. Experiments show that CN-LRW and CN-RWR outperform LRW and RWR respectively in most cases. Incorporating node information with the network structure features seems promising in discovering the latent semantics of the network. Copyright © 2015 Binary Information Press.

引用

页码：1757 / 1764

页数：7

共 13 条

[1]

Clauset A., Moore C., Newman M.E., Hierarchical structure and the prediction of missing links in networks, Nature, 453, 7191, pp. 98-101, (2008)

[2]

Sarukkai R.R., Link prediction and path analysis using markov chains, Computer Networks, 33, 1, pp. 377-386, (2000)

[3]

Linyuan L., Link prediction in complex network, University of Electronic Science and Technology, 39, 5, (2010)

[4]

Liu W., Lu L., Link prediction based on local random walk, EPL (Europhysics Letters), 89, 5, (2010)

[5]

Coppersmith D., Doyle P., Raghavan P., Snir M., Random walks on weighted graphs and applications to on-line algorithms, Journal of the ACM (JACM), 40, 3, pp. 421-453, (1993)

[6]

Zhao B., Zhang Z., Gu Y., Gong X., Qian W., Zhou A., Discovering collective viewpoints on micro-blogging events based on community and temporal aspects, Advanced Data Mining and Applications, pp. 270-284, (2011)

[7]

Backstrom L., Leskovec J., Supervised random walks: predicting and recommending links in social networks, Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, pp. 635-644, (2011)

[8]

Yang Y., Zhang Z., Random walks in unweighted and weighted modular scale-free networks with a perfect trap, The Journal of Chemical Physics, 139, 23, (2013)

[9]

Liben-Nowell D., Kleinberg J., The link-prediction problem for social networks, Journal of the American Society for Information Science and Technology, 58, 7, pp. 1019-1031, (2007)

[10]

Kemeny J.G., Snell J.L., Finite Markov Chains, 28, (1976)

← 1 2 →