社群發現演算法中模組化度量值Q(Modularity)的計算

NO IMAGE

 社群發現演算法中模組化度量值Q(Modularity)的計算

Modularity Measure(模組化度量值),由Newman等人提出,是目前常用的一種衡量網路中社群穩定度的方法。

 

 

 

 

如上圖所示的圖中,我們將這個圖以圖中兩根橫線為方式進行劃分,共得三個社群(community),其中紅色,綠色以及藍色的點各為一個社群,這裡我們採用的計算公式為:Q=∑(I/E-((2I O)/2E)2)

在上式中I表示兩個端點均在同一社群中的邊的數目,O表示其中一個端點在社群中,而另一個端點不在社群中的邊的數目,將3個社群中的Q值計算出來以後相加,就得到我們需要的值。如圖所示,上圖中對藍色和綠色兩個點運用上公式後,可得Q值0.165,紅色點所在的社群Q值為0.16,將三者相加可得總的Q值為0.49,為所求,這也是所有的劃分方法中所能得到的最大的Q值。