社群劃分的標準–模組度

在社群發現演算法中,幾乎不可能先確定社群的數目,於是,必須有一種度量的方法,可以在計算的過程中衡量每一個結果是不是相對最佳的結果。

模組度(Modularity)用來衡量一個社群的劃分是不是相對比較好的結果。一個相對好的結果在社群內部的節點相似度較高,而在社群外部節點的相似度較低。

全域性模組度 

設Avw為網路的鄰接矩陣的一個元素,定義為:

假設cv和cw分別表示點v和點w所在的兩個社群,社群內部的邊數和網路中總邊數的比例:

 

函式δ(cv,cw)的取值定義為:如果v和w在一個社群,即cv=cw,則為 1,否則為 0。m 為網路中邊的總數。 

模組度的大小定義為社群內部的總邊數和網路中總邊數的比例減去一個期望值,該期望值是將網路設定為隨機網路時同樣的社群分配所形成的社群內部的總邊數和網路中總邊數的比例的大小,於是模組度Q為:

 

其中kv表示點v的度。

 

設eij表示社群i和社群j內部邊數目的和與總邊數的比例,ai表示社群i內部的點所關聯的所有的邊的數目與總邊數的比例。

    

為了簡化Q的計算,假設網路已經劃分成n個社群,這個時候就有一個 n維矩陣,Q 的計算可以變成:

 

在進行每次劃分的時候計算Q值,Q取值最大的時候則是此網路較理想的劃分。Q值的範圍在0-1之間,Q值越大說明網路劃分的社群結構準確度越高,在實際的網路分析中,Q值的最高點一般出現在0.3-0.7之間。

區域性模組度 

有時候,可能不知道全網路的資料,可以用區域性社群的區域性模組度的方式來檢查社群的合理性。假設有一個已經檢測出來的社群,社群的節點的集合為V,這些節點所有的鄰接節點而加入到集合當中來,形成新的集合V*。定義V*的鄰接矩陣為:

於是,和全域性模組度相似的是,可以用節點集V*全部屬於節點集V中的元素所佔的比例的大小來衡量一個社群的好壞:

其中,δ(i,j)表示的是如果i,j都是V中則值為1,否則為0。m*表示的是鄰接矩陣內邊的數目。

區域性模組度比全域性模組度要快的多,因為區域性模組度的計算只需要用到區域性的網路資訊,只需要在剛剛開始的時候掃描一下整個網路。對於中小規模的網路可能區域性模組度的效果要低於全域性模組度,但是而且對於中等或者大規模的社會網路來說,區域性模組度的效果可能還要好一些。

參考資料:

Finding community structure in very large networks