基于個體關系屬性的加權網絡社群結構探測模型

張鍇琦，杜海峰

（西安交通大學a.管理學院；b.公共管理與復雜性科學研究中心；c.公共政策與管理學院，西安 710049）

社會人際互動關系中，由相同或相似屬性個體所結成的小團體，具有小團體內部個體間關系稠密，小團體之間個體關系稀疏的特征，復雜網絡將這種現象稱為社群結構特征［1］。由于社群結構能夠有效地揭示網絡中具有共性節點的結構及特征，因而其研究與應用受到了物理學、管理學、社會學等學科的重視［1-4］。在社會網絡研究中，社群結構特征除了表現為個體屬性的相似外，還表現為個體關系的親疏。個體間關系的強弱會影響社群結構特征的分布。因而，對應到網絡模型中，這種受到個體關系強弱影響的社群結構稱為加權網絡社群結構［5］。同時，受到關系強弱的影響，位于社群邊緣的個體可能會隸屬于多個社群，在結構上表現為社群結構的重疊，使得社群結構特征更為復雜。因而，加權網絡的社群結構特征研究在實際社會網絡中具有重要的研究意義。

社群結構探測是社群結構特征研究的基礎，目前較為通用的社群結構探測方法多通過優化Newman［2］設計的模塊性指標，實現對社群結構的探測，如Newman［7］提出的快速探測算法（簡稱N算法）、Du等［8］提出的基于節點先驗知識的探測算法（簡稱PKM 算法）、Aaron等［9］提出的社群結構探測算法（簡稱A 算法）、Blondel等［10］提出的社群壓縮算法（簡稱B 算法）等。但是由于經典模塊性指標是針對0-1網絡提出的，因而上述算法不能有效地實現加權網絡的社群結構探測。由于加權網絡的社群結構探測需要將權值納入社群結構的評價體系中，故相比于0-1網絡而言，加權網絡社群結構概念中的定義元素更加多樣，而其探測問題也變得更為復雜［5-6，11］。

Girvan等［12］針對加權網絡社群結構提出了一種基于GN（Girvan-Newman）算法的社群結構探測算 法 （Weighted Girvan-Newman Algorithm，WGN）［13］，并同時給出了模塊性指標在加權網絡中的改進思路。Duch 等［14］將提出的極值優化算法（External Optimization Algorithm，EO）用于改進后的模塊性指標Qw，以實現加權網絡的社群結構探測。Jin等［15］在WGN 算法的基礎上，通過發現社群中心節點，調整非中心節點的方法改進并提出了相應的算法，使得該算法針對大型加權網絡具有良好的探測效果。Lu等［16］進一步基于計算群內中心度和群間中心度的方法，提出了相應的加權網絡社群結構探測算法。除了上述基于WGN 算法及改進指標優化的探測算法外，一些研究從其他角度重新定義了加權網絡社群結構并提出了相應的算法。Farkas等［17］在派系過濾方法的基礎上提出了加權派系過濾算法（Clique Percolation Method with Weights，CPMw），用于加權網絡社群結構的探測；而Reichardt等［18］提出的Potts模型則是從模糊社群的概念出發，對加權網絡社群結構進行探測。然而，上述方法大多只是將權值理解為節點間的多重邊，而不是節點間關系親疏的強度；同時，上述方法鮮有考慮可能存在的社群重疊現象。因而，對于加權網絡社群結構探測而言，上述方法存在改進的空間。Ahn等［19］提出了連邊社群的概念用于探測具有重疊特征的社群結構，其核心思想認為，盡管一個節點可能屬于多個社群，但每一條邊的社群含義是相對明確的。因而將對于節點的社群結構探測轉向對邊的社群結構探測。在連邊社群概念基礎上，Brian等［20］提出了一種基于概率模型的重疊社群結構探測方法（Principled Statistical Approach for Overlapping Communities，PSOC），其通過構建網絡還原模型，并對該模型進行優化來實現社群結構的探測。

受連邊社群概念與PSOC 算法設計的啟發，本文認為加權網絡社群結構的探測應以邊為探測的主體，并將邊的權值納入社群結構的探測中，通過計算邊與社群的隸屬關系來探測網絡的社群結構。相比于已有的加權網絡社群結構探測算法而言，本文通過將權值轉化為距離，用于表示節點間關系的親疏，并重新定義社群結構概念，使得加權網絡中社群內的節點間具有較短的連邊距離，社群間的節點間具有較長連邊距離；同時，本文采用PSOC算法的概率模型作為基礎模型，針對加權網絡結構特征改進原有模型，提出相應的探測算法。

1 基于節點關系屬性的加權網絡社群結構

社群結構特征所表現出的社群內部關系稠密可以解釋為社群內的節點總是通過較少的連接邊進行聯系，節點間關系親密程度較高。社會網絡觀點認為節點間距離是節點關系親疏程度的體現［21］。因而從節點間距離的定義出發，社群結構特征可以描述為社群內節點的平均路徑長度較短，而社群間節點的平均路徑長度較長。在0-1網絡下，節點間的距離表示連接兩點最短路徑上的邊的數量。在加權網絡中，由于權值本身就暗含節點間關系強弱的意義，而邊的賦權使得節點間的關系可以量化表示，故可以通過節點間的距離來描述加權網絡社群結構。如圖1所示，圖1（a）、（b）分別是2個具有相同網絡結構的0-1網絡和加權網絡；在0-1網絡結構下，節點C、A的距離d C-A=2，而節點C、B的距離d C-B=1，從距離上看，節點C、B更應屬于同一個社群；而在加權網絡結構中，雖然網絡結構未發生改變，但由于權值的存在，使得d C-A=0.5+0.5=d C-B=1；相比0-1網絡，節點C的社群隸屬關系將有更多的可能性。同時，受到引入權值的影響，圖1中出現了重疊的社群結構特征。

圖1 相同結構下0-1網絡與加權網絡節點距離比較

但是，上述通過權值反映距離，進而描述社群結構的方法并不完全符合Newman等［1］對加權網絡社群結構的定義。Newman［13］認為，不是所有的權值都應該納入社群結構的探測過程中，加權網絡社群結構中邊的權值是節點間的多重邊表示。在對應的WGN 算法中，網絡邊的居中中心性每次迭代都需要被重新計算，通過刪除居中中心性最高的邊，以實現社群結構的探測。而權值在該算法中的作用是控制邊被刪除的次數，即權值為w的某邊至多被刪除w次。圖2所示為WGN 算法對加權網絡的社群結構探測結果節點i、j之間邊的居中中心性是該網絡中最高的，因此，WGN 算法會刪除節點i、j之間的邊，將節點i、j分置于2個社群。上述結果表明，由于權值只是被視為維系節點間關系有無的條件，故WGN 算法并不能完全反映節點間邊的權值對社群結構探測結果的影響。導致上述問題的原因有兩方面：①WGN 算法機理強調整體結構，而在一定程度上忽視了邊的權值；②WGN 算法及其改進算法的探測結果均強調網絡節點在相應社群的單一歸屬，即節點i一旦被劃分到某一個社群，就不會再隸屬于其他社群。但對于加權網絡的社群結構劃分，處于社群邊緣的節點，如圖2中的節點i、j，由于兩者之間的權值較大，使得節點i、j被嚴格分割在2個社群中并不十分合理，而更合理的探測結果是節點i、j同時隸屬于2 個社群，只是隸屬程度各有差異。因此，由于節點i、j及其特殊關系的存在，導致了社群的“重疊”。

圖2 WGN 算法加權網絡社群結構探測結果

所謂重疊社群結構是指一個節點可能分屬于多個社群的社群結構特征［5］。Ahn等［19］提出連邊社群的概念認為雖然節點可能屬于多個社群，但一條邊屬于多個社群的情況并不多見。Brian等［20］基于連邊社群的概念提出了PSOC 算法，用于重疊社群結構探測。其算法核心思想是根據邊兩端節點度值的分布計算邊與社群的隸屬程度。具體地，PSOC算法認為，邊對社群Cz的隸屬度q ij（z）取決于邊兩端節點i、j屬于社群C z的期望θiz與θjz，而該期望又受到節點度值的影響。其假設θ·z總體符合泊松分布，因而如果θ·z能夠使得生成網絡G對原網絡的還原概率P獲得最大，則生成網絡能夠在還原網絡的同時，通過θ·z反映節點、邊和社群的隸屬關系，揭示網絡中存在的重疊社群結構。PSOC算法采用最大期望估計算法（Expectation-Maximization Algorithm，EM）實現對θ·z的估計，而通過爬山算法實現對估計結果的優化。

雖然PSOC算法是針對0～1網絡重疊社群結構探測問題而設計的，但本文認為其計算邊的隸屬度的過程即是在對邊進行重新賦權的過程，而最終結果是通過概率模型使每條邊對所有社群的期望加和為1。因而從設計機理而言，該算法可以應用到加權網絡之中；其次，PSOC算法通過節點的期望作為計算邊隸屬度的估計標準，而該期望正是節點通過節點間關系屬性分配度值的結果，因而該方法的計算過程符合本文所描述的基于關系屬性的加權網絡社群結構特征；此外，由于權值的存在，網絡可能出現重疊社群結構特征，故其本身符合PSOC 算法的探測對象。基于以上分析，本文以加權網絡社群結構探測為研究對象，對于PSOC 算法進行了重新設定及優化方法上的改進，使其能夠更加符合加權網絡社群結構探測的需要。

2 基于概率模型的加權網絡社群結構探測方法

根據以上對于加權網絡社群結構概念的討論以及對PSOC 算法［18］應用于加權網絡的機理分析，本文針對加權網絡社群結構構建了相應的概率模型和探測方法（Principled Statistical Approach for Communities in Weighted Network，PSCw）。具體地，設網絡G=（V，E）包含個節點和條邊；節點可被分為K個社群，設Cz表示第z個社群；用對稱鄰接矩陣A ij表示網絡節點i、j之間關系的有無，用wij表示網絡中節點i、j連邊e（i，j）的權值。設節點i屬于社群Cz的期望為θiz，表示以節點i的端點的連邊中屬于社群Cz的數量；因而對于邊e（i，j）而言，其屬于社群Cz的期望λij（z）=θizθjz。設權值w ij均勻分布于K個社群中，因而加權后最終邊e（i，j）的權值屬于社群Cz的期望為

也可解釋為邊e（i，j）中的權值對社群Cz的隸屬度。基于以上對于節點、邊與社群概率估計的構建，根據PSOC算法中的概率模型，對于網絡G的還原概率為

式中，∑zωij（z）為邊e（i，j）屬于所有社群的期望，即邊e（i，j）的權值。理論上，式（1）獲得越大，其獲得的網絡結構與原網絡越相似。在采用詹森不等式［20］進行化簡后，式（1）可簡化為

式中：qij（z）為邊e（i，j）屬于社群Cz的概率，其滿足∑z q ij（z）=1，即

事實上，式（2）中的ωij（z）和qij（z）的物理含義是同質的，其都反映了邊與社群的情況。為了進一步獲取節點與社群的隸屬關系，采用θiz代替ωij（z），即式（2）可表示為

表示以節點i為端點的若干連接邊中在社群C z中實際分布的權值；設κz=∑ik iz表示社群Cz中實際擁有的權值；則，且有

而qij（z）則可表示為

對式（4）中D值求解獲得最大，便是在獲得式（1）期望最大，即獲得網絡的最大復原。PSOC 算法中采用EM 算法的步驟來獲得期望的最大估計，具體的算法分為計算步驟和剪枝步驟，通過參數反復對期望進行估計求取最大，并不斷修正參數，實現結果的收斂；其中計算步驟通過初始的節點特征kiz計算邊屬于社群的概率qij（z），并同時計算修正后的節點特征；在剪枝步驟中，通過比較和初始容忍度之間差異判斷算法是否收斂。算法收斂后計算所得D值為最終優化解，其獲得的節點和社群的隸屬關系為最終所求社群劃分結果。但文獻［22］中分析發現，PSOC 算法中的爬山算法很容易使得算法陷入局部最優解中，并且原算法存在隱含并行性和算法多參數影響等問題。因而借鑒文獻［22］中算法，本文采用進化算法對上式模型進行優化，以實現加權網絡的社群結構探測。

具體地，用矩陣M表示節點與社群關系θiz，并初始建立g個種群

對每個種群τi（M）個體進行最大期望估計求解；以每次期望估計所得的D值作為種群進化的適應度函數；每次迭代選取D值最優的種群進入下一次迭代估計，并同時更新種群τi（M）中的θiz。延用文獻［22］中的算法，本文算法中分別引入克隆操作、交叉操作和變異操作等以保持種群的多樣性和種群之間的交互，從而更富效率地獲得社群結構的劃分結果。PSCw 算法基礎框架如表1所示。

算法中對于矩陣M的期望估計操作（18～22行）與PSOC算法中計算步驟單次迭代過程一致；克隆步驟（6～9行）、交叉操作（11～14行）、變異操作（15～17 行）與文獻［20］中的操作一致；選擇操作（25～28行）根據適應度函數D分別計算克隆種群中不同種群的適應度，將D值最優的種群進行保留進入下一次迭代過程。本文優化算法采用迭代次數作為算法的中止條件。算法最終以求得的Dmax所對應的社群劃分結果作為算法的最終社群結構探測結果。算法的單次時間復雜度為O（gme K），g為設定種群數量，m為克隆種群數量，e為網絡中存在的邊的數量，K為初始社群數量。該算法時間復雜度僅與網絡規模有關系，而并不受到網絡權值的影響，且復雜度在合理范圍內。因而該算法可以運用于規模較大且權值復雜的加權網絡之中。算法的收斂性證明與基礎進化算法類似，此處便不再贅述。

表1 PSCw算法基礎框架

3 實驗與討論

對于本文所提PSCw算法的實驗包括兩部分：①對計算機生成加權網絡的社群結構探測；②對實際加權網絡的社群結構探測。測試實驗均在Intel（R）Core（TM）2 quad CPU q8400 @2.66GHzPC 機 的Matlab7.0平臺下完成。算法參數如表2所示。

表2 PSCw算法參數設置

3.1 計算機生成加權網絡

計算機生成加權網絡選取基準加權網絡［13］為實驗測試網絡。基準加權網絡中存在n個節點和k個社群，每個社群內含有k/n個節點；每個節點平均度值為d，其中與社群內的節點連接邊數為kin，與社群外的節點連接邊數為kout；社群內連接邊的權值為win，社群間的連接權值為wout，且一般有win＞wout。在基準加權網絡基礎上，本文對計算生成加權網絡的測試包括兩部分：①限定社群內權值win的情況下，不同連接邊數kout所構成的網絡結構；②限定kout條件下，不同社群內權值win所構成的網絡結構。用于測試的網絡含有128個節點，分為4個社群，每個社群含有32個節點，除全連接網絡外每個節點平均度值為16。實驗采用NMI指標［23］作為社群結構探測效果的評價指標，其計算式為

NMI指數越接近1，探測社群結構與實際社群結構越相似，反之差異越大。

對于第1 類網絡結構，在限定社群內權值win的情況下，kout的改變意味著網絡拓撲結構的改變。對于這類網絡的實驗旨在算法在加權網絡情況下，針對不同網絡結構其對于社群結構的探測效果。圖3為win的均值等于5，wout的均值等于3的情況下，PSCw 算法對于不同kout的網絡結構的探測效果。為了消除網絡結構的隨機性，對于每個kout分別生成10個獨立網絡，對每個獨立網絡進行10次獨立運算，以下測試方法與之相同。

圖3 win均值為5時，不同kout網絡探測NMI結果

從社群結構探測結果來看，當kout＜5時，網絡的社群結構相對較為清晰；此時NMI值始終等于1，說明算法的社群探測結果與原網絡劃分的社群結構一致。隨著kout值的不斷變大，節點與社群內外的連接邊逐漸一致，在這種情況下，拓撲結構上社群結構已經逐漸模糊，網絡權值則成為判斷社群結構的主要標準。從結果來看，當kout≥5時，PSCw 也能獲得較為滿意的結果。但由于權值win與wout的差異并不明顯，從權值上一些邊也很難區分其社群歸屬，因而PSCw 算法的探測結果存在一定誤差。圖4為win的均值等于10，wout的均值等于5的情況下，PSCw 算法對于不同kout的網絡結構的探測效果。從結果來看，由于權值的差異加大，社群結構的探測效果要優于圖3中的結果。

圖4 win均值為10時，不同kout網絡探測NMI結果

對于第2類網絡結構，在限定kout的情況下，不同的權值win所對應的社群結構特征也不相同。當win=wout=1 時，網絡等同于0-1 網絡結構；而win＞wout時，網絡中的社群結構便會受到權值的影響而不同，尤其是在kout≥kin時，拓撲結構上的社群結構特征變得逐漸模糊，權值對于社群結構的影響便尤為重要。圖5是限定kout=8的條件下，wout均值等于2，win均值由2～10時，PSCw 算法所得的社群結構探測效果。

圖5 kout=8時，不同win網絡探測NMI結果

從結果來看，在win均值等于2時，社群內外的權值基本保持一致，無論從拓撲結構上還是從網絡權值上，網絡社群結構特征均不明顯，因而，此時PSCw 算法的探測結果也相對較差。而隨著win均值的不斷增大，即使網絡拓撲結構上的社群結構特征不明顯，但從權值上也能逐漸地區分出社群結構，因而PSCw 算法的探測效果不斷提高。當win均值等于10時，通過網絡權值已經能夠較好地區分出社群內和社群外的連接邊，因而PSCw 算法也獲得了較好的結果。從實驗結果來看，PSCw 算法能夠在社群內外權值區分較明顯，而拓撲結構不明顯的情況下，探測出加權網絡的社群結構特征。

綜合以上兩種生成網絡的實驗結果而言，PSCw 算法既能夠在拓撲結構固定的情況下，較好地探測出不同權值的網絡社群結構，也能在權值固定的情況下，較好地探測出不同拓撲結構的網絡社群結構。因而從計算機生成網絡的結果來看，PSCw 可以適用于加權網絡的社群結構探測。

3.2 實際加權網絡

為了進一步驗證PSCw 算法的探測效果，本文對PSCw 算法在實際加權網絡的社群結構探測進行了實驗。實驗基于西安交通大學人口與發展研究所于2005年深圳市農村流動人口調查的整體網絡數據進行。本文選取了調查數據中CZ公司的整體網絡作為實驗數據。其包含了該公司農民工流動人口實際支持、情感支持和社會交往支持等3個社會支持網絡，以及婚姻討論、生育及子女教育討論、避孕討論和養老討論等4個社會討論網絡。但是由于此次調查僅針對支持或討論關系的有無，因而每個網絡都是一個0-1網絡，因此，本文在實驗過程中對這些網絡進行了疊加處理。這種處理除了使測試網絡成為加權網絡外，還具有一定的社會學意義，其表示了一種復合性的社會支持網絡或社會討論網絡，這種由多個網絡構成的網絡結構能夠更全面地反映被調查者的支持或討論關系，因而其社群結構也能夠更真實地揭示被調查者的實際社群關系。因此，本文測試的數據包含三部分，其分別為疊加社會支持網絡、疊加社會討論網絡以及將社會支持和社會討論相疊加的社會網絡（簡稱復合社會網絡），相應的網絡屬性如表3所示。

表3 測試實際網絡屬性

由于PSCw 算法需要預先設定網絡中的社群數量，故本文采用N 算法［5］對其進行預探測獲得社群數量。結果表明，該公司的7個網絡中平均包含5.8個社群，其中，社會支持網絡平均包含5.3個社群，社會討論網絡平均包含6.2個社群。因而在采用PSCw 算法進行探測時，依照向下取整的原則分別設定社會支持網絡K=5，社會討論網絡K=6，復合社會網絡K=5。圖6（a）～（c）分別表示疊加社會支持網絡、疊加社會討論網絡以及復合社會網絡的探測結果。

從結果來看，PSCw 算法能夠較好地區分網絡中存在的社群結構，并且該劃分也較好地體現了網絡中的權值對于社群結構的影響。如圖6（b）中，節點64、110由于權值的影響，其雖然在結構上應附屬于另一個節點90所在社群，但PSCw 算法仍將其判斷為一個獨立的社群。同時，PSCw 算法可以識別網絡中位于社群重疊部分的節點。圖7表示3組測試網絡中位于社群重疊部分的部分節點與社群的隸屬程度。

圖6 PSCw 算法對實際網絡探測結果

圖7中節點至少與2個社群擁有較高的隸屬度關系，因而這些節點位于社群結構的重疊部分。在社會網絡分析過程中，這類節點大多位于社群的邊緣結構或結構洞位置，能夠有效控制網絡資源，具有一定的社會學意義。而準確的隸屬度值則能夠在一定程度上解釋這種結構形成的原因，進而可以對網絡進行更深層次的分析。

總體而言，PSCw 算法能夠較好地應用于實際網絡的社群結構探測，同時，由于PSCw 算法能夠準確地計算網絡中節點對社群的隸屬度，也為社群結構特征在實際研究中的應用拓寬了領域。但需要說明的是，由于PSCw 算法在探測過程中無法對算法的社群數量進行有效收斂，故圖6（a）、（c）中節 點52、72、118、135 形 成 社 群 與 節 點120被劃歸為一個社群，這可能在一定程度上影響了社群結構探測效果，因而需要在進一步的研究工作中予以克服。

圖7 3組測試網絡部分節點與社群隸屬關系

4 結語

本文基于節點間關系的親疏對加權網絡社群結構進行了重新定義，加權網絡的社群結構不僅表現為節點連接邊的稠密，而且應表現為節點關系的緊密，同時，權值會使得社群結構出現重疊的特征。受到連邊社群概念的啟發，本文在PSOC 算法基礎上改進并提出了針對加權網絡社群結構的探測模型及優化算法——PSCw 算法，將網絡結構與權值納入到一個統一的模型中進行計算。通過在計算機生成網絡的實驗發現，PSCw 算法能夠在不同網絡拓撲結構和不同權值分布的情況下對加權網絡中的社群結構進行有效探測；在對實際加權網絡的探測過程中，PSCw 算法也能給出符合原網絡實際的社群結構劃分，并且獲得了節點隸屬于社群的信息，為相關社會問題的定量化研究提供了方法支持。通過研究發現，在加權網絡社群結構探測過程中，節點與社群隸屬關系的量化能夠更好地反映網絡真實情況和深層內涵，尤其是針對具有現實意義的社會網絡結構。因此，在進一步的研究中需要探求節點與社群隸屬程度的現實社會學意義。然而，受到PSOC 算法概率模型原始假定的限制，PSCw 算法仍然是一種分類算法，在社群結構未知的情況下，該算法不能對社群數量進行較好的收斂。因此，在未來的研究過程中需要進一步完善。