基于中心節點和局部優化的復雜網絡社團劃分方法*

（平頂山學院計算機學院，平頂山467000）

1 引言

自然界與現實世界中的許多系統都可以用由節點和邊組成的網絡抽象地來表示，如社會關系網、流行病傳播網、蛋白質交互網、Internet網絡等，這些網絡因其具有高復雜性被稱為“復雜網絡”。復雜網絡通常具有小世界效應和無標度特性這兩個統計特性。其中，“小世界效應”是指復雜網絡具有短路徑長度和高聚類系數的特點[1]；“無標度特性”則是指復雜網絡中的結點的度服從冪率分布特征[2]。“社團結構”是復雜網絡的一種重要結構特性，指的是社團中的點相互連接緊密，而這些點同社團外的點連接較為松散[3]。社團的發現和劃分對于分析網絡的組織結構、功能劃分和成員關系等有著重要的理論意義和實際價值。

近年來，隨著社團結構研究不斷深入，社團挖掘算法被主要分為全局社團挖掘算法和局部社團挖掘算法。全局社團挖掘算法基于全網信息進行分析，如譜聚類算法[4]、GN 算法[5]、快速 Newman 算法[6]，但目前復雜網絡的規模愈來愈大、動態性愈來愈強，導致算法的普適性、復雜度和效率等有待改進。局部社團挖掘算法基于網絡的局部信息進行挖掘，如Clauset等提出的基于局部模塊度R（R是社團內部總邊數與社團內外邊數之和的比值）的算法，它是通過最大化局部模塊度增量來進行局部社團搜索[7]；Luo等提出的另一種評價局部模塊度的指標M（M是社團內部總邊數與社團外部節點和邊界節點連邊數之比）的算法[8]，其中，局部社團的規模、初始節點的位置等均會影響到社團最終的劃分結果。評價社團劃分算法的優劣，一個通常的做法是對每個劃分給出一個度量，較合理的劃分有較高的度量，優化該度量以得到最優或次優的社團結構。第一個 (也是目前最有效的)度量是“模塊優度”（modularity），是由 Newman 在 2004 年提出的[9]，其值越大說明社團結構越明顯，在實際網絡中，該值通常位于0.3～0.7之間。

本文結合復雜網絡社團結構的相關研究，提出了一種基于中心節點和局部優化的復雜網絡社團劃分方法。該算法首先通過多個節點中心性指標對復雜網絡中節點的中心性進行綜合判斷，找出網絡的中心節點集，接著使用局部優化思想基于每個中心節點進行社團擴張，從而形成多個社團，然后再對一些特殊節點進行處理，最終實現整個復雜網絡的社團劃分。

2 基于多屬性判別和相似性的社團中心節點發現算法

Reihaneh等人首次提出了基于中心節點的社團定義，即將社團看作由一個領導者和聚集在其周圍的跟隨者組成，其中領導者就是社團的中心節點[10]。因此，在復雜網絡的社團劃分中，首先要做的就是尋找網絡的中心節點，然后再根據中心節點選取適當的方法進行社團挖掘。

2.1 節點中心性指標

節點的中心性評價指標較多，下面僅對新算法需要用到的度中心性、介數中心性、接近中心性三項指標展開介紹。

(1)度中心性

度中心性（degree centrality，DC）是描述無標度網絡結構的基本參數[11]。為了適應不同規模的網絡，這里進行歸一化處理，定義度中心性為節點實際關聯的邊數與可能關聯的最大邊數之比。節點v的度中心性DCv表達式為：

其中，n為網絡中節點的個數，d(v)是節點v的度，指其實際所關聯的邊的數目。

度中心性表明了節點在網絡中的直接影響力，其值越大，節點屬于局部中心點(即社團中心點)的可能性越大。

(2)介數中心性

介數中心性（betweenness centrality，BC）用途經節點的任意節點對間最短路徑的多少來衡量該節點在網絡中的地位。節點v的介數中心性BCv表達式為：

其中，V為網絡中節點的集合，gxy(v)表示節點x和y之間途經節點v的最短路徑的條數，gxy為節點x和y之間最短路徑的總數。

若一個節點是網絡中其他節點對之間通信的必經之路，則其在網絡中必有重要地位，因此，節點的BC值越大，說明在網絡傳輸信息、物質或能量時，其負載越重，可以被認為是網絡的中心節點之一[11]。

(3)接近中心性

接近中心性（closeness centrality，CC）用節點到網絡中其它節點的距離來衡量該節點是否處于中心地位。節點v的接近中心性CCv表達式為：

其中，n為網絡中節點的個數，d(v ,u)表示節點v到u的距離，即兩節點之間最短路中邊的數量。

一個節點到網絡中其它節點的距離越短，節點的接近中心性的值就越大，表明節點居于網絡中心位置的可能性越大。

2.2 基于多屬性判別的節點中心性計算

由上述節點中心性指標的定義可以看出，不同的指標從不同的角度描述了節點在復雜網絡中的中心程度。由于只利用單一中心性指標來計算節點在網絡中的中心性可能存在偏差，故此提出一種基于多屬性判別的節點中心性計算方法。該方法將網絡中的每一個節點作為一個方案，將節點的多個中心性指標作為方案的屬性，則節點的中心性計算就轉化為一個多屬性判別問題[12]。

設網絡中有n個節點，則對應的方案集合可以表示為P={P1,P2,…,Pn}，若節點的中心性指標有m個，則對應的方案屬性集合I={I1,I2,…,In},第i個節點的第j個指標的值記為Pi=(Ij)（i=1,2,…,n;j=1,2,…,m。下同），構成判別矩陣：

由于各指標的量綱不同，為了便于比較，對上述矩陣做如下標準化處理：

標準化處理后的矩陣記為 R=（rij）n×m。

設第j個指標的權重為ωj（j=1,2,…,m；則加權標準化判別矩陣為：

由上，計算第i個節點的綜合中心性Ci為:

采用度中心性DC、介數中心性BC、接近中心性CC這三個指標對節點的中心性進行綜合判斷，各指標的權重按照文獻[12]中使用的層次分析法進行計算，得到 ωDC=0.5493，ωBC=0.2616，ωCC=0.1891。

2.3 社團中心節點發現算法

基于不同社團的中心點之間應當保持一定距離的思想，還需要對節點之間的相似性進行計算，在選取綜合中心性值大的節點時，將相似度極高的節點去掉。

(1)節點相似性

節點相似性用兩個節點的共有鄰居節點的數目來描述節點間的緊密程度，節點u和v的相似性Suv的表達式為:

其中，Nu表示節點u的鄰居節點集（且包含u點自身）表示節點u和v的共有鄰居節點的數目表示節點u和v包含自身在內的所有鄰居節點的數目。

一般情況下，兩個節點的相似度越高，即Suv值越大，則這兩個節點屬于同一個社團的概率就越大。

(2)算法描述

至此，給出基于多屬性判別和相似性的社團中心節點發現算法，首先根據綜合中心性值選取候選中心節點，然后計算候選節點之間的相似度，相似度大的話，就將相似的兩個節點中綜合中心性值較小的那個節點刪掉。算法流程如圖1所示。

圖1 復雜網絡中心節點發現算法流程圖

3 基于局部優化的社團劃分方法

社團往往是指一個內部連接緊密、外部連接松散的子圖。在確定了網絡的中心節點集后，對每個中心節點利用局部優化的思想，不斷地將鄰近節點歸入社團以實現社團規模的擴大，從而形成多個局部社團。下面先給出局部模塊優度的定義，然后對基于局部優化的社團劃分算法展開描述。

3.1 局部模塊優度

用社團的局部模塊優度LC來衡量一個社團劃分的優劣，其表達式為:

其中，Ein是社團內部邊的數目，內部邊指邊的兩個頂點都在社團中；Eout是社團外部邊的數目，外部邊指的則是邊的一個頂點在社團內部，另一個頂點在社團外部。

加入鄰居節點后的社團局部模塊優度LC'的表達式為：

加入鄰居節點后，社團的局部模塊優度增量ΔLC的表達式為：

通過ΔLC可以衡量鄰居節點對社團局部模塊優度的影響，進而判斷該鄰居節點是否要劃歸到社團內部。

3.2 社團劃分算法描述

基于局部優化的社團劃分算法，是逐個計算加入鄰居節點后的局部模塊優度增量ΔLC，將增量大于設定閾值的鄰居節點加入候選節點集，然后從候選節點集中選擇與社團具有最多共同鄰居節點的節點來更新社團，直到沒有大于設定的增量閾值的節點出現。以一個中心節點為例挖掘以該節點為中心節點的社團，算法流程如圖2所示。

在對所有的中心節點執行完局部社團挖掘后，需要對一些特殊節點進行處理。一類是未被劃分至任何社團的節點，另一類是被劃分至多個社團的節點，這些節點最終均將被劃分至與其有最多鄰居節點的社團。

4 實驗驗證

4.1 算法結果評價指標

主要的算法結果評價指標包括以下三種：

(1)準確率（Precision，P）

準確率為劃分結果中正確節點數量與劃分結果中總節點數量之比，表達式為：

圖2 社團劃分算法流程圖

(2)召回率（Recall，R）

召回率為劃分結果中正確節點數量與真實社團中總節點數量之比，表達式為:

(3)綜合評價指標

為防止過分割和欠分割的情況，用綜合評價指標F來對社團劃分進行總體評價，表達式為:

4.2 實驗結果

為了驗證算法的準確性，分別以空手道俱樂部成員關系網絡數據集Zachary[13]和海豚網絡數據集Dolphin[14]為例進行了測試。經驗證，中心節點相似度閾值和局部模塊優度增量閾值分別為0.3和0.33時，最符合真實的網絡社團結構。

算法對Zachary的測試結果如圖3所示，其中，網絡被分成了兩個社團。

圖3 Zachary社團結構圖

實驗中，針對上述定義的準確率、召回率、綜合評價這三個算法評價指標，將此算法與引言中介紹的R算法及M算法進行了對比。對比結果如表1所示，從中可以看出，在Zachary數據集的測試結果中，此算法明顯優于其它算法，在Dolphin數據集的測試結果中，除了準確率低于R算法，其它指標均優于所對比的算法。

表1 算法對比數據表

5 結束語

對復雜網絡中節點的度中心性、介數中心性、接近中心性、相似度、局部模塊優度等指標做了歸納、整理并適當加以擴展。分別應用基于多屬性判別和相似性的社團中心節點發現算法和基于局部優化的社團劃分方法對Zachary和Dolphin數據集進行了測試，同時與R算法和M算法進行了對比，結果表明新算法具有較好的社團劃分能力，可以有效地挖掘出社團結構。在此基礎上，進一步降低算法的時間復雜度和解決大規模真實網絡應用中的優化問題，將是下一步的研究重點。