Random Walk 随机游走

Introduction

Random Walk
Random Walk with Restart
Fast Random Walk

What’s Random Walk ?

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

随机游走算法的基本思想是,从一个或一系列顶点开始遍历一张图。在任意一个顶点,遍历者将以概率1-a游走到这个顶点的邻居顶点,以概率a随机跳跃到图中的任何一个顶点,称a为跳转发生概率,每次游走后得出一个概率分布,该概率分布刻画了图中每一个顶点被访问到的概率。用这个概率分布作为下一次游走的输入并反复迭代这一过程。当满足一定前提条件时,这个概率分布会趋于收敛。收敛后,即可以得到一个平稳的概率分布。

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.

重启随机游走算法是在随机游走算法的基础的改进。从图中的某一个节点出发,每一步面临两个选择,随机选择相邻节点,或者返回开始节点。算法包含一个参数a为重启概率,1-a表示移动到相邻节点的概率,经过迭代到达平稳,平稳后得到的概率分布可被看作是受开始节点影响的分布。重启随机游走可以捕捉两个节点之间多方面的关系,捕捉图的整体结构信息。

Words

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

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据