Random Walk 随机游走


Random Walk
Random Walk with Restart
Fast Random Walk

What’s Random Walk ?

Quoting from 重启随机游走算法(RWR)


What’s Random Walk with Restart(RWR) ?

Let’s have some brief about RWR at first.
Quoting from What is Random Walk with Restart (RWR)?, it says :

RWR is a algorithm originally proposed for image segmentation. It iteratively explores the global structure of the network to estimate the proximity (affinity score) between two nodes. Starting at a node, the walker faces two choices at each step: either moving to a randomly chosen neighbor, or jumping back to the starting node. This algorithm only contains one fixed parameter r called ‘the restarting probability’ (with 1 − r for the probability of moving to a neighbor). After iteratively reaching stability, the steady probability vector contains the affinity score of all nodes in the network to the starting node. This steady probability vector can be viewed as the ‘influential impact’ over the network imposed by the starting node.

In addition to a single starting node, RWR can be extended to a set of starting nodes. In this context, the resulting steady probability vector can also be considered as the ‘influential impact’ over the network, but collectively imposed by a set of starting nodes.

The steady probability vector for a set of starting nodes can be calculated according to the steady probability vector for single starting nodes. For this reason, it is useful to pre-compute affinity matrix for nodes in the graph with respect to each starting node as a seed (by looping over every node in the graph). The motivation behind this is that this pre-computed affinity matrix can be extensively reused for obtaining affinity scores between any combinations of nodes. For instance, such a strategy can dramatically relieve the computational burden involved in sampling a large number of random node combinations. Therefore, this pre-computation does permit some flexibility in the downstream use, in particular for statistical testing.

Some features can be extracted from this quoting.
At first , RWR was first proposed for image sementation. Automatic Multimedia Cross-modal Correlation Discovery. It was proposed to solve the problem about proximity of two node in graph. Second, only one parmeter r ( restarting probability) and two choices (1.jumping batch to the starting node 2. move to a randomly chosen neighbor). After iteratively reaching stablility, the steady probability vector contains affinity score of all nodes in the graph to the starting node. That means in intuition, the more far away node from the starting node ,the less influence it has to the starting node.



affinity n. 类似, 近似, 密切关系.
burden n. 负担, 包袱, 责任 vt. 使烦恼, 劳累.
flexibility n. 柔度, 灵活性.