Louvain、Lpa、Infomap算法
前面我們說過圖的第二個優(yōu)點是拉幫結(jié)派，在圖里面是很容易形成團伙結(jié)構(gòu)，近年來，研究這個問題的論文也是汗牛充棟。本章，我們就這一問題所衍生出來的兩個方向：社區(qū)檢測（Community Detection）和高密子圖挖掘（Dense Subgraph Mining）作相關(guān)講解。
本文，我們先講社區(qū)檢測的相關(guān)算法。社區(qū)檢測的任務(wù)是什么呢？舉個例子，給定如下圖。
直觀印象告訴我們，該圖存在以下的社區(qū)結(jié)構(gòu)：
像這樣，從給定圖中，將各節(jié)點劃分到相應(yīng)社團的任務(wù)稱為社區(qū)檢測。值得注意的一點是，一般當我們在說社區(qū)檢測的時候，節(jié)點都是同態(tài)的，類型都一樣。
本文會重點介紹三個最流行的社區(qū)檢測算法Louvain、Lpa、Infomap，最后對社區(qū)檢測作一些補充說明。
Louvain算法
Louvain算法是一種基于模塊度的社區(qū)檢測算法，由于其良好的效率與穩(wěn)定性而廣受歡迎。網(wǎng)上也有基于Spark GraphX 的開源實現(xiàn)版本。
模塊度（Modularity）
同很多無監(jiān)督的聚類算法一樣，衡量指標是一個至關(guān)重要的因素，很多時候，我們只需要定義好這個指標，然后選擇啟發(fā)式的更新方法去不斷優(yōu)化這個值。一個算法的大概骨架也就出來了。當然一個好的社區(qū)衡量指標要符合基本邏輯：社區(qū)內(nèi)聯(lián)系緊密，社區(qū)間聯(lián)系松散。在06年《Modularity and Community structure in networks 》一文中，作者Newman 給出了如下Modularity的定義：
m表示圖中邊的數(shù)量；
c表示某個社區(qū)；
Ec表示社區(qū)c內(nèi)邊的數(shù)量；
表示社區(qū)c節(jié)點的度之和（包含與其他社區(qū)相連邊的度）
可以這樣去理解上面這個公式：
表示實際情況下，c社區(qū)內(nèi)產(chǎn)生邊的概率
表示在一種理想情況下，給定任意節(jié)點i的的度ki，對節(jié)點i和節(jié)點j進行隨機連邊，邊屬于社區(qū)c的概率期望
于是上式就表示了社區(qū)內(nèi)連邊數(shù)與隨機期望的一個差值。連邊數(shù)比隨機期望值越高，表明社區(qū)劃分的越好。
比如上圖中的：
有了上述模塊度的定義作為鋪墊，Louvain算法就可以啟發(fā)式地去最大化Q值了。
Louvain算法步驟
初始化，將圖中的每個節(jié)點看成一個獨立的社區(qū)；
對每個節(jié)點，依次嘗試把節(jié)點i分配到其鄰居節(jié)點所在的這個社區(qū)計算分配之前與分配之后的模塊度變化△Q，并記錄△Q最大的社區(qū)，如果Max△Q>0，則將該節(jié)點分配到該社區(qū)；
重復(fù)第二步，直到所有節(jié)點的所屬社區(qū)不再變化。
我們看第2步，很像決策樹生長時計算信息熵取最大增益一樣，假設(shè)節(jié)點i移動到社區(qū)c；
移動前模塊度
移動后模塊度
可以看到，△Q的計算只與節(jié)點i和社區(qū)c的連邊有關(guān)，所以這個計算是非常快的，并且也比較容易并行處理。
最后，Louvain算法也可以分層進行，將每一次Louvain算法檢測出來的社區(qū)進行壓縮處理成一個新的節(jié)點，重新構(gòu)圖，繼續(xù)跑Louvain算法，這樣就可以得到層次化的社區(qū)標簽了。
LPA-Label Propagation Algorithm
LPA算法是一個極其簡單的圖傳播算法，其經(jīng)驗假設(shè)是以節(jié)點為中心，進行投票制，十分高效。
算法過程
初始化，將圖中的每個節(jié)點看成一個獨立的社區(qū)；
While所有節(jié)點的社區(qū)標簽不再變化；
統(tǒng)計每個節(jié)點鄰居的社區(qū)，將出現(xiàn)最多次的社區(qū)賦給該節(jié)點，如果出現(xiàn)最多次的社區(qū)有多個，隨機選擇一個社區(qū)賦給該節(jié)點。
算法本身很簡單，分布式實現(xiàn)也很容易。但是這個算法也存在很大的問題：由于存在隨機選擇的情況，所以算法很容易出現(xiàn)振蕩。但這個算法的運行開銷很低，拿來做baseline，作為參考也是可以的。另外，對于一個帶權(quán)重的圖，亦可以考慮帶權(quán)重的投票機制。
Infomap算法
這個算法又稱map equation，是個思路十分清奇的算法。從信息論的角度出發(fā)，假設(shè)一個random worker 在圖上進行隨機游走，那么怎么用最少的編碼長度來表示其路徑呢？也即最小平均比特（minimize bits per step）。一個基本的經(jīng)驗是：
?如果節(jié)點沒有社區(qū)結(jié)構(gòu)，那么直接根據(jù)每個節(jié)點的到達概率，調(diào)用香農(nóng)信息熵公式，就可以得到理論上的最小平均比特；
?如果節(jié)點存在社區(qū)結(jié)構(gòu)，那么社區(qū)內(nèi)的節(jié)點就可以共享社區(qū)的bit位碼，這相當于其本身可以用更少的位碼來表示，所以相比沒有社區(qū)結(jié)構(gòu)的情況，可以得到更小的平均比特；
社區(qū)劃分的越好，那么表示任意一條隨機游走的路徑所需的平均比特就越小。
OK，現(xiàn)在的問題就可以轉(zhuǎn)化為如何在數(shù)學(xué)上量化這個平均比特，如果我們能量化這個衡量標準，那么整個算法的框架就跟前面 Louvain 算法幾乎一致，不斷改變節(jié)點的社區(qū)劃分，啟發(fā)式地去最小化平均比特。
那么首先我們來看看最簡單的情況，所有節(jié)點都屬一個社區(qū)的時候怎么去量化平均比特？
由于節(jié)點都在一個社區(qū)，所以隨機游走每一步都只能是在節(jié)點之間行走，不存在進出其他社區(qū)的事件發(fā)生，如果我們能夠計算出每個節(jié)點的到達概率，就可以依據(jù)信息熵的公式來量化平均比特了：
這里pα表示節(jié)點α的到達概率：
給定一個有向權(quán)重圖，節(jié)點的到達概率怎么計算呢？
一個暴力的辦法是在圖上進行長時間的隨機游走，最后統(tǒng)計每個節(jié)點的出現(xiàn)概率。這個方法很好理解，但是在實際應(yīng)用中，如果圖很大，那就很難奏效了。
其實我們在第二章講到PageRank算法時，就已經(jīng)計算出了這個值。這里我們簡單回顧下，假設(shè)節(jié)點 α 指向 節(jié)點 β 的邊的權(quán)重為：
那么節(jié)點 α 到 節(jié)點 β轉(zhuǎn)移概率：
節(jié)點 α 的到達概率：
那么只要我們初始化了每個節(jié)點的到達概率之后，就可以依據(jù)上述兩式不斷交替迭代式地更新每個節(jié)點的到達概率，這個結(jié)果會很快趨于收斂。
跟PageRank 算法一樣考慮到 DeadEnds和Spider traps的問題，需要一個假想的在整個圖上的隨機跳轉(zhuǎn)概率，所以實際上節(jié)點α 達到概率的更新公式為：
τ 是一個超參數(shù)，表示發(fā)生隨機跳轉(zhuǎn)的概率，一般取0.15。
這樣對計算完的
進行歸一化處理，然后帶到上面信息熵的公式，就可以計算出理論上同屬一個社區(qū)時的最小平均比特了。
現(xiàn)在我們來看一般情況，假設(shè)圖被劃分成 m 個社區(qū)，那么每走一步就可能是以下三種事件中的一種情況：進入某個社區(qū)、從某個社區(qū)中出來、在社區(qū)內(nèi)部節(jié)點間轉(zhuǎn)移。現(xiàn)在我們來定義這三個事件發(fā)生的概率：
在社區(qū)內(nèi)從節(jié)點α 轉(zhuǎn)移到節(jié)點 β 的概率:
進入某個社區(qū) i 的概率：
從某個社區(qū) i 中出來的概率：
有了上面三種事件的概率定義，結(jié)合信息熵公式，我們一樣可以計算出平均比特了。下面我們直接給出計算公式并給出相關(guān)參數(shù)的意義解釋：
將圖劃分成 m 個社區(qū)，編碼隨機游走路徑時的平均比特；
產(chǎn)生進入社區(qū)這種事件的總概率；
進入社區(qū)事件發(fā)生的信息熵；
random worker在社區(qū) i 內(nèi)部的概率，這里包括了在社區(qū)內(nèi)跳轉(zhuǎn)和離開該社區(qū)兩類事件；
random worker 下一步事件發(fā)生在社區(qū) i 內(nèi)部的信息熵；
上面的這個式子就是Infomap算法的核心，亦稱之為 map equation。其本質(zhì)就是從信息論的角度出發(fā)，定義清楚各類事件的發(fā)生概率，依據(jù)信息熵公式，就可以得到此時編碼所需的平均比特了。
上面這個圖就是在不同劃分時候的平均比特的值了，可以看到，同屬一個社區(qū)的時候，編碼需要的平均比特為 4.53 bits, 如果按照左下圖所示，將圖劃分成4個社區(qū)，編碼所需的平均比特只需要3.09bits。值得注意的是，這里依據(jù)概率和Huffman編碼算法給出了各節(jié)點具體的code，實際我們在使用Infomap的時候，并不需要顯式地把每類事件都編碼出來，只需要將各種概率帶入公式計算出平均比特，就知道此時劃分的效果好壞了。
Infomap算法的迭代過程
初始化，對每個節(jié)點都視作獨立的社區(qū)；
while 平均比特的值不再下降；
對圖里的節(jié)點隨機采樣出一個序列，按順序依次嘗試將每個節(jié)點賦給鄰居節(jié)點所在的社區(qū)，取平均比特下降最大時的社區(qū)賦給該節(jié)點，如果沒有下降，該節(jié)點的社區(qū)不變。
Infomap 算法是一個十分優(yōu)秀的算法，同樣支持層次化的社區(qū)劃分，也是三個算法里面唯一支持有向圖的，論文作者也開源了C++ 版本的實現(xiàn)代碼：
http://www.mapequation.org/code.html
另外作者也設(shè)計了一個動態(tài)展示demo：
http://www.mapequation.org/apps/MapDemo.html
demo的相關(guān)說明 ：
http://www.mapequation.org/assets/publications/mapequationtutorial.pdf
總結(jié)
關(guān)于社區(qū)檢測的算法，上面已經(jīng)介紹了三類。其中Louvain 和Infomap 算法都是基于一個合理的全局衡量指標對社區(qū)的劃分不斷進行啟發(fā)式的優(yōu)化。如果從聚類的角度去看待社區(qū)檢測，那么一個基本的范式就是首先得到每個節(jié)點的特征表達，然后基于各種聚類算法進行聚類從而得到社區(qū)的劃分。這里，節(jié)點的特征表達可以從圖的拉普拉斯矩陣獲得，這類方法稱為譜方法；也可以由 graph embedding 的方式習得每個節(jié)點的向量表達，這些相關(guān)的方法我們會在后續(xù)的相關(guān)章節(jié)進行講解。
作者：極驗GEETEST
來源：CSDN
原文：https://blog.csdn.net/geek_wh2016/article/details/81359242
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請附上博文鏈接！
總結(jié)
以上是生活随笔為你收集整理的Louvain、Lpa、Infomap算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 常用内建模块
- 下一篇： JDBC单独了解一下