In this paper we estimate the context-insensitive relevance score between two nodes using one of the most widely used algorithm -Random Walk with Restart (RWR) (Tong et al., 2006), which can be fast computed and has been successfully used in many applications, like personalized PageRank (Haveliwala, 2003), image retrieval (He et al., 2004), etc.
rWr models the relevance score between node i and node j in a graph G as the steadystate probability ri,j, i.e., the probability of a random walk starts from node i will end at node j.