基于節(jié)點(diǎn)聚類(lèi)系數(shù)的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)

朱 玲，余本國(guó)，冀慶斌

(1.中北大學(xué) 理學(xué)院，山西 太原 030051；2.海南醫(yī)學(xué)院 醫(yī)學(xué)信息學(xué)院，海南 ?？?570216；3.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006)

0 引 言

近年來(lái)，網(wǎng)絡(luò)在很多專(zhuān)業(yè)領(lǐng)域已經(jīng)被廣泛應(yīng)用，網(wǎng)絡(luò)拓?fù)淇梢杂脕?lái)描述自然界中的多種網(wǎng)絡(luò)系統(tǒng)，例如社交網(wǎng)絡(luò)、計(jì)算機(jī)科學(xué)網(wǎng)絡(luò)、電力通信網(wǎng)絡(luò)等.社區(qū)結(jié)構(gòu)是網(wǎng)絡(luò)的一個(gè)基本特征.網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)性質(zhì)是指網(wǎng)絡(luò)中存在著一些聚集程度較高且被稱(chēng)為“社區(qū)”的模塊[1-2].尋找網(wǎng)絡(luò)中社區(qū)的技術(shù)稱(chēng)為社區(qū)檢測(cè)或社區(qū)發(fā)現(xiàn)，指僅使用網(wǎng)絡(luò)拓?fù)渲芯幋a的信息來(lái)識(shí)別社區(qū)[3-4].現(xiàn)實(shí)網(wǎng)絡(luò)中的社區(qū)可能是重疊或非重疊的[5-6]，本文重點(diǎn)關(guān)注非重疊社區(qū)檢測(cè).非重疊社區(qū)檢測(cè)的結(jié)果稱(chēng)為劃分或社區(qū)劃分[5]，指的是將網(wǎng)絡(luò)的所有節(jié)點(diǎn)劃成k≥2個(gè)互不相交的節(jié)點(diǎn)組.

1 相關(guān)工作

1.1 社區(qū)檢測(cè)算法

學(xué)者們?cè)谘芯烤W(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的同時(shí)還提出了很多有關(guān)社區(qū)檢測(cè)的算法.2002年，Girvan和Vewman提出了GN算法[1]；2004年，Radicchi等在GN算法的基礎(chǔ)上提出了邊聚類(lèi)系數(shù)算法[7]；2007年，Raghavan等運(yùn)用了標(biāo)簽傳播算法[8]；2004年，Newman提出了Newman快速算法[9]；Newman在提出模塊度概念的同時(shí)給出了一種基于模塊度矩陣的譜算法[2]，2008年，這種譜算法被Leicht和Newman應(yīng)用到有向網(wǎng)絡(luò)中[10]；2010年，Guo等[11]用共鄰矩陣與增益函數(shù)作為網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的目標(biāo)函數(shù)，進(jìn)一步推導(dǎo)出基于增益矩陣、增量矩陣這兩種矩陣的特征值以及特征向量的社區(qū)檢測(cè)劃分算法.2014年，Ma等[12]通過(guò)判斷兩個(gè)節(jié)點(diǎn)與其共享鄰居節(jié)點(diǎn)能否構(gòu)成三角形來(lái)判斷這兩個(gè)節(jié)點(diǎn)是否屬于同一社區(qū)，并提出了一種基于三角形的重疊社區(qū)檢測(cè)劃分算法.

在聚類(lèi)分析處理算法中譜聚類(lèi)是一種新型劃分算法[13].傳統(tǒng)譜劃分算法通?；谕剐螛颖?，一旦出現(xiàn)樣本不為凸形的特殊情況，劃分算法就會(huì)陷入一個(gè)局部最優(yōu).譜聚類(lèi)算法與傳統(tǒng)譜劃分算法相比有一個(gè)優(yōu)點(diǎn)，即它可以在任意樣本空間上劃分，并且劃分結(jié)果能收斂于全局最優(yōu)[14].除此之外，譜聚類(lèi)劃分算法還具有嚴(yán)格的邏輯推理劃分過(guò)程，目前已發(fā)展成為多種不同領(lǐng)域的研究熱點(diǎn).

1.2 譜方法

譜方法最早是由圖劃分算法引出的.目前，人們?cè)谟?jì)算機(jī)中的圖劃分領(lǐng)域已經(jīng)做了深入研究.網(wǎng)絡(luò)中的圖劃分是指將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分成組，最后使各組之間的連接邊數(shù)達(dá)到最小.其中，由Fiedler提出且由Pothon等人推廣的譜劃分，通過(guò)Laplacian矩陣的特征值以及特征向量完成圖劃分的方法使用最廣泛.

Laplacian矩陣是由圖劃分問(wèn)題引出的，定義為L(zhǎng)=D-A，其中A是鄰接矩陣，D是度矩陣，也是一個(gè)對(duì)角矩陣，對(duì)角線元素Dii表示第i個(gè)節(jié)點(diǎn)的度.Laplacian矩陣有一個(gè)基本特點(diǎn)是圖的塊數(shù)與0特征值的個(gè)數(shù)相同.當(dāng)圖為連通圖時(shí)，其Laplacian矩陣有一個(gè)0特征值，與其對(duì)應(yīng)一個(gè)元素都為1的特征向量，該Laplacian矩陣的特征值是非負(fù)的.假設(shè)λ1<λ2<…<λn，對(duì)于一個(gè)連通圖，λ2是該Laplacian矩陣最接近0的特征值，此時(shí)，對(duì)應(yīng)的特征向量稱(chēng)為Fiedler向量.基于Laplacian矩陣的社區(qū)二分劃分算法就是計(jì)算該Laplacian矩陣特征值對(duì)應(yīng)的特征向量，并且尋找一個(gè)和它最接近的索引向量來(lái)對(duì)節(jié)點(diǎn)進(jìn)行劃分，將索引所對(duì)應(yīng)的特征向量中的非負(fù)元素劃分到一個(gè)社區(qū)，負(fù)元素劃分到另一個(gè)社區(qū).

1.3 識(shí)別社區(qū)間邊的CCE規(guī)則

在網(wǎng)絡(luò)G中，給定社區(qū)劃分P和一條社區(qū)間邊e(i,j)，di>2，dj>2，節(jié)點(diǎn)i,j所屬的社區(qū)分別是C(i)，C(j)，通過(guò)聚類(lèi)系數(shù)的變化識(shí)別邊界社區(qū)劃分的社區(qū)間邊[15].下面給出識(shí)別社區(qū)間邊的一種判定準(zhǔn)則.

(1)

若CCE(e)ij=1，則e(i,j)是社區(qū)間邊.

2 相似度矩陣的構(gòu)造與社區(qū)劃分

2.1 相似度矩陣的構(gòu)造

相似度矩陣的構(gòu)造是決定譜聚類(lèi)算法聚類(lèi)性能最關(guān)鍵的一步[16].網(wǎng)絡(luò)中的社區(qū)是由連接松散的邊界分隔開(kāi)的子圖，社區(qū)檢測(cè)劃分方法的核心是尋找社區(qū)邊界[2].由文獻(xiàn)[15]知，網(wǎng)絡(luò)中社區(qū)的邊界也是一個(gè)子圖.使用上述CCE規(guī)則可以刻畫(huà)邊界子圖中節(jié)點(diǎn)間的相似性，因此可以構(gòu)造一個(gè)相似圖進(jìn)行社區(qū)劃分.在該相似圖中利用CCE規(guī)則引出相似度矩陣并找出社區(qū)邊界，本文中將相似度矩陣稱(chēng)為網(wǎng)絡(luò)密度矩陣，記為C.則有

(2)

對(duì)于網(wǎng)絡(luò)密度矩陣中的每一個(gè)元素cij，若cij=1，說(shuō)明節(jié)點(diǎn)i,j之間相似且互為鄰居節(jié)點(diǎn)，此時(shí)，e(i,j)構(gòu)成社區(qū)間邊，否則，e(i,j)構(gòu)成社區(qū)內(nèi)邊.

2.2 圖分割和Laplacian矩陣

在一個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)中，先定義一個(gè)網(wǎng)絡(luò)密度矩陣C，即式(2).圖劃分是將較相似的節(jié)點(diǎn)劃分成一組，使各組之間的連邊數(shù)目達(dá)到最小，將連接兩組之間的邊定義為H，其中節(jié)點(diǎn)i,j在不同的組中，如式(3)所示.

(3)

定義一個(gè)包含n個(gè)元素的索引向量si，表示為

(4)

可得

(5)

當(dāng)節(jié)點(diǎn)在同一組時(shí)，δij=0；不在同一組時(shí)，δij=1.此時(shí)，H可表示為

(6)

(7)

在式(6)中，

(8)

此時(shí)，H可以寫(xiě)為

(9)

將式(9)改寫(xiě)成矩陣形式為

(10)

(11)

式中：βi是L的特征值；ui是特征值βi所對(duì)應(yīng)的特征向量，使連接各組之間的邊數(shù)H達(dá)到最小.L的特征值由小到大的排列為β1≤β2≤β3≤…≤βn，最小化H的值即選擇適合的ai的值，將最小化H的任務(wù)賦予第二小特征值β2對(duì)應(yīng)的特征向量u2，即Fiedler向量.由于si=±1，因此，si不能與特征向量ui做平行選擇，通過(guò)選擇si與ui盡可能平行，最終可以獲得一個(gè)近似解

(12)

2.3 算法流程

Input：網(wǎng)絡(luò)G(V,E)

Output:網(wǎng)絡(luò)社區(qū)劃分的最終結(jié)果

Step 1 利用式(2)，得到網(wǎng)絡(luò)G(V,E)的一個(gè)網(wǎng)絡(luò)密度矩陣C；

Step 2 計(jì)算網(wǎng)絡(luò)G(V,E)的度矩陣D，D是一個(gè)對(duì)角矩陣，對(duì)角線元素Dii為第i個(gè)節(jié)點(diǎn)的外部度；

Step 3 計(jì)算Laplacian矩陣L=D-C；

Step 6 用不同的形狀標(biāo)記已知分組情況的社區(qū)1和社區(qū)2；

Step 7 出圖；

Step 8 算法結(jié)束.

2.4 算法分析

本文研究了網(wǎng)絡(luò)中節(jié)點(diǎn)聚類(lèi)系數(shù)與社區(qū)結(jié)構(gòu)之間的關(guān)系，并且提出了使用局部度量節(jié)點(diǎn)聚類(lèi)系數(shù)對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)結(jié)構(gòu)檢測(cè)的劃分算法.對(duì)于一些大型網(wǎng)絡(luò)，采用局部度量節(jié)點(diǎn)聚類(lèi)系數(shù)將網(wǎng)絡(luò)進(jìn)行有效劃分.下面分析本文算法的時(shí)間復(fù)雜度.計(jì)算一個(gè)聚類(lèi)系數(shù)的時(shí)間為O(d2)，執(zhí)行一次CCE度量需要計(jì)算4個(gè)聚類(lèi)系數(shù)，每執(zhí)行一次CCE度量可以識(shí)別一條社區(qū)間邊.假設(shè)有m條社區(qū)間邊，則計(jì)算網(wǎng)絡(luò)密度矩陣的時(shí)間復(fù)雜度為O(4d2m);計(jì)算度矩陣D和Laplacian矩陣的時(shí)間復(fù)雜度為O(n)，n為矩陣維數(shù).Lanczos[17]算法可以計(jì)算出第二小特征值對(duì)應(yīng)的特征向量，時(shí)間復(fù)雜度是O(n).因此，整個(gè)算法的時(shí)間復(fù)雜度是O(4d2m+2n)，由此可看出，網(wǎng)絡(luò)中社區(qū)間邊數(shù)越少，算法的時(shí)間復(fù)雜度越小.

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

評(píng)價(jià)一個(gè)算法優(yōu)良的標(biāo)準(zhǔn)之一是對(duì)其劃分結(jié)果進(jìn)行綜合分析.一般情況下，不能概括性地評(píng)價(jià)一個(gè)算法優(yōu)于另外一個(gè)算法，因?yàn)橥ǔＲ粋€(gè)好的算法往往只在某些方面具有優(yōu)勢(shì).針對(duì)一些模塊結(jié)構(gòu)已知的網(wǎng)絡(luò)圖，將能否把模塊結(jié)構(gòu)正確劃分出來(lái)作為最終目標(biāo)，并且與其他實(shí)驗(yàn)的劃分結(jié)果相比得出最終結(jié)論；針對(duì)模塊結(jié)構(gòu)未知的圖，通過(guò)與傳統(tǒng)譜劃分算法的劃分結(jié)果相比較，以驗(yàn)證本文提出的基于Laplacian矩陣的譜算法在劃分社區(qū)網(wǎng)絡(luò)中的有效性.真實(shí)網(wǎng)絡(luò)的基本信息如表1 所示.

表1 真實(shí)網(wǎng)絡(luò)的基本信息Tab.1 The basic data of the real network information

3.1 Karate網(wǎng)絡(luò)實(shí)驗(yàn)

Karate網(wǎng)絡(luò)是社會(huì)網(wǎng)絡(luò)分析領(lǐng)域的經(jīng)典數(shù)據(jù)集之一.20世紀(jì)70年代，Zachary[18]對(duì)美國(guó)一所大學(xué)的空手道俱樂(lè)部進(jìn)行了兩年左右的研究，最終發(fā)現(xiàn)俱樂(lè)部中的34名成員彼此之間存在社會(huì)關(guān)系.由于該俱樂(lè)部的現(xiàn)任校長(zhǎng)和主管之間有了沖突，因此，該俱樂(lè)部被劃分成相對(duì)較小的兩部分，這兩部分分別將俱樂(lè)部現(xiàn)任校長(zhǎng)以及主管作為核心.該網(wǎng)絡(luò)中有34個(gè)節(jié)點(diǎn)和78條邊，每?jī)蓚€(gè)節(jié)點(diǎn)之間存在一條邊表示對(duì)應(yīng)的兩個(gè)成員之間是聯(lián)系頻繁的朋友關(guān)系.根據(jù)該網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，如圖1 所示為使用本文方法劃分的最終結(jié)果，該俱樂(lè)部成員的真實(shí)劃分情況分別用長(zhǎng)方形和菱形表示.由圖1 可知，本文算法比Newman的GN算法[9]得到的結(jié)果更準(zhǔn)確.

圖1 Karate網(wǎng)絡(luò)社團(tuán)劃分Fig.1 Community division of Karate network

為了更直觀地分析實(shí)驗(yàn)劃分結(jié)果，做了以下數(shù)據(jù)處理.如圖2 所示，以0值為界反映了此俱樂(lè)部成員的劃分情況.其中橫坐標(biāo)表示節(jié)點(diǎn)標(biāo)號(hào)，縱坐標(biāo)表示與第二小特征值β2=0.468 5相對(duì)應(yīng)的特征向量中元素的取值結(jié)果.顯然，0值以上有18個(gè)數(shù)據(jù)，0值以下有16個(gè)數(shù)據(jù)，因此，使用本文提出的網(wǎng)絡(luò)社區(qū)劃分算法得到的劃分結(jié)果與實(shí)際劃分情況相符.

圖2 Karate網(wǎng)絡(luò)社團(tuán)劃分特征向量中元素的取值分布Fig.2 Value distribution of feature vector elements for community division of Karate network

3.2 Dolphin網(wǎng)絡(luò)

Dolphin網(wǎng)絡(luò)也是網(wǎng)絡(luò)社區(qū)劃分的一個(gè)經(jīng)典數(shù)據(jù)集.Lusseau等對(duì)新西蘭海灣中62只海豚種群的生活習(xí)性進(jìn)行了實(shí)地考察.通過(guò)研究發(fā)現(xiàn)，當(dāng)其中一只海豚離開(kāi)后，該海豚種群就會(huì)被劃分成兩個(gè)相對(duì)較小的種群，由此他們構(gòu)造了一個(gè)包含62個(gè)節(jié)點(diǎn)和159條邊的社會(huì)網(wǎng)絡(luò).如果出現(xiàn)某兩只海豚經(jīng)常一起頻繁活動(dòng)的情況，那么網(wǎng)絡(luò)中對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)之間就會(huì)存在一條邊.如圖3 所示為使用本文方法進(jìn)行劃分的最終結(jié)果，形狀的區(qū)分表示網(wǎng)絡(luò)的真實(shí)劃分情況.由圖3 可知，實(shí)驗(yàn)劃分結(jié)果沒(méi)有把標(biāo)號(hào)是29，31，40的節(jié)點(diǎn)準(zhǔn)確地劃分到所屬社區(qū)中，但與網(wǎng)絡(luò)的真實(shí)劃分結(jié)果相接近.因此，實(shí)驗(yàn)結(jié)果表明使用本文算法與文獻(xiàn)[19]中使用模塊度矩陣的譜算法得到的劃分結(jié)果都相對(duì)準(zhǔn)確，由此說(shuō)明了本文所述算法的合理性.

圖3 Dolphin網(wǎng)絡(luò)社區(qū)劃分Fig.3 Community division of Dolphin network

同上述實(shí)驗(yàn)，做以下數(shù)據(jù)處理.如圖4 所示，橫坐標(biāo)表示節(jié)點(diǎn)標(biāo)號(hào)，縱坐標(biāo)表示與第二小特征值β2=0.173 0所對(duì)應(yīng)的特征向量中元素的取值結(jié)果.以0值為界反映了Dolphin網(wǎng)絡(luò)的劃分情況.很明顯，圖中0值以上數(shù)據(jù)有41個(gè)，0值以下數(shù)據(jù)有21個(gè).由此可見(jiàn)，使用本文算法可以將該網(wǎng)絡(luò)劃分成兩個(gè)明顯的社區(qū).

圖4 Dolphin網(wǎng)絡(luò)社團(tuán)劃分特征向量中元素的取值分布Fig.4 Value distribution of feature vector elements for community division of Dolphin network

3.3 Blogs網(wǎng)絡(luò)

Blogs網(wǎng)絡(luò)包含1 222個(gè)節(jié)點(diǎn)和16 714條邊.圖5 所示為傳統(tǒng)譜劃分算法劃分網(wǎng)絡(luò)的節(jié)點(diǎn)分布圖，以0值為界展示了Blogs網(wǎng)絡(luò)的節(jié)點(diǎn)分組情況，其中，橫坐標(biāo)表示節(jié)點(diǎn)標(biāo)號(hào)，縱坐標(biāo)表示與第二小特征值β2=0.117 6相對(duì)應(yīng)的特征向量中元素的取值情況.可以看出，有1 200個(gè)數(shù)據(jù)幾乎分布在0值上，顯然沒(méi)有將0值兩端的數(shù)據(jù)很好地區(qū)分開(kāi)，因此，傳統(tǒng)譜劃分算法對(duì)Blogs網(wǎng)絡(luò)的劃分結(jié)果不能令人滿(mǎn)意.

圖5 傳統(tǒng)譜劃分算法節(jié)點(diǎn)分布圖Fig.5 Node distribution of traditional spectral classification algorithm

圖6 所示為用本文所述的基于Laplacian矩陣的譜算法對(duì)Blogs網(wǎng)絡(luò)進(jìn)行劃分的節(jié)點(diǎn)分布圖.對(duì)比圖5，圖6 中0值左右的數(shù)據(jù)能被明顯地區(qū)分開(kāi)，其中有453個(gè)數(shù)據(jù)分布在0值以上，624個(gè)數(shù)據(jù)分布在0值以下，145個(gè)數(shù)據(jù)分布在0值附近.與傳統(tǒng)譜劃分算法劃分網(wǎng)絡(luò)的結(jié)果相比，本文方法可以把Blogs網(wǎng)絡(luò)劃分成兩個(gè)相對(duì)明顯的社區(qū).

圖6 Laplacian矩陣節(jié)點(diǎn)分布圖Fig.6 Node distribution of Laplacian matrix

4 結(jié) 論

本文研究了從微觀角度定義的節(jié)點(diǎn)聚類(lèi)系數(shù)與網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)之間的關(guān)系，并且提出了使用局部度量節(jié)點(diǎn)聚類(lèi)系數(shù)對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)結(jié)構(gòu)檢測(cè)的高效劃分算法.通過(guò)在3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)中的測(cè)試，驗(yàn)證了本文算法不僅能夠?qū)⒛K結(jié)構(gòu)正確無(wú)誤地劃分出來(lái)，還能提高劃分算法的時(shí)間效率.然而，對(duì)于一些存在大量星型模塊結(jié)構(gòu)的網(wǎng)絡(luò)，多數(shù)節(jié)點(diǎn)的聚類(lèi)系數(shù)為零，此時(shí)，CCE規(guī)則不適用，本文提出的算法很難在此類(lèi)型網(wǎng)絡(luò)中發(fā)現(xiàn)有意義的社區(qū)結(jié)構(gòu).此外，隨著科技的發(fā)展，人類(lèi)研究的網(wǎng)絡(luò)規(guī)模也越來(lái)越大，到目前為止，在大規(guī)模的網(wǎng)絡(luò)上進(jìn)行社區(qū)結(jié)構(gòu)檢測(cè)仍是一個(gè)難題，如何將局部社區(qū)發(fā)現(xiàn)進(jìn)一步應(yīng)用于大規(guī)模網(wǎng)絡(luò)局部結(jié)構(gòu)分析等實(shí)際問(wèn)題將是下一步研究工作的重點(diǎn).