社區發現演算法綜述—part2—infomap

  • 2020 年 5 月 23 日
  • AI

infomap這個演算法確實不好理解,所以獨立開一章來學習。

首先回顧下louvain的演算法實現過程:

而infomap的演算法實現過程:

1、最開始,每個原始節點堪稱一個獨立的社區;

2、對圖裡的節點隨機取樣出一個序列,按順序依次嘗試將每個節點賦給鄰居節點所在的社區,取平均比特下降最大時的社區賦給該節點,如果沒有下降,該節點的社區不變;

3、重複步驟2直到平均每步編碼長度收斂為止。

louvain和infomap都是遵循一種自下而上的思路,類似於凝聚聚類,而不同之處在於:

1、louvain使用模組度增益而infomap使用平均比特增益用於決定如何合併社區;

2、louvain遍歷所有節點的鄰節點而infomap則是通過random walk隨機取樣;

下面就來詳細解釋一下:

數據壓縮與資訊熵 – 阮一峰的網路日誌www.ruanyifeng.com圖標

首先需要了解,資訊熵(對,就是西瓜書的決策樹那一章節里的那個資訊熵,二者是完全相同的)和平均每步編碼長度的關係。上述的文章寫的非常清晰易懂,這裡就不複製黏貼了,給定了關於數據壓縮的背景,

資訊熵=最小平均編碼長度

原文來自:

最小熵原理(五):「層層遞進」之社區發現與聚類 – 科學空間|Scientific Spaceskexue.fm圖標

我們常說資訊熵用于衡量事物的不確定性,資訊熵越大則不確定性越小,早期的決策樹通過分裂,是一個不斷的降低資訊熵,也就是降低不確定性的過程,而infomap則是從平均編碼長度的角度來論述資訊熵在該演算法中的角色; 可以看到,數據中概率的分布越均勻(數據的不確定性越大),則理論最短平均編碼越大,即資訊熵越大

而infomap 的設計目的,是為了:

Infomap 將社區發現同資訊編碼(數據壓縮)聯繫到了一起。一個好的社區劃分,可以帶來更短的編碼。所以,如果能量化編碼長度,找到使得長度最短的社區劃分,那就找到了一個好的社區劃分。

這是infomap的重要思想。(直觀上來體會也比較讓人好接受,假設我們沒有劃分社區,也就是假設每一個節點都是一個社區,那麼對於人類的直觀感受來說原始的圖數據的混亂程度很高,資訊熵大,如果說節點有序的劃分為不同的社區,對於人類的直觀感受來說原始的圖數據的混亂程度就降低了)

注意,我們這裡談及的編碼都是 二進位編碼的形式,也就是編碼的方式都是通過0,1的方式來進行編碼的

那麼對於圖數據來說,怎麼去編碼?剛接觸的時候我的第一反應是,這怎麼編碼,每個節點都是獨立的,這豈不是一個均勻分布?按照這個例子:

假設有100個節點,每個節點出現的概率是1/100,那麼按照公式不是可以直接計算出來其最短平均編碼長度了(資訊熵)了嗎。。。

但是實際上是這樣的:

給定變數X,變數X的樣本空間是圖上所有節點的集合,X的概率分布為網路所有節點被隨機遊走訪問的頻率分布

這意味著,圖上的節點的概率分布不是直接通過統計的方法來計算的(如果通過這種方式計算,那麼顯然所有節點的出現概率都是1/n,n表示節點數量)節點的概率分布為網路所有節點被隨機遊走訪問的頻率分布


太難了。。。先這樣吧。。頭看炸