張鍇琦，杜海峰

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

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

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

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

受連邊社群概念與PSOC 算法設(shè)計的啟發(fā)，本文認為加權(quán)網(wǎng)絡(luò)社群結(jié)構(gòu)的探測應(yīng)以邊為探測的主體，并將邊的權(quán)值納入社群結(jié)構(gòu)的探測中，通過計算邊與社群的隸屬關(guān)系來探測網(wǎng)絡(luò)的社群結(jié)構(gòu)。相比于已有的加權(quán)網(wǎng)絡(luò)社群結(jié)構(gòu)探測算法而言，本文通過將權(quán)值轉(zhuǎn)化為距離，用于表示節(jié)點間關(guān)系的親疏，并重新定義社群結(jié)構(gòu)概念，使得加權(quán)網(wǎng)絡(luò)中社群內(nèi)的節(jié)點間具有較短的連邊距離，社群間的節(jié)點間具有較長連邊距離；同時，本文采用PSOC算法的概率模型作為基礎(chǔ)模型，針對加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)特征改進原有模型，提出相應(yīng)的探測算法。

1 基于節(jié)點關(guān)系屬性的加權(quán)網(wǎng)絡(luò)社群結(jié)構(gòu)

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

圖1 相同結(jié)構(gòu)下0-1網(wǎng)絡(luò)與加權(quán)網(wǎng)絡(luò)節(jié)點距離比較

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

圖2 WGN 算法加權(quán)網(wǎng)絡(luò)社群結(jié)構(gòu)探測結(jié)果

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

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

2 基于概率模型的加權(quán)網(wǎng)絡(luò)社群結(jié)構(gòu)探測方法

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

也可解釋為邊e（i，j）中的權(quán)值對社群Cz的隸屬度。基于以上對于節(jié)點、邊與社群概率估計的構(gòu)建，根據(jù)PSOC算法中的概率模型，對于網(wǎng)絡(luò)G的還原概率為

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

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

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

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

而qij（z）則可表示為

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

具體地，用矩陣M表示節(jié)點與社群關(guān)系θiz，并初始建立g個種群

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

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

表1 PSCw算法基礎(chǔ)框架

3 實驗與討論

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

表2 PSCw算法參數(shù)設(shè)置

3.1 計算機生成加權(quán)網(wǎng)絡(luò)

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

NMI指數(shù)越接近1，探測社群結(jié)構(gòu)與實際社群結(jié)構(gòu)越相似，反之差異越大。

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

圖3 win均值為5時，不同kout網(wǎng)絡(luò)探測NMI結(jié)果

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

圖4 win均值為10時，不同kout網(wǎng)絡(luò)探測NMI結(jié)果

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

圖5 kout=8時，不同win網(wǎng)絡(luò)探測NMI結(jié)果

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

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

3.2 實際加權(quán)網(wǎng)絡(luò)

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

表3 測試實際網(wǎng)絡(luò)屬性

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

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

圖6 PSCw 算法對實際網(wǎng)絡(luò)探測結(jié)果

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

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

圖7 3組測試網(wǎng)絡(luò)部分節(jié)點與社群隸屬關(guān)系

4 結(jié)語

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