基于中心節(jié)點和局部優(yōu)化的復雜網(wǎng)絡(luò)社團劃分方法*

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

1 引言

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

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

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

2 基于多屬性判別和相似性的社團中心節(jié)點發(fā)現(xiàn)算法

Reihaneh等人首次提出了基于中心節(jié)點的社團定義，即將社團看作由一個領(lǐng)導者和聚集在其周圍的跟隨者組成，其中領(lǐng)導者就是社團的中心節(jié)點[10]。因此，在復雜網(wǎng)絡(luò)的社團劃分中，首先要做的就是尋找網(wǎng)絡(luò)的中心節(jié)點，然后再根據(jù)中心節(jié)點選取適當?shù)姆椒ㄟM行社團挖掘。

2.1 節(jié)點中心性指標

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

(1)度中心性

度中心性（degree centrality，DC）是描述無標度網(wǎng)絡(luò)結(jié)構(gòu)的基本參數(shù)[11]。為了適應不同規(guī)模的網(wǎng)絡(luò)，這里進行歸一化處理，定義度中心性為節(jié)點實際關(guān)聯(lián)的邊數(shù)與可能關(guān)聯(lián)的最大邊數(shù)之比。節(jié)點v的度中心性DCv表達式為：

其中，n為網(wǎng)絡(luò)中節(jié)點的個數(shù)，d(v)是節(jié)點v的度，指其實際所關(guān)聯(lián)的邊的數(shù)目。

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

(2)介數(shù)中心性

介數(shù)中心性（betweenness centrality，BC）用途經(jīng)節(jié)點的任意節(jié)點對間最短路徑的多少來衡量該節(jié)點在網(wǎng)絡(luò)中的地位。節(jié)點v的介數(shù)中心性BCv表達式為：

其中，V為網(wǎng)絡(luò)中節(jié)點的集合，gxy(v)表示節(jié)點x和y之間途經(jīng)節(jié)點v的最短路徑的條數(shù)，gxy為節(jié)點x和y之間最短路徑的總數(shù)。

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

(3)接近中心性

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

其中，n為網(wǎng)絡(luò)中節(jié)點的個數(shù)，d(v ,u)表示節(jié)點v到u的距離，即兩節(jié)點之間最短路中邊的數(shù)量。

一個節(jié)點到網(wǎng)絡(luò)中其它節(jié)點的距離越短，節(jié)點的接近中心性的值就越大，表明節(jié)點居于網(wǎng)絡(luò)中心位置的可能性越大。

2.2 基于多屬性判別的節(jié)點中心性計算

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

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

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

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

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

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

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

2.3 社團中心節(jié)點發(fā)現(xiàn)算法

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

(1)節(jié)點相似性

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

其中，Nu表示節(jié)點u的鄰居節(jié)點集（且包含u點自身）表示節(jié)點u和v的共有鄰居節(jié)點的數(shù)目表示節(jié)點u和v包含自身在內(nèi)的所有鄰居節(jié)點的數(shù)目。

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

(2)算法描述

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

圖1 復雜網(wǎng)絡(luò)中心節(jié)點發(fā)現(xiàn)算法流程圖

3 基于局部優(yōu)化的社團劃分方法

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

3.1 局部模塊優(yōu)度

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

其中，Ein是社團內(nèi)部邊的數(shù)目，內(nèi)部邊指邊的兩個頂點都在社團中；Eout是社團外部邊的數(shù)目，外部邊指的則是邊的一個頂點在社團內(nèi)部，另一個頂點在社團外部。

加入鄰居節(jié)點后的社團局部模塊優(yōu)度LC'的表達式為：

加入鄰居節(jié)點后，社團的局部模塊優(yōu)度增量ΔLC的表達式為：

通過ΔLC可以衡量鄰居節(jié)點對社團局部模塊優(yōu)度的影響，進而判斷該鄰居節(jié)點是否要劃歸到社團內(nèi)部。

3.2 社團劃分算法描述

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

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

4 實驗驗證

4.1 算法結(jié)果評價指標

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

(1)準確率（Precision，P）

準確率為劃分結(jié)果中正確節(jié)點數(shù)量與劃分結(jié)果中總節(jié)點數(shù)量之比，表達式為：

圖2 社團劃分算法流程圖

(2)召回率（Recall，R）

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

(3)綜合評價指標

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

4.2 實驗結(jié)果

為了驗證算法的準確性，分別以空手道俱樂部成員關(guān)系網(wǎng)絡(luò)數(shù)據(jù)集Zachary[13]和海豚網(wǎng)絡(luò)數(shù)據(jù)集Dolphin[14]為例進行了測試。經(jīng)驗證，中心節(jié)點相似度閾值和局部模塊優(yōu)度增量閾值分別為0.3和0.33時，最符合真實的網(wǎng)絡(luò)社團結(jié)構(gòu)。

算法對Zachary的測試結(jié)果如圖3所示，其中，網(wǎng)絡(luò)被分成了兩個社團。

圖3 Zachary社團結(jié)構(gòu)圖

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

表1 算法對比數(shù)據(jù)表

5 結(jié)束語

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