Link prediction based on local random walk

Weiping Liu and Linyuan Lü

Department of Physics, University of Fribourg - Chemin du Musée 3, CH-1700 Fribourg, Switzerland

Corresponding author: linyuan.lue@unifr.ch

Received: 12 October 2009
Accepted: 3 March 2010

Abstract

The problem of missing link prediction in complex networks has attracted much attention recently. Two difficulties in link prediction are the sparsity and huge size of the target networks. Therefore, to design an efficient and effective method is of both theoretical interest and practical significance. In this letter, we proposed a method based on local random walk, which can give competitively good or even better prediction than other random-walk–based methods while having a much lower computational complexity.