那這個演算的方法其實可以透過下面這幾行這個演算的方法來 幫我們完成去計算這個每個點,在
random walk 情境之下 它的影響力。
好,首先呢,演算的過程第一步就是說 給定你一個網路,首先你就是要依照這個網路的連結情況
去產生這個所謂的,我們剛才看到了,那個矩陣 p。
好,那接下來第二件事情呢你必須要先定義好說,你今天 teleport
發生的可能性是多少,那當然就是 α 這個值你要設定。
那有了 α 這個值之後呢,你就可以按照我們剛剛講到的說,你可以結合原本的按照連結產生出來這個轉-
移的矩陣, 跟 teleport 亂飛產生出來的這個轉移矩陣,你把這兩個矩陣按照 α 這個配重去產生這個 p'。
好,那接下來呢,這個矩陣已經 ready
之後, 我們剛剛講到,你怎麼去算出最後結果,你就是亂逛嘛,對不對?
好,那亂逛的時候,你現在就設 n=0,n 是一個時間點的意思。
你就是隨機去產生一個所謂 q0,q0 就是我們剛看到一開始起始點的那個
起始點落在哪一點,那一點就是距離為 1,其他都是 0。
這邊講到 隨機,其實你可以很放心,為什麼?因為你今天就算在點 1 開始,點 2 開始,點 3 開始,任何點開始,
透過剛剛的這個 teleport 機制,其實都不會影響最後的結果。
好,那接下來你產生 q0 之後呢,你就可以用我們剛剛講到的非常簡單的這個所謂矩陣的這個所謂的運算,去算
q n+1 的情況之下,那個造訪各點的這個機率是多少。
那不斷地遞回、 遞回、 遞回,這邊 n+1 就是時間點再 +1。
那你不斷遞回之後,你就開始累計下個時間點造訪各點的機率是多少,下個時間點的機率- 是多少,
如果你發現,算了很久之後你發現,這個時間點跟下個時間點也就是 qn 跟
q n+1 這兩個時間點算出來的結果 幾乎一樣,或是根本就是一樣,那代表什麼意思?
你可以不用再瘋狂逛了,它已經收斂了,那這時候你就可以停止。
假如說你發現這一輪算出來的這個 q 跟下一輪算出來的
q 結果不一樣,那怎樣?代表你還沒有收斂,你就繼續
重複我們剛剛講到的這個矩陣運算代表這個走下一步的這件事情。
繼續在裡頭瘋狂逛,逛到什麼,直到收斂為止,好。
那如果它收斂呢,最後你就可以怎樣?去觀察這個 qn 裡頭的值。
okay,這 qn 是代表你造訪各點的機率嘛,對不對? 當然機率越高,代表你常會逛到它,對不對?
那這裡頭值高的元素就代表這裡頭 這些點是重要,那反映回去,我們要分析這個 social
network,就代表 這些使用者他事實上是比較重要的使用者,換句話說就是有影響力的使用者。
那剛剛講到是用這個所謂寫程式演算法的方式來做,那假如說你
今天說我可能並不是那麼在行,對於寫程式並不是那麼的有把握,
有沒有其他的方式能夠幫我算出最後收斂出來的這個 qn
值呢? 那其實有另外一種算法,那種算法怎麼做呢?
各位可以想想看,假如說今天我們回到剛剛那一個瘋狂亂逛的結果。
假設你逛好久,逛好久,逛好久,你就會發現說這一輪的 q 跟下一輪的
q 一樣, 假設我們說這個 q 造訪各點這個機率這個
向量叫做 q stable,它已經收斂了,穩定了。
那你可以發現,如果它已經收斂,你再透過這個矩陣的這個
乘法的運算,你還會得到相同的結果,不然它不叫收斂嘛,對不對,結果要一樣。
好,那這個式子是不是很相似,假如說各位同學如果對於這個所謂線性代數很熟悉的話,
你可以知道說,如果一個向量乘上一個矩陣,會得到這個向量再乘上一個值。
那這個東西代表什麼?代表就是 eigenvector 跟 eigenvalue。
它的最基本的定義。
那你可以,假如說我今天在前面擺上個 1, 是不是就等於這邊我寫上的這個 eigenvector
eigenvalue 的定義 的公式一模一樣,只是說現在這個 eigenvalue 的值會等於 1。
好,換句話說呢,如果你今天不想要自己去寫我們剛剛講到的那個瘋狂亂逛的程式,
你想要透過一些其他方法來解,其實是有的,怎麼做呢? 也是一樣,你首先呢先去把我們剛剛講到集合
teleport 之後, 那個轉移的矩陣 p' 求出來,okay,
p' 求出來之後,你要做什麼事情?你找一個市面上幾乎每個商用的統計軟體都可以勝任,
你隨便找一個商用的統計軟體,做什麼事呢? 去求這個 p 的特徵向量跟特徵值,也就是 eigenvalue 跟 eigenvector。
像如果各位同學比較常用的像是 R 或 MATLAB, 它都有這樣的功能。
求出來之後呢,你去找 哪一個特徵向量它對應到的特徵值是 1,那個特徵向量就是你要的解。
那得到那個特徵向量之後呢,你就也是一樣,按照上面講的步驟,你去檢查這個向量裡頭
哪一個元素值最高,那個元素對應到的那個點 okay,就是這個網絡裡頭最重要的點。
好,所以 PageRank 呢這邊講了它基本的概念,還有它兩種算法,一個就是說
你可以用這個瘋狂亂逛的做法,另外一個方法就是說你可以用一個商用統計軟體的方式幫- 你去求。
所以這地方其實兩種方法都是很常用的,好。
那講完了這一個 PageRank 之餘,這個所謂找出 這個重要的意見領袖之後,我們其實還有一些細節必須要討論。
首先第一件事情要討論的是什麼呢?就是說我們剛剛在建立轉移的機率的
矩陣的時候,我們是把所有的連結都視為均等的,對不對,還記得嗎? 我們剛剛講說,連點 1,有兩個連結,一個連結到 2,一個連結到
3, 對不對?那這時候呢,它走到 2 的機率是 50%,走到 3 機率是
50%,對不對,但是實際上你一定要用這種所謂均等的方式來調配這個走出去的機率嗎? 不見得嘛,對不對。
假設你想想看,假設今天這個使用者跟這使用者 它其實呢,有好友關係,但是他們發出來的文章並不是那麼相似。
但這個使用者跟這個使用者也好友關係,他們發出來的文章都是在討論一樣的興趣, 那當然你認為他們之間關係會比較緊密嘛,對不對。
所以不見得你 必須都要用均等的方式,那甚至我們今天講到這個 10
年這一篇論文裡頭 它其實就是利用一些文本分析方法,去分析使用者在
Twitter 上面 發文相似性,然後去調整這個所謂的轉移的一個機率,進而找出這個所謂的意見領袖。
所以不見得一定要均等地去分配這個轉移的機率。
好,那第二個問題是說,我們今天如果要運用的情景它並不是
有這個所謂的很明顯的這個跟隨者跟被跟隨者這個連結的情況,
那怎樣去建立這一個網路,怎樣去建立這一個相對應的這個轉移的這個機率的矩陣呢?
那其實呢,這地方也有人是這樣做了,就是說我們可以分析使用者互動,就比如說,我今天
要分析一個論壇,我發現說這個使用者總是跟這個使用者 有互動。
發了文,他就按推文或按贊,某種程度就是一種跟隨、 一種概念。
那我可以統計相關的這個次數,來產生這個走過去的這個機率。
對不對。
所以不見得你要有明顯顯性的這個網路關係,有些隱性的使用者互動
那當然這個互動必須要由於某種程度是有跟隨的這種意味存在,那你就可以利用這些使用者互- 動,這些資訊
來建立這個轉移的這個機率的這個矩陣。
好,那在第三個問題還是一個老問題,就是我們剛剛 teleport 對不對,我們剛看到說你在任何時間點都可以跳到任一個點,
那那時候我們舉的例子是說,假設現在這個網路有三個點,任何一個時間點跳到這個 123
這個點的機率都是 1/3, 可是一定要 1/3 嗎,我們一定要機率均等嗎? 也不見得嘛,對不對。
我們可以,如果你有一些先驗的知識, 我知道說現在這個網路裡頭,有些人可能就是已知的一些已成名的人,
那我跳到他的機率也許可以比較大,那跳到其他人的機率也許機率就比較小一點,所以不見得
要用一個所謂的均等的方式去建造這個所謂 teleport
它的那個轉移的矩陣,你可以用一些 自己的獲得到的一些先驗知識來做一些調配。
但是要注意一件事情,就是說我們必須要能夠保證就是 我們加入
teleport 之後,你必須要能保證最後那個 p' 它要滿足 aperiodic
還有 irreducible 這兩個特性,不然如果這兩個特性沒有辦法保持的話,
那可能你最後這個瘋狂亂逛,瘋狂亂逛,你可能就不會收斂。
那你也許你要找這個 eigenvector 會求不出解來。
那今天我們主要介紹 了兩個主題,一個是群落偵測,一個就是意見領袖的找尋。
那在這個社群媒體蓬勃發展的時代啊,每個人都有可以表達自己的意見,
那如何從這個廣大的社群網路這麼多的使用者裡頭 去找出一群一群他們彼此也許有不同的看法
的使用者群落,是一個了解輿情的非常重要的一個關鍵了。
那除此之外,也由於每個人都可以表達意見,如何從這麼多的使用者裡頭去找出具代表性的意- 見領袖,
去參考他們的意見,也是輿情分析一個重要的課題。
那以上就是我們今天所上的單元,謝謝各位!