随机游走(RandomWalk)问题直观:有个醉汉走在回家路上,由于酒醉未醒,分不清家往哪边走。假如家在东面n的位置,醉汉处在m(m<n)位置。醉汉每一个时间单位走一步,向东(家的方向)或者向西(酒吧的方向)的概率皆为1/2。 这个醉汉的行为就可用randomwalk来模拟。这是一个简单的一维随机游走问题模型,从这个模型中我们可以对随机游走有一个直观上的感受:每一步都是随机的。什么是随机游走随机游走是由一系列随机步伐(steps)所形成的活动模型。比如:液体或空气中分子的运动;动物的觅食;股票的价格波动;一个赌徒的财产状况…这些都可以模型为randomwalks(尽管现实中他们可能不是真正的随机)KarlPearson在1905年第一次提出了randomwalk,如今已被应用在诸多领域:生态学、经济学、心理学、计算机科学、物理学、化学、生物学等。随机游走概述一维随机游走上述问题可以用杨辉三角来看:当n趋于无穷的时候,就可以与中心极限定理相联系一维随机游走一维随机游走模拟结果图:高维随机游走模拟二维模拟:一个25000步伐的二维随机游走三维模拟:高斯随机游走带重启的随机游走(RWR)Randomwalkwithrestart:从一个节点开始,在每一步游走时面临两个选择:或者移动到一个随机选择的邻点;或者跳回起点。RWR最初是为图像分割而提出的一个算法,它反复的探究一个网络的总体结构去估计两个节点之间的亲和力程度(亲和力分数),这个算法只考虑一个参数r:“重启概率”(1-r的概率移动到某个邻点)这个过程反复迭代进行下去直到走遍所有节点,此时得到的概率向量包含所有节点与起点的亲和力分数。另外,RWR的起点也可以选择一个起点集合(多个起点组成的集合)。RMR实例
随机游走 来自淘豆网m.daumloan.com转载请标明出处.
