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

（平頂山學(xué)院計(jì)算機(jī)學(xué)院，平頂山467000）

1 引言

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

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

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

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

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

2.1 節(jié)點(diǎn)中心性指標(biāo)

節(jié)點(diǎn)的中心性評(píng)價(jià)指標(biāo)較多，下面僅對(duì)新算法需要用到的度中心性、介數(shù)中心性、接近中心性三項(xiàng)指標(biāo)展開介紹。

(1)度中心性

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

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

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

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

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

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

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

(3)接近中心性

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

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

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

2.2 基于多屬性判別的節(jié)點(diǎn)中心性計(jì)算

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

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

由于各指標(biāo)的量綱不同，為了便于比較，對(duì)上述矩陣做如下標(biāo)準(zhǔn)化處理：

標(biāo)準(zhǔn)化處理后的矩陣記為 R=（rij）n×m。

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

由上，計(jì)算第i個(gè)節(jié)點(diǎn)的綜合中心性Ci為:

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

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

基于不同社團(tuán)的中心點(diǎn)之間應(yīng)當(dāng)保持一定距離的思想，還需要對(duì)節(jié)點(diǎn)之間的相似性進(jìn)行計(jì)算，在選取綜合中心性值大的節(jié)點(diǎn)時(shí)，將相似度極高的節(jié)點(diǎn)去掉。

(1)節(jié)點(diǎn)相似性

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

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

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

(2)算法描述

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

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

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

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

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

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

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

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

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

通過ΔLC可以衡量鄰居節(jié)點(diǎn)對(duì)社團(tuán)局部模塊優(yōu)度的影響，進(jìn)而判斷該鄰居節(jié)點(diǎn)是否要?jiǎng)潥w到社團(tuán)內(nèi)部。

3.2 社團(tuán)劃分算法描述

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

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

4 實(shí)驗(yàn)驗(yàn)證

4.1 算法結(jié)果評(píng)價(jià)指標(biāo)

主要的算法結(jié)果評(píng)價(jià)指標(biāo)包括以下三種：

(1)準(zhǔn)確率（Precision，P）

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

圖2 社團(tuán)劃分算法流程圖

(2)召回率（Recall，R）

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

(3)綜合評(píng)價(jià)指標(biāo)

為防止過分割和欠分割的情況，用綜合評(píng)價(jià)指標(biāo)F來對(duì)社團(tuán)劃分進(jìn)行總體評(píng)價(jià)，表達(dá)式為:

4.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

5 結(jié)束語

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