醫(yī)學(xué)網(wǎng)絡(luò)平臺(tái)分析-隨機(jī)游走

1、 醫(yī)學(xué)網(wǎng)絡(luò)平臺(tái)分析生物醫(yī)學(xué)軟件工程教研室 隨機(jī)游走(random walk)隨機(jī)游走簡(jiǎn)介 隨機(jī)游走（Random Walk），是一種數(shù)學(xué)統(tǒng)計(jì)模型，它由一連串的軌跡所組成，其中每一次都是隨機(jī)的。它能用來表示不規(guī)則的變動(dòng)形式，如同一個(gè)人酒后亂步，所形成的隨機(jī)過程記錄。 日常生活中有很多自然現(xiàn)象與隨機(jī)游走有關(guān)，如氣味的擴(kuò)散、氣體分子的運(yùn)動(dòng)、滴入水中的墨水等。Random Walk是擴(kuò)散過程的基礎(chǔ)，因此它被廣泛地用于對(duì)物理和化學(xué)等擴(kuò)散現(xiàn)象的模擬上。在應(yīng)用數(shù)學(xué)上，Random Walk是利用隨機(jī)因素模擬真實(shí)的動(dòng)力系統(tǒng)的常用方法。圖 (a)和(b)分別顯示的是Random Walk在二維和三維空間的模擬圖

2、。 此外，Random Walk又是設(shè)計(jì)隨機(jī)算法的一個(gè)非常廣泛的工具，其中一個(gè)典型的例子就是 “馬爾可夫鏈蒙特卡羅”法（MCMC）。MCMC是解決近似計(jì)算問題一種重要方法，它能以比確定性算法快指數(shù)級(jí)的速度提供解決問題的最好隨機(jī)方法，目前已經(jīng)被廣泛地應(yīng)用在統(tǒng)計(jì)領(lǐng)域。 關(guān)于在一維或者多維空間中隨機(jī)游走，數(shù)學(xué)上已經(jīng)有一些有趣的證明。 假設(shè)有一條水平直線，從某個(gè)位置出發(fā)，每次有50%的概率向左走1米，有50%的概率向右走1米。按照這種方式無(wú)限的隨機(jī)游走下去，最終能回到出發(fā)點(diǎn)的概率是多少？ 答案是100%。即在一維隨機(jī)游走過程中，只要時(shí)間足夠長(zhǎng)，最終總能回到出發(fā)點(diǎn)。假設(shè)有一個(gè)喝醉的酒鬼，他在街道上隨機(jī)游

3、走，而整個(gè)城市的街道呈網(wǎng)格狀分布，酒鬼每走到一個(gè)十字路口，都會(huì)概率均等的選擇一條路（包括自己來時(shí)的那條路）繼續(xù)走下去。那么他最終能回到出發(fā)點(diǎn)的概率是多少？答案也是100%。開始時(shí)，酒鬼可能會(huì)越走越遠(yuǎn)，但最終他總能找到回家的路。 假設(shè)有一醉酒的小鳥在飛行，每次都從上、下、左、右、前、后中概率均等的選擇一個(gè)方向，那么它很有可能永遠(yuǎn)也回不到出發(fā)點(diǎn)。事實(shí)上，在三維網(wǎng)格中隨機(jī)游走，最終能回到出發(fā)點(diǎn)的概率只有大約34%。 上面的定理是著名數(shù)學(xué)家波利亞（George Plya）在1921年證明的。隨著維度的增加，回到出發(fā)點(diǎn)的概率將變得越來越低，在四維網(wǎng)格中隨機(jī)游走，最終能回到出發(fā)點(diǎn)的概率是19.3%，而在八

4、維空間中，這個(gè)概率只有7.3%。圖中的隨機(jī)游走 圖上的Random Walk 是指給定一個(gè)圖和一個(gè)出發(fā)點(diǎn)，隨機(jī)地選擇一個(gè)鄰居結(jié)點(diǎn)，移動(dòng)到鄰居結(jié)點(diǎn)上，然后把當(dāng)前結(jié)點(diǎn)作為出發(fā)點(diǎn)，重復(fù)以上過程。 那些被隨機(jī)選出的結(jié)點(diǎn)序列就構(gòu)成了一個(gè)在圖上的Random Walk 過程，如下圖所示：圖中顯示螞蟻在三個(gè)結(jié)點(diǎn)組成的圖上Random Walk 的過程，邊上數(shù)字是轉(zhuǎn)移概率，(a)-(d)分別顯示t=0,1,2,3這四種時(shí)刻的螞蟻的狀態(tài)。 對(duì)于給定的一個(gè)圖，隨機(jī)游走是考慮圖的全局結(jié)構(gòu)特征模擬游走者的隨機(jī)游走行為，從給定的出發(fā)點(diǎn)（源結(jié)點(diǎn)或種子結(jié)點(diǎn)）隨機(jī)游走到鄰居結(jié)點(diǎn)，隨后再將當(dāng)前結(jié)點(diǎn)作為出發(fā)點(diǎn)，重復(fù)以上過程，直到

5、達(dá)到平穩(wěn)狀態(tài)。 自上個(gè)世紀(jì)八十年代以來，圖上的Random Walk就開始吸引研究者的目光。大量的研究者，包括頂尖圖論專家L.Lovsz，F(xiàn).Chung,B.Bollobas，R.Kannan等，都研究圖與Random Walk之間的連接關(guān)系，他們從理論上深入地研究了Random Walk在圖上的平均首達(dá)時(shí)間，平均往返時(shí)間，平均覆蓋時(shí)間，以及混合時(shí)間和特征值等問題。 這里我們給出一些可以參考的理論著作：一個(gè)比較好的關(guān)于圖上的Random Walk 的理論研究綜述是由Lovsz 給出的;Lovsz, L, Random walks on graphs: a survey. In Combinat

6、orics, Paul Erdos is eighty, Vol.2, pp. 353397, 1993. 在線的關(guān)于圖上的Random Walk理論書籍是Aldous和Fill的Reversible Markov Chains and Random Walks on Graphs； 隨機(jī)圖上的Random Walk理論書籍是Hughes的Random Walk in Random Environment。隨機(jī)游走的應(yīng)用 理論研究為Random Walk 的應(yīng)用提供了一個(gè)堅(jiān)實(shí)的基礎(chǔ)，而Random Walk在圖上應(yīng)用的一個(gè)亮點(diǎn)則最早出現(xiàn)在信息檢索領(lǐng)域。 早期的搜索引擎例如Yahoo！使用的是關(guān)

7、鍵詞匹配技術(shù)，其性能容易受到關(guān)鍵詞頻率的欺騙，所以搜索效果不是很好。 但是到1998 年Jon Kleinberg 提出了HITS算法，以及Sergey Brin 和Larry Page 提出了PageRank算法之后，搜索的正確率就得到了巨大的改觀，其原因就是這兩種技術(shù)都建立在共同理論支柱就是圖上的Random Walk上。 隨后，Brin 和Page 利用PageRank 技術(shù)成立了Google 公司，而今天Google已經(jīng)在人們的日常生活中顯示出巨大影響，所以可以毫不夸張地說Random Walk改善了今天的生活。下圖為PageRank 的一般描述示意圖，邊上顯示的是轉(zhuǎn)移概率，而網(wǎng)頁(yè)上除

8、了ID 外顯示的是頁(yè)片的Rank 值。Google 的PageRank 一般描述 在信息檢索領(lǐng)域方面，Random Walk 除了被用在網(wǎng)頁(yè)的連接分析之外，還被應(yīng)用到私人PageRank、Rank 的穩(wěn)定性、以及結(jié)點(diǎn)的相似性等方面。在電路網(wǎng)絡(luò)和電力網(wǎng)格方面，Random Walk 也有很廣泛的應(yīng)用。而在P2P 網(wǎng)絡(luò)（對(duì)等互聯(lián)網(wǎng)絡(luò)）領(lǐng)域， Random Walk 則被用于P2P 搜索，拓?fù)錁?gòu)建，同等采樣等方面。 此外，在復(fù)雜網(wǎng)絡(luò)方面，Random Walk還被應(yīng)用于蛋白質(zhì)網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)的分析等方面。圖a 和圖b所示的是復(fù)雜網(wǎng)絡(luò)中的蛋白質(zhì)交互網(wǎng)絡(luò)，社會(huì)關(guān)系網(wǎng)絡(luò)的示意圖。蛋白質(zhì)交互網(wǎng)絡(luò)社會(huì)關(guān)系網(wǎng)絡(luò)

9、由于在網(wǎng)絡(luò)上的成功應(yīng)用，Random Walk 也逐漸開始吸引機(jī)器學(xué)習(xí)研究者的目光，并開始被應(yīng)用于半監(jiān)督學(xué)習(xí)，聚類分析，圖像分割和圖的匹配等問題上。與Random Walk 相關(guān)的擴(kuò)散核也被應(yīng)用于基于核的學(xué)習(xí)等方面。重啟動(dòng)的隨機(jī)游走(Random Walk with Restart) 重啟動(dòng)的隨機(jī)游走（Random Walk with Restart，簡(jiǎn)稱RWR）是隨機(jī)游走分析的一種變形，游走者可以以一定的概率回到源結(jié)點(diǎn)，RWR主要用于計(jì)算圖中結(jié)點(diǎn)之間的結(jié)構(gòu)相關(guān)性，它已經(jīng)被廣泛的應(yīng)用于疾病基因預(yù)測(cè)、藥物靶點(diǎn)預(yù)測(cè)等生物信息學(xué)研究領(lǐng)域。 RWR方法的主要思想是：游走者從圖中某個(gè)結(jié)點(diǎn)或某些結(jié)點(diǎn)出發(fā)，

10、沿著圖中的邊隨機(jī)游走，在任意結(jié)點(diǎn)上，以一定的概率隨機(jī)選擇與該結(jié)點(diǎn)相鄰的邊，沿著邊移動(dòng)到下一個(gè)結(jié)點(diǎn)，或者以一定的概率回到原來的結(jié)點(diǎn)，經(jīng)過有限次的隨機(jī)游走后，游走者到達(dá)圖中每個(gè)結(jié)點(diǎn)的概率值達(dá)到平穩(wěn)狀態(tài)。此時(shí)，每個(gè)結(jié)點(diǎn)的概率值可以用來衡量該結(jié)點(diǎn)與源結(jié)點(diǎn)聯(lián)系的緊密程度（也可以稱為關(guān)聯(lián)度或者相似度）。 W:圖的列向量歸一化的鄰接矩陣。P0:初始概率向量，對(duì)于每一個(gè)種子結(jié)點(diǎn)，以相 等的概率分配，向量中各元素之和為1。r:游走者返回種子結(jié)點(diǎn)的概率（重啟動(dòng)概率），r的值越接近于0，表示隨機(jī)游走方法考慮圖的全局結(jié)構(gòu)特征越多。 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