天天看點

基于子產品度的社團檢測算法

一、CNM算法

該算法是基于貪婪算法思想的社團結構檢測算法,該算法的計算複雜度為O(nlog 2 ^2 2n),算法代碼可以從網上搜到。CNM算法采用堆資料結構計算和更新子產品度,具體描述如下:

(1)初始化:初始時假設每個節點就是一個獨立的社團,子產品度值Q=0,初始的e i j _{ij} ij​、a i _i i​計算如下:

基于子產品度的社團檢測算法

初始的子產品增量矩陣的元素計算如下:

基于子產品度的社團檢測算法

得到初始的子產品度增量矩陣後,就可以得到由它每一行的最大元素構成的最大堆H。

(2)從最大堆中選擇最大的 Δ \Delta ΔQ i j _{ij} ij​,合并相應的社團i和j,标記合并後的社團的标号為j,并更新子產品度增量矩陣 Δ \Delta ΔQ i j _{ij} ij​,最大堆H和輔助向量a i _i i​。

Δ \Delta ΔQ i j _{ij} ij​的更新:删除第i行和第i列的元素,更新第j行和第j列的元素,得到:

基于子產品度的社團檢測算法

最大堆H的更新:更新最大堆中相應的行和列的最大元素。

輔助向量a i _i i​的更新:a j , _j^, j,​=a i _i i​+a j _j j​,a i , _i^, i,​=0。記錄合并以後的Q=Q+ Δ \Delta ΔQ i j _{ij} ij​。

(3)重複步驟(2)直到網絡中所有節點都歸到一個社團内。

當子產品度增量矩陣中最大的元素由正變負時就可以停止合并,并認為此時的結果就是網絡的社團結構。

二、階層化社團檢測

大規模實際網絡中的節點往往具有不同層次的組織結構,大社團内部可能含有較小規模的社團,較小規模社團内部可能又包含更小規模的一些社團,如下圖所示:

基于子產品度的社團檢測算法

基于子產品度的概念人們提出了一種能夠用于權重網絡的階層化社團結構的凝聚算法,簡稱BGLL算法,算法分為兩個階段:

(1)初始時假設每個節點都是一個獨立的社團。對任意相鄰的節點i和節點j,計算将節點i加入其鄰居節點j所在的社團(記為社團C)時對應的子產品度增量 Δ \Delta ΔQ:

基于子產品度的社團檢測算法

其中s i , i n _{i,in} i,in​是節點i與社團C内其它節點所有連邊的權重和。

計算節點i與所有鄰居節點的子產品度增量,然後選出其中最大的一個。當該值為正時,把節點i加入相應的鄰居節點所在的社團,否則,節點i留在原社團中。這種社團合并過程重複進行,直到不在出現合并現象,這樣就劃分出了第一層社團。

(2)構造一個新網絡,其中的節點是前一階段劃分出的社團,節點之間的連邊權重是兩個社團之間所有連邊的權重和。然後再利用(1)中的方法對新網絡進行社團劃分,得到第二層社團結構,以此類推,直到不能劃分出更高一層的社團結構為止。

三、多片網絡社團檢測

1、定義

子產品度的概念可以推廣同于随時間演化的動态網絡、具有多種連接配接形式的多元網絡以及具有不同尺度社團結構的過尺度網絡。一種統一的處理辦法就是把這些網絡表示為如下圖所示的多片網絡。其中,同一片上的節點之間的連接配接用實線表示,位于不同片的同一個節點之間用虛線連接配接。

基于子產品度的社團檢測算法

根據片與片的關系,可以把多篇網絡分為兩類:

(1)各片之間有先後次序關系的多片網絡,典型例子包括随時間演化的組織内部成員之間的關系網絡。

(2)各片之間并無先後次序關系的多片網絡。典型例子包括一群個體之間基于不同的關系類型定義而得到的不同的關系網絡。

2、多片權重網絡的子產品度公式

第p片上節點i與節點j之間的連接配接權重記為w i j p _{ijp} ijp​,第p片網絡上的節點i與第q片網絡上的節點i之間的連接配接的權重記為c i p q _{ipq} ipq​。定義第p片上的節點i的三種強度如下:

片上強度:

基于子產品度的社團檢測算法

片間強度:

基于子產品度的社團檢測算法

總強度:

基于子產品度的社團檢測算法

第p片上所有節點的強度之和記為W ρ _\rho ρ​= ∑ i \sum_i ∑i​s i p _{ip} ip​,所有片上所有節點的總強度之和記為:

基于子產品度的社團檢測算法

由上可得,多片權重網絡的子產品度公式如下:

基于子產品度的社團檢測算法

其中 λ p \lambda_p λp​是用來控制各片網絡内社團劃分規模和數量的分辨率系數。理論上說,方括号中的第二項也可以添加一個表示片間耦合的分辨路參數因子,但是這個參數可以包含到片間節點的連邊權重c i p q _{ipq} ipq​的取值中,通常取值為0(沒有連接配接)或者取為 ω \omega ω>0。

四、空間網絡社團檢測

為了更有效的研究空間網絡的社團結構,我們再看以下子產品度的原始定義:

基于子產品度的社團檢測算法

其中p i j _{ij} ij​是零模型中節點i和節點j之間連邊數的期望值,并且對于通常選取的保持度序列不變的配置模型有:

基于子產品度的社團檢測算法

為了考慮空間的影響,可以把上式修改為:

基于子產品度的社團檢測算法

其中N i _i i​是度量節點i的重要性,d i j _{ij} ij​是節點i和節點j之間的實體距離。由于相隔一定距離的節點之間的總的權值應保持不變,即有

基于子產品度的社團檢測算法

是以,障礙函數具有如下形式:

基于子產品度的社團檢測算法

繼續閱讀