一、模塊度的局限性

（1）判斷網絡是否具有較強的社團結構一種方法是把一個給定網絡與該網絡相應的隨機化模型做對比。通常做法是通過隨機重連方式生成許多具有相同度序列的隨機化網絡，并計算這些網絡的模塊度的均值和方差，分別記為< Q >${}_{NM}$和${\delta }_Q^{NM}$，然后計算給定網絡的最大模塊度Q${}_{max}$的統計重要性：

如果Z${}_Q$>0，就可以認為網絡具有社團結構，并且Z${}_Q$越大就表明網絡的社團結構越強。但是問題來了：一些大家公認不具有較強社團結構的網絡也會具有較大的Z${}_Q$值；大家公認具有明顯社團結構的網絡卻具有很小的Z${}_Q$值。
（2）模塊度另一個更為重要的問題是分辨率限制：它無法識別出規模充分小的社團。

二、派系過濾算法

在上篇文章介紹的算法中，一個節點只能被劃分到一個社團。然而大規模實際網絡的社團結構往往具有重疊性特征，即網絡中會存在一些”騎墻節點“，每一個騎強節點都會同時屬于多個社團。所以人們提出了一種派系過濾算法來分析具有重疊性的社團結構，并編制了相應軟件CFinder。

1、k-派系社團的定義

k-派系是網絡中包含k各節點的全耦合子圖，即這k個節點中任意兩個節點都有邊相連。如果兩個k-派系有k-1個公共節點那么就稱這兩個k-派系是相鄰的。如果一個k-派系可以通過若干個相鄰的k-派系到達另一個k-派系，就稱這倆個k-派系是彼此連通的。網絡中由所有彼此連通的k-派系構成的集合就稱為一個k-派系社團。下圖為4-派系社團。

2、尋找網絡中的派系

在派系過濾算法中，采用由大到小、迭代回歸的算法來尋找網絡中的派系。首先，從網絡中各節點的度可以判斷網絡中可能存在的最大全耦合子圖的大小。從網絡中一個節點出發，找到所有包含該節點的大小為s的派系后，刪除該節點以及與之相連的邊（以避免多次找到同一個派系）。然后，另選一個節點，重復上述步驟，直到網絡中沒有節點為止。至此，找到了網絡中大小為s的所有派系。接著，逐步減小s，每次s值減小1，再用上述方法便可尋找到網絡中所有不同大小的派系。
這里的關鍵是如何從一個節點v出發尋找包含它的所有大小為s的派系。為此，首先定義兩個集合A和B：集合A為包括節點v在內的兩兩相連的所有結點的集合。而集合B則為與集合A中各結點都相連的結點的集合。為了避免重復選到某個節點，對集合A和B中的節點都按節點序號順序排列。
尋找包含節點v的所有大小為s的派系的迭代回歸算法如下：
（1）初始集合A={v}，B={v的鄰居}；
（2）從集合B中移動一個節點到集合A，同時刪除集合B中不在與集合A中所有節點相鄰的節點；
（3）如果在集合A的大小未達到s之前，集合B已為空集，或者集合A和B為已有的一個較大的派系中的子集，則停止計算，返回上一步。否則，當集合A的大小達到s，就得到一個新的派系，記錄該派系，然后返回上一步，繼續尋找包含節點v的新的派系。

3、利用派系尋找k-派系社團

找到網絡中所有的派系以后，就可以得到這些派系的重疊矩陣。該矩陣是一個對稱方針，每一行（列）對應于一個派系，對角線上的元素表示相應派系的大小（即派系所包含的節點數目）。在派系重疊矩陣中，將對角線上小于k而非對角線上小于k-1的元素置為0，其它元素置為1，就可以得到k-派系的社團結構鄰接矩陣，各個連通部分分別代表各個k-派系的社團。

三、連邊社團檢測算法

此算法的新思路是一個社團是一組緊密相連的連邊的集合，而不是通常定義的緊密相連的節點的集合。這樣定義的好處是一條邊只能屬于一個社團。
連邊社團檢測算法的基本步驟就是把具有一定相似度的連邊合并為一個社團。此時需要給出連邊相似度的定量刻畫。假設初始時我們把網絡中的每一天邊都看作一個社團，現在要把其中的兩條邊合并為一個社團，一個自然的要求就是這兩條邊應該是連在一起的，即有一個公共節點。具有一個公共節點k的一對連邊e${}_{ik}$和e${}_{jk}$之間的相似度的合理定義就是考慮節點對i和j之間的相似度。
定義連邊對e${}_{ik}$和e${}_{jk}$之間的相似度如下：

其中n${}_{+}$(i)為節點i及其所有鄰居節點的集合。

上圖連邊的相似度為4/12=1/3。
利用連邊的相似度定義，就可以用分級聚類方法來檢測網絡社團結構。具體步驟如下：
（1）計算網絡中所有相連的連邊對即至少擁有一個共同節點的連邊對的相似度，并根據相似度的值按降序排列這些連邊對。
（2）按排列次序依次將連邊對所屬社團進行合并，將合并過程以樹圖的形式記錄下來。這里，如果一些連邊對具有相同的相似度，那么就在同一步進行合并。
（3）社團的合并過程可進行到某一步為止，至多可進行到所有的連邊都屬于一個社團。
在上述操作過程中，兩個社團融合時所對應的相似度值稱為融合社團的強度，并對應于樹圖分支的高度。
為了得到最佳的社團結構，需要確定分割樹圖的最佳位置，或者等價的，確定社團合并過程進行到哪一步是最佳的。為此，基于社團內部的連邊密度定義一個目標函數，稱為劃分密度D。假設一個包含M條連邊的網絡被劃分為C個社團{P${}_1$,P${}_2$，，P${}_c$}，其中社團P${}_c$包含m${}_c$條連邊和n${}_c$個節點，它所對應的歸一化密度定義為：

其中n${}_c$-1是使得n${}_c$個節點構成連通圖所需的最少連邊數，而n${}_c$（n${}_c$-1）/2則是n${}_c$個節點之間最大可能的連邊數。這里，如果n${}_c$=2，那么定義D${}_c$=0。整個網絡的劃分密度就定義為D${}_c$的加權和：

由于上式求和中的每一項都局限在社團內部，從而使得劃分密度避免了模塊度具有的分辨率限制問題。通過計算連邊樹圖每一層所對應的劃分密度或者直接優化劃分密度就可以得到最佳的社團劃分。

四、社團檢測算法的評價標準

1、基準圖方法

對于把社團檢測算法應用于實際網絡分析，算法的好壞取決于兩點：
（1）時間：算法能否早可接受的時間內給出社團劃分結果。
（2）性能：算法能否高質量地揭示出實際網絡的社團結構。

2、元數據方法

為了定量比較不同社團劃分算法的效果，可以引入以下幾個指標：
（1）社團質量：相似的節點應該共享盡可能多的元數據。
（2）重疊質量：對于網絡中的每個節點i，我們從元數據中提取一個標量（稱為重疊元數據），它對應于節點i所屬的真實社團的數目。
（3）社團覆蓋： 計算屬于非平凡社團(即有3個或以上節點的社團)的節點所占的比例。
（4）重疊覆蓋：計算每個節點所屬的非平凡社團的數目的平均值。兩個算法可能具有相同的社團覆蓋度，但是一個算法有可能比另一個算法提取出更多的重疊節點。對于不具有檢測重疊性的社團算法，重疊覆蓋度與社團覆蓋度是一樣的。

總結

以上是生活随笔為你收集整理的除了基于模块度之外的其它社团检测算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。