好,那怎樣叫做一個 random walk?random walk 它其實是這樣來看,就是說
首先一個網路,一個網路的連接的情況, 在這一個 random
walk 裡頭,我們事實上是用一個所謂的 轉移機率矩陣這個 P 來表示,這個矩陣來表示。
那舉一個例來看, 假如說現在我面臨到的這個所謂的這個網路連接情況是這樣,這個
使用者 1 呢他跟隨者使用者 3 跟使用者 2, 使用者 2 呢跟隨使用者 1,使用者 3 跟隨使用者 1,
那這一個幾率矩陣呢,到底要怎麼去來描述這件事情?其實呢它是一個,假如說你有三個點, 那就是一個三乘三的矩陣。
裡頭的任意點,假設這一個點好了,這個點叫做 P12,
代表什麼意思呢?就是說我從 1 這邊 1,這邊
2,從點 1 走到點 2 的幾率 那你看看點 1 現在要麼就走到點
2,要麼就走到點 3,所以它走到點 2 的幾率是多少?是一半,是 0.5。
所以你可以看到, 這個矩陣呢你就可以用來描述這個網路裡頭的連接情況。
好,那有了這個轉移幾率矩陣這個 P
之後呢, 我們現在要來想一件事情,就是所謂 random walk
這邊的 所講到的這件事情,就是說,假如說你今天處在這個網路裡頭, 你開始在裡頭瘋狂地亂逛,一直走來走去,一直走來走去,無窮盡地走來走去,
走來走去,那你走久了以後呢,你會發現到一個有趣的事情, 什麼事情呢?就是說你會發現說你常常會逛到一些特定的點,
OK?那這些點呢會有一些特性,什麼特性?這些點通常都是會有很多人指向它,
為什麼你會常逛到,因為太容易就走向它嘛,對不對?
那除此之外呢?它除了有很多的這個連線指向它,還有什麼樣的特性?
這些從這個連線過來的前面那個點也常常會被走到, 常常會被走到。
好,那我們再呼應到前面我們說影響力 這些想法,我們剛剛講說,一個人有沒有影響力源自於他有沒有很多跟隨者,
對不對?還有這些跟隨者是不是也相對有某種程度的影響力, 那呼應到這邊的
random walk 也是一樣的想法,就是說,如果在網路上亂逛, 你會發現說你很容易走到這些點,這些點為什麼容易走到?因為它有很多的
link 指向它,連接指向它, 它的跟隨者眾,對不對?那再一個是怎樣呢?為什麼你容易找到它?除了它
的跟隨者眾,還有很多連接指向它,你也很容易走到它的上一步。
那這些人,假如說你把這個,這個容易走到這件事想象成影響力,就是說這些人的影響力- 也不差。
好,所以呢,基於這樣的想法,你可以想象下假如說我今天,
在這一個社群網路裡頭,我開始瘋狂地亂逛,瘋狂地亂逛,瘋狂地亂逛, OK。
那久而久之你會發現說,我很很容易就遇到一些人,很容易就遇到一些人。
這些人呢有些特性就是他的跟隨者眾。
而且呢,在這些被跟隨者也是一些很容易被逛到的點,那些邊緣他影響力也不差。
好,所以如果你可以接受這樣的概念上,我們繼續來看, 這個上述這個
random walk 就像我們剛剛講到,用白話方式 你可以說一件事情沒做,但是通常我們需要用一些數量的方法,
來吧一些現象用一些數學方式來做一些表達,你這樣才有辦法 去定義這些數值出來,影響力的數值出來。
好,那上述的這個 random walk 呢其實呢可以用一個數學的方式來表達,那這邊就
會涉及到我們要有一些所謂的線性代數的一些很簡單,非常簡單的概念。
好,那首先第一件事情就是說,我們現在在講說我不斷地走,不斷地走,那假設說我們有時間- 點好了。
用 t 這個變數來表示時間點,那 t=0 當然就是時間點
0,那 t=1 就是下個時間點,2 就是下下個時間點,以此類推。
好,那有了這個時間點的概念之後,我們定義一個向量叫 q,
這個 qt 呢,它是,假如說今天你 網路裡頭有
n 個點,那它的維度呢就有 n 就是它有 n 個格子在裡頭。
那它這裡頭的數值是什麼呢?就是說,第一格就是說你在時間點 t
的時候你逛到這個第一個點的幾率,那第二格是 什麼呢?代表就是你在時間
t 的時候你走到這個點 2 的幾率。
現在呢假設說我們在時間點 t=0 的 情況之下,我們開始還模擬,剛剛我們講到的所謂的 random walk 這件事情好了。
好,那假如說在時間點 t=0 的情況下你現在停在點 1, 那開始你要準備開始瘋狂地去逛這個網路。
那這時候,你的這個所謂的 q0 要怎麼去表示呢?好,我們可以看到下面這個地方來。
這個 q0 可以這樣來表示,就是裡頭格子是這樣子,1,0,0,為什麼呢?你看,你時間點
在 0 的時候你在點 1,這時候你還沒有逛到點 2 跟點 3。
所以你逛到各點的幾率當然就是在點 1 是 100%,點 2 跟點 3 幾率各為 0。
OK?好,那接著呢我們如果想要知道 時間點,在下個時間點 t=1 的時候逛到各點的幾率為何。
我們可以透過這個算式,這個矩陣跟向量乘法的算式來進行驗算。
那這個算式其實非常簡單,首先第一件事情就是說我們必須要把 剛剛之前講到的那個前面那一個
P 的那個幾率矩陣呢做一個 轉置,做一個 transpos。
那所謂的轉置是什麼意思呢?就是原本把這個 ij 這一個格子變成
ji,換句話說就是好像把它映射過去的意思一樣。
好,那這一個式子,這個矩陣乘法意思代表什麼意思呢?其實非常簡單,我們來看。
這裡頭經過轉置,這個 Pt 經過轉置之後呢,它 每一個
row,每一個橫列呢,我們都可以代表說它現在呢 從某個點走到某一個點的幾率。
舉例而言,我們看第一個 row 好了。
第一個 row 代表什麼意思呢?就是說你如果現在呢,想要走回點 1, OK?那如果你現在身處點
1 的時候你回到 1 的幾率是多少,如果你身處在 2 的時候,
點 2 的時候,你走回去點 1 的幾率是多少,如果你現在身處在點 3
的時候,你回到點 1 的幾率是多少,那其實你可以從左邊這個圖形來看。
假如說你現在處在點 1 的話,因為你要往前走到點 2 點 3,你不可能回到點 1,所以它的幾率是 0。
假如說你在點 2 的時候,因為它只有一個指出去的連接,就是回到點 1,
所以你回到點 1 的幾率是百分之百,對不對?那點 3 也是同樣的意思,
好,那透過矩陣乘法呢,我們知道說,這個乘出來的結果,第一格呢 等於這個矩陣的第一個 row 乘上這個第一個 column。
所以乘出來就代表說你現在處於哪一點,你再走回去這一個點的幾率是多少,那你可以來看到- ,乘出來的結果,
q1 就變成 0、 0.5、 0.5,那你可以用直覺去驗證,假如說你現在在點
1 的話, 下個時間點你要麼就是在點 3,要麼就是在點 2,所以跳到這兩點的幾率就是
各 50 percent,對不對?好,那透過這個
非常簡單,非常簡單的矩陣跟向量的預算,於是我們寫到這邊來。
你可以依樣畫葫蘆,你可以算出,現在如果在時間點 1 的時候,我想要在時間點
2 到各點的幾率是多少,你也可以把上面這個式子,只是帶不同的
q 進去,就可以算出下一個 q 時間點 2 的時候,各點造訪的幾率。
那你這樣一直重複,一直重複,重複,重複計算,計算久了,像我們剛剛講到, 所謂 random
walk 就是你在裡頭瘋狂亂逛,對不對? 你可以一直重複,重複計算、
重複算……算很久之後, 你似乎,我們這邊要強調,你似乎就可以得到一個解答。
那假如說你算很久, 算很久,對不對,算很久結果叫 qn,n 可能是非常久的一個時間點。
那你就可以從這個 qn 裡頭去看,哪些點的幾率值特別高,
那這些點呢就是代表你最容易逛到的點,那這些點 按照之前講到的,可能就是一些重要的點。
好, 那你可以看到說,我這邊一直在強調,這邊是說,你似乎就可以 得到這個解答,為什麼說是似乎呢?
主要原因就是說上面這個式子我們還必須要面臨兩個很重要的問題,什麼問題呢?
我們剛剛想想看,我們在隨機亂走,瘋狂亂逛的時候,我們說我們一開始 就停在點
1 嘛,對不對?然後開始進行這個瘋狂的亂逛。
那假如說我一開始出發點就在點 2 或點 3,
會不會影響最後的結果,會不會因為我起始點的不同 最後得到這個亂逛久了以後,那個幾率會不一樣?
那如果不一樣的時候,我該相信從哪個起始點出發才是對的呢?那另外一個問題是什麼呢?
另外一個問題是說,我這樣瘋狂地亂逛,那我要逛多久啊? 我逛一百步,逛一千步,到底什麼時候該停下來?
那其實這個逛多久這個問題,其實衍生到另外一個問題是說, 我是不是能夠說明一件事情,就是說我逛夠久之後,這個
qn 那個 n 是代表時間點,n 很大的時候,是不是 qn 跟
qn+1 開始慢慢變得很相似,最後變成一樣,或者換句話說這個結果會不會收斂?
如果我們沒辦法解答這兩個問題,那其實我在裡頭瘋狂亂逛,我沒有要告訴你一個確切的結果。