医学网络平台分析-随机游走

1、 医学网络平台分析生物医学软件工程教研室 随机游走(random walk)随机游走简介 随机游走（Random Walk），是一种数学统计模型，它由一连串的轨迹所组成，其中每一次都是随机的。它能用来表示不规则的变动形式，如同一个人酒后乱步，所形成的随机过程记录。 日常生活中有很多自然现象与随机游走有关，如气味的扩散、气体分子的运动、滴入水中的墨水等。Random Walk是扩散过程的基础，因此它被广泛地用于对物理和化学等扩散现象的模拟上。在应用数学上，Random Walk是利用随机因素模拟真实的动力系统的常用方法。图 (a)和(b)分别显示的是Random Walk在二维和三维空间的模拟图

2、。 此外，Random Walk又是设计随机算法的一个非常广泛的工具，其中一个典型的例子就是 “马尔可夫链蒙特卡罗”法（MCMC）。MCMC是解决近似计算问题一种重要方法，它能以比确定性算法快指数级的速度提供解决问题的最好随机方法，目前已经被广泛地应用在统计领域。 关于在一维或者多维空间中随机游走，数学上已经有一些有趣的证明。 假设有一条水平直线，从某个位置出发，每次有50%的概率向左走1米，有50%的概率向右走1米。按照这种方式无限的随机游走下去，最终能回到出发点的概率是多少？ 答案是100%。即在一维随机游走过程中，只要时间足够长，最终总能回到出发点。假设有一个喝醉的酒鬼，他在街道上随机游

3、走，而整个城市的街道呈网格状分布，酒鬼每走到一个十字路口，都会概率均等的选择一条路（包括自己来时的那条路）继续走下去。那么他最终能回到出发点的概率是多少？答案也是100%。开始时，酒鬼可能会越走越远，但最终他总能找到回家的路。 假设有一醉酒的小鸟在飞行，每次都从上、下、左、右、前、后中概率均等的选择一个方向，那么它很有可能永远也回不到出发点。事实上，在三维网格中随机游走，最终能回到出发点的概率只有大约34%。 上面的定理是著名数学家波利亚（George Plya）在1921年证明的。随着维度的增加，回到出发点的概率将变得越来越低，在四维网格中随机游走，最终能回到出发点的概率是19.3%，而在八

4、维空间中，这个概率只有7.3%。图中的随机游走 图上的Random Walk 是指给定一个图和一个出发点，随机地选择一个邻居结点，移动到邻居结点上，然后把当前结点作为出发点，重复以上过程。 那些被随机选出的结点序列就构成了一个在图上的Random Walk 过程，如下图所示：图中显示蚂蚁在三个结点组成的图上Random Walk 的过程，边上数字是转移概率，(a)-(d)分别显示t=0,1,2,3这四种时刻的蚂蚁的状态。 对于给定的一个图，随机游走是考虑图的全局结构特征模拟游走者的随机游走行为，从给定的出发点（源结点或种子结点）随机游走到邻居结点，随后再将当前结点作为出发点，重复以上过程，直到

5、达到平稳状态。 自上个世纪八十年代以来，图上的Random Walk就开始吸引研究者的目光。大量的研究者，包括顶尖图论专家L.Lovsz，F.Chung,B.Bollobas，R.Kannan等，都研究图与Random Walk之间的连接关系，他们从理论上深入地研究了Random Walk在图上的平均首达时间，平均往返时间，平均覆盖时间，以及混合时间和特征值等问题。 这里我们给出一些可以参考的理论著作：一个比较好的关于图上的Random Walk 的理论研究综述是由Lovsz 给出的;Lovsz, L, Random walks on graphs: a survey. In Combinat

6、orics, Paul Erdos is eighty, Vol.2, pp. 353397, 1993. 在线的关于图上的Random Walk理论书籍是Aldous和Fill的Reversible Markov Chains and Random Walks on Graphs； 随机图上的Random Walk理论书籍是Hughes的Random Walk in Random Environment。随机游走的应用 理论研究为Random Walk 的应用提供了一个坚实的基础，而Random Walk在图上应用的一个亮点则最早出现在信息检索领域。 早期的搜索引擎例如Yahoo！使用的是关

7、键词匹配技术，其性能容易受到关键词频率的欺骗，所以搜索效果不是很好。 但是到1998 年Jon Kleinberg 提出了HITS算法，以及Sergey Brin 和Larry Page 提出了PageRank算法之后，搜索的正确率就得到了巨大的改观，其原因就是这两种技术都建立在共同理论支柱就是图上的Random Walk上。 随后，Brin 和Page 利用PageRank 技术成立了Google 公司，而今天Google已经在人们的日常生活中显示出巨大影响，所以可以毫不夸张地说Random Walk改善了今天的生活。下图为PageRank 的一般描述示意图，边上显示的是转移概率，而网页上除

8、了ID 外显示的是页片的Rank 值。Google 的PageRank 一般描述 在信息检索领域方面，Random Walk 除了被用在网页的连接分析之外，还被应用到私人PageRank、Rank 的稳定性、以及结点的相似性等方面。在电路网络和电力网格方面，Random Walk 也有很广泛的应用。而在P2P 网络（对等互联网络）领域， Random Walk 则被用于P2P 搜索，拓扑构建，同等采样等方面。 此外，在复杂网络方面，Random Walk还被应用于蛋白质网络和社会网络的分析等方面。图a 和图b所示的是复杂网络中的蛋白质交互网络，社会关系网络的示意图。蛋白质交互网络社会关系网络

9、由于在网络上的成功应用，Random Walk 也逐渐开始吸引机器学习研究者的目光，并开始被应用于半监督学习，聚类分析，图像分割和图的匹配等问题上。与Random Walk 相关的扩散核也被应用于基于核的学习等方面。重启动的随机游走(Random Walk with Restart) 重启动的随机游走（Random Walk with Restart，简称RWR）是随机游走分析的一种变形，游走者可以以一定的概率回到源结点，RWR主要用于计算图中结点之间的结构相关性，它已经被广泛的应用于疾病基因预测、药物靶点预测等生物信息学研究领域。 RWR方法的主要思想是：游走者从图中某个结点或某些结点出发，

10、沿着图中的边随机游走，在任意结点上，以一定的概率随机选择与该结点相邻的边，沿着边移动到下一个结点，或者以一定的概率回到原来的结点，经过有限次的随机游走后，游走者到达图中每个结点的概率值达到平稳状态。此时，每个结点的概率值可以用来衡量该结点与源结点联系的紧密程度（也可以称为关联度或者相似度）。 W:图的列向量归一化的邻接矩阵。P0:初始概率向量，对于每一个种子结点，以相 等的概率分配，向量中各元素之和为1。r:游走者返回种子结点的概率（重启动概率），r的值越接近于0，表示随机游走方法考虑图的全局结构特征越多。 0.3=0.1*0+0.9*0*(1/4)+0.9*0*(1/2)+0.9*0*(1/2)+0.9*1*(1/3)1432567910811120.130.100.130.130.050.050.080.040.020.040.03OntheFly:143256791081112Random walkNode 4Node 1Node 2Node 3Node 4Node 5Node 6Node 7Node 8Node 9Node 10Node 11Node 120.130.100.130.220.130.050.050.080.040.030.040.021432567910811120.130.100.130.130.050.050