吳衛(wèi)江，周　靜，李國和

(中國石油大學(xué)(北京) 地球物理與信息工程學(xué)院，北京 102200)

?

一種基于節(jié)點重要度的社團(tuán)劃分算法

吳衛(wèi)江，周靜*，李國和

(中國石油大學(xué)(北京) 地球物理與信息工程學(xué)院，北京 102200)

摘要指出了通過挖掘復(fù)雜網(wǎng)絡(luò)中存在的社團(tuán)結(jié)構(gòu)，可以分析整個復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和功能，還可以發(fā)現(xiàn)網(wǎng)絡(luò)中隱藏的規(guī)律.為了得到最佳社團(tuán)劃分結(jié)構(gòu)，定義了網(wǎng)絡(luò)的節(jié)點重要度矩陣和聚類矩陣，結(jié)合圖的特征譜平分法和模塊度函數(shù)，提出了一種基于節(jié)點重要度的社團(tuán)劃分算法(CDNIM).通過在空手道俱樂部、海豚關(guān)系網(wǎng)絡(luò)等多個經(jīng)典數(shù)據(jù)集上應(yīng)用，結(jié)果表明：該算法能夠有效提高發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)的準(zhǔn)確率.

關(guān)鍵詞復(fù)雜網(wǎng)絡(luò)； 社團(tuán)結(jié)構(gòu)； 譜平分； 聚類算法； 模塊度

Community Partition Algorithm Based on Node Importance

WuWeijiang,ZhouJing,LiGuohe

(China University of Petroleum-Beijing,College of Geophysics and Information Engineering,Beijing 102200,China)

AbstractThis paper points out that through mining the society existed in complex networks, the topological structure and function of complex networks can be analyzed, and the hidden rules can be found either. In order to get the optimal community structure, node importance matrix and clustering matrix are defined, combined the spectral bisection method based on graph and modularity function, an community partition algorithm (CDNIM) based on node importance is proposed. This algorithm is applied in karate club, dolphin networks, and other classical data sets, the result of experiment shows that this algorithm can effectively improve the accuracy of discovering community structure.

Keywordscomplex networks；society structure；spectral bisection method；clustering algorithm；modularity

在現(xiàn)實世界中，存在著各式各樣的網(wǎng)絡(luò)，如科技網(wǎng)、社會網(wǎng)絡(luò)、生物網(wǎng)等,它們都可以抽象成復(fù)雜網(wǎng)絡(luò).小世界[1]和無標(biāo)度[2]特性是研究復(fù)雜網(wǎng)絡(luò)理論的開創(chuàng)性標(biāo)志，隨著人們對復(fù)雜網(wǎng)絡(luò)的研究不斷深入，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的另外一個特性，即社團(tuán)結(jié)構(gòu)[3]特性.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)表征為：存在于單個社團(tuán)內(nèi)部的各個節(jié)點之間的邊較多，分布比較有地域密集性，而社團(tuán)之間相互連接的邊比較少.這種社團(tuán)結(jié)構(gòu)暗示著同一社團(tuán)內(nèi)的節(jié)點具有相同的屬性或者是有其他相似的方面.對復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，可以更好地了解現(xiàn)實網(wǎng)絡(luò)中的內(nèi)部組織結(jié)構(gòu)：依據(jù)復(fù)雜網(wǎng)絡(luò)中劃分的各個社團(tuán)的功能，可以推測出整個網(wǎng)絡(luò)的實際功能；研究網(wǎng)絡(luò)中某些節(jié)點的功能，可以推測在與該節(jié)點同一社團(tuán)內(nèi)其他節(jié)點的功能；研究網(wǎng)絡(luò)中劃分的各個社團(tuán)之間的聯(lián)系，可以清晰地認(rèn)知網(wǎng)絡(luò)的整體布局.因此，能夠有效地挖掘出復(fù)雜網(wǎng)絡(luò)中存在的社團(tuán)結(jié)構(gòu)，對于現(xiàn)實網(wǎng)絡(luò)的研究具有非常重要的意義.

本研究根據(jù)譜平分法的啟發(fā)，定義了網(wǎng)絡(luò)的節(jié)點重要度矩陣，結(jié)合聚類分析算法，提出了基于節(jié)點重要度的社團(tuán)劃分算法(CDNIM)，用來探測網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).將該算法在經(jīng)典的數(shù)據(jù)集上—空手道俱樂部網(wǎng)絡(luò)、海豚關(guān)系網(wǎng)、足球隊網(wǎng)絡(luò)等進(jìn)行了驗證，全部得到了正確的社團(tuán)劃分結(jié)果.圍繞劃分社團(tuán)的準(zhǔn)確率，進(jìn)一步實驗，比較了CDNIM與其他經(jīng)典的社團(tuán)發(fā)現(xiàn)算法，得出CDNIM算法挖掘復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)準(zhǔn)確率較高.

1相關(guān)定義

在一個無向無權(quán)網(wǎng)絡(luò)G=中，節(jié)點集為V，邊集為E，節(jié)點集V中一對點即對應(yīng)邊集E中的一條邊.

定義1：設(shè)節(jié)點集V={e1,e2,…,en}，令(ei,ej)表示節(jié)點ei∈V與節(jié)點ej∈V之間的邊，邊集E?{(ei,ej):ei,ej∈V}，那么節(jié)點ei的度Di就表示ei的鄰居節(jié)點的數(shù)目，即與該節(jié)點連接的其他節(jié)點的數(shù)目，Di表達(dá)式為：

Di=|{(ei,ej):ei,ej∈V;(ei,ej)∈E}|.

(1)

(2)

其中，wij為網(wǎng)絡(luò)的鄰接矩陣中所對應(yīng)的元素,wij取值為0或1.wij=1，表示網(wǎng)絡(luò)中的節(jié)點i和節(jié)點j直接相連；wij=0，表示網(wǎng)絡(luò)中的節(jié)點i和節(jié)點j沒有直接相連.矩陣中對角線上的元素全部置為1，它表示網(wǎng)絡(luò)中每個節(jié)點對于自身的重要度貢獻(xiàn)比值為1.根據(jù)定義2，網(wǎng)絡(luò)的節(jié)點重要度矩陣H是網(wǎng)絡(luò)鄰接矩陣的映射.當(dāng)i≠j時，wij映射成wijDj/2；當(dāng)i=j時，wij=1.

定義3：為了對網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，將社團(tuán)劃分的問題轉(zhuǎn)化成對網(wǎng)絡(luò)中各個節(jié)點進(jìn)行k聚類問題.根據(jù)譜平分方法的啟示，實際上是計算網(wǎng)絡(luò)節(jié)點重要度矩陣H的特征值和特征向量.將節(jié)點重要度矩陣H進(jìn)行行標(biāo)準(zhǔn)化，求其特征值之后將其排序，從中挑選k-1個特征值對應(yīng)的特征向量((e1,e2,…,ek-1)，其中ei∈Rn,i=1,2,…,k-1)組合成聚類矩陣E.矩陣E的行向量作為n個數(shù)據(jù)向量形式的待聚類數(shù)據(jù).

利用網(wǎng)絡(luò)的Laplace[5]矩陣進(jìn)行社團(tuán)劃分是譜平分法[6]的理論基礎(chǔ).網(wǎng)絡(luò)G的Laplace矩陣L是一個是對稱的矩陣，假設(shè)矩陣L的n特征向量為0=λ1<λ2<，…,λn，其對應(yīng)的特征向量為v1

2CDNIM算法

2.1CDNIM算法概述

本文算法定義了節(jié)點重要度矩陣H和聚類矩陣E，結(jié)合圖的譜平分法思想，提出了一種基于節(jié)點重要度的社團(tuán)劃分算法(CDNIM).算法CDNIM具體描述如下.

對于一個給定的網(wǎng)絡(luò)G=，給定一個聚類數(shù)目k，基于k-means聚類的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)探測算法基本步驟如下：

輸入：具有n個節(jié)點的復(fù)雜網(wǎng)絡(luò)G=，需要劃分的社團(tuán)個數(shù)為k；

輸出：網(wǎng)絡(luò)的社團(tuán)集合S；

(1)計算網(wǎng)絡(luò)的節(jié)點重要度矩陣Hi=wijDi/2；

(2)將節(jié)點重要度矩陣H進(jìn)行行標(biāo)準(zhǔn)化即H1=norw(H)后，求矩陣H1的特征值D和特征向量V；

(3)將特征值排序，選取k-1個特征值所對應(yīng)的特征向量組成聚類矩陣E；

(4)將聚類矩陣E的行向量作為n個數(shù)據(jù)向量形式的待聚類數(shù)據(jù)，調(diào)用k-means算法將節(jié)點進(jìn)行聚類.根據(jù)聚類得到的劃分結(jié)果，計算出此時相對應(yīng)的模塊度值Q；

(5)根據(jù)以上步驟，可以得到k-1個Q值，社團(tuán)的最佳社團(tuán)結(jié)構(gòu)即對應(yīng)最大的Q值.

2.2網(wǎng)絡(luò)社團(tuán)數(shù)目k值確定

聚類分析中的k-means算法的k值需要根據(jù)經(jīng)驗得到，本文提出的CDNIM算法輸入也包含復(fù)雜網(wǎng)絡(luò)中的社團(tuán)個數(shù)k，這里k值需要根據(jù)模塊度Q值確定.對于一個復(fù)雜網(wǎng)絡(luò)，我們事先并不知道該網(wǎng)絡(luò)中到底存在多少個社團(tuán)，更不知道該網(wǎng)絡(luò)應(yīng)該被劃分成多少個社團(tuán)才是符合現(xiàn)實情況的.本文算法中的k值可以通過Newman和Girvan提出的模塊度函數(shù)Q[9]確定，函數(shù)Q作為網(wǎng)絡(luò)劃分的一個衡量標(biāo)準(zhǔn).

綜上，網(wǎng)絡(luò)的社團(tuán)劃分結(jié)構(gòu)決定了模塊度的大小，即網(wǎng)絡(luò)劃分的社團(tuán)結(jié)構(gòu)強(qiáng)度越強(qiáng)，劃分質(zhì)量越好時模塊度Q值越大.當(dāng)CDNIM算法運行結(jié)束時，不同的社團(tuán)劃分個數(shù)對應(yīng)不同的模塊度Q值，Q值最大時對應(yīng)的網(wǎng)絡(luò)社團(tuán)劃分方案就是最佳的社團(tuán)劃分結(jié)果，即最佳的k值.

3算法驗證及分析

在5個真實數(shù)據(jù)集上進(jìn)行實驗，驗證CDNIM算法的合理性和有效性.實驗環(huán)境為因特爾酷睿雙核P7350處理器，內(nèi)存2GB，32位Windows 7操作系統(tǒng)，主要編程語言為Java語言以及Matlab編程工具.

3.1實驗數(shù)據(jù)集

(1)Zachary空手道俱樂部.Zachary空手道俱樂部成員關(guān)系網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)、社團(tuán)發(fā)現(xiàn)技術(shù)等領(lǐng)域的典型測試網(wǎng)絡(luò)數(shù)據(jù)集，數(shù)據(jù)集中的各個節(jié)點代表俱樂部中的成員，網(wǎng)絡(luò)中的邊代表成員之間的聯(lián)系[10].網(wǎng)絡(luò)中的人物關(guān)系因為某種原因分裂成了2個小社團(tuán).

(2)海豚關(guān)系網(wǎng)絡(luò).另外一個檢測網(wǎng)絡(luò)社團(tuán)劃分算法的經(jīng)典數(shù)據(jù)集是海豚關(guān)系網(wǎng)絡(luò)(Dolphins)[10]，該網(wǎng)絡(luò)的數(shù)據(jù)由D．Lusseau 等人提供.網(wǎng)絡(luò)中的62的節(jié)點代表海豚，159條邊代表海豚之間有頻繁的往來關(guān)系.海豚關(guān)系網(wǎng)初始分裂為2個社團(tuán).

(3)信息熵網(wǎng)絡(luò).信息熵網(wǎng)絡(luò)來自于Martin Rosvall等人的研究，用于研究采用信源和信宿之間的互信息熵最大時所得的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法是否準(zhǔn)確.

(4)Strike數(shù)據(jù)集.Strike數(shù)據(jù)集描述的是一家鋸木廠中不同種族員工之間溝通情況的數(shù)據(jù)集.該鋸木廠的團(tuán)隊領(lǐng)導(dǎo)根據(jù)員工之間的溝通頻率將網(wǎng)絡(luò)分為3個社團(tuán).

(5)足球隊網(wǎng)絡(luò).足球隊網(wǎng)絡(luò)中，有115個節(jié)點，613條邊，節(jié)點對應(yīng)足球隊，邊表示足球隊之間的賽事.這些足球隊被分在了12個小組里，每個小組有8～12支球隊，在同一小組內(nèi)的球隊之間比賽次數(shù)較多.

3.2驗證社團(tuán)個數(shù)k值實驗結(jié)果

表1　CDNIM算法應(yīng)用在不同的數(shù)據(jù)集上得到的社團(tuán)劃分個數(shù)

3.3CDNIM算法劃分足球隊網(wǎng)絡(luò)實驗結(jié)果

足球隊網(wǎng)絡(luò)中包含12個小組，具體分布見表2.應(yīng)用本文算法劃分足球隊網(wǎng)絡(luò)，網(wǎng)絡(luò)被劃分成k個社團(tuán)時所對應(yīng)的模塊度值如圖1所示.

圖1　足球隊網(wǎng)絡(luò)被劃分成k個社團(tuán)時所對應(yīng)的模塊度值Fig.1　Themodularity of that network football is divided intok communities

當(dāng)網(wǎng)絡(luò)被劃分成12個社團(tuán)時(即k=12)，模塊度達(dá)到了最大值，符合實際情況.利用CDNIM算法劃分足球隊網(wǎng)絡(luò)的社團(tuán)結(jié)果如表3，總共有8個節(jié)點(29,43,59,60,64,91,93,98)劃分錯誤，劃分社團(tuán)的準(zhǔn)確率為93.04%.

表2　足球隊網(wǎng)絡(luò)原始數(shù)據(jù)

表3　CDNIM算法在足球隊網(wǎng)絡(luò)上的社團(tuán)劃分結(jié)果

3.4多種社團(tuán)劃分算法實驗結(jié)果

分別利用經(jīng)典的社團(tuán)發(fā)現(xiàn)算法(GN算法[12]、K-L算法[13]、Newman快速算法[14])以及CDNIM算法對數(shù)據(jù)集進(jìn)行社團(tuán)劃分，社團(tuán)劃分結(jié)果的準(zhǔn)確率如圖2所示.

3.5實驗結(jié)果分析

從圖2中的數(shù)據(jù)看出，CDNIM社團(tuán)發(fā)現(xiàn)算法劃分社團(tuán)的正確率較高.CDNIM算法通過節(jié)點重要度矩陣來表示網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，在一定程度上，節(jié)點重要度矩陣比網(wǎng)絡(luò)的鄰接矩陣更能體現(xiàn)節(jié)點間的相互關(guān)系.網(wǎng)絡(luò)中的節(jié)點度值越大，那么它對鄰居節(jié)點的重要度貢獻(xiàn)比值就越大.當(dāng)網(wǎng)絡(luò)中節(jié)點之間有相互連

接時，該節(jié)點的度值發(fā)生變化，其負(fù)載和重要度也會變化，通過與鄰居節(jié)點之間的傳遞，形成了重要度貢獻(xiàn)關(guān)系的拓?fù)浣Y(jié)構(gòu).這種網(wǎng)絡(luò)結(jié)構(gòu)表示作為劃分網(wǎng)絡(luò)社團(tuán)的基準(zhǔn)數(shù)據(jù)，能夠得到更好的劃分結(jié)果，準(zhǔn)確率更高.

圖2　不同的算法在5個數(shù)據(jù)集上的劃分結(jié)果的準(zhǔn)確率Fig.2　The accuracy of different algorithms on five data sets of the partition result

4結(jié)束語

本文借鑒了譜平分法的思想，將節(jié)點重要度矩陣與k-means算法相結(jié)合，提出了一種新的社團(tuán)劃分算法，然后利用一個聚類度量函數(shù)—模塊度函數(shù)來查找出網(wǎng)絡(luò)中最佳社團(tuán)的數(shù)目，得到網(wǎng)絡(luò)的最佳社團(tuán)劃分結(jié)果.CDNIM社團(tuán)發(fā)現(xiàn)算法在多個經(jīng)典的數(shù)據(jù)集上得到了正確的驗證，證明了該算法在復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)中的有效性和正確性；通過實驗發(fā)現(xiàn)，CDNIM社團(tuán)發(fā)現(xiàn)算法與目前較流行的社團(tuán)發(fā)現(xiàn)算法相比，挖掘復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)準(zhǔn)確率較高.

參考文獻(xiàn)

[1]Watts D J, Strogatz S H. Collective dynamics of ″small world″ networks [J]. Nature, 1998, 393(6684): 440-442.

[2]Barabási A L,Albert R Emergence of scaling in random networks[J].Science,1999,286:509-512.

[3]趙之瀅，于海，朱志良，等．基于網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的節(jié)點傳播影響力分析[J]．計算機(jī)學(xué)報，2014(04)：753-766．

[4]周漩，張鳳鳴，李克武，等．利用重要度評價矩陣確定復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點[J]．物理學(xué)報，2012(05)：1-7．

[5]程澤凱，張佳玉．基于節(jié)點相似度的社團(tuán)發(fā)現(xiàn)算法[J]．計算機(jī)工程與設(shè)計，2014(05)：1688-1693．

[6]周林，平西建，徐森，等．基于譜聚類的聚類集成算法[J]．自動化學(xué)報，2012(08)：335-1342．

[7]吳建平，宋君強(qiáng)，張衛(wèi)民，等．計算Fiedler向量的一種高效準(zhǔn)確方法[J]．計算機(jī)學(xué)報，2013(11)：2266-2273．

[8]羅倩．K-means聚類中心的魯棒優(yōu)化算法[J]．計算機(jī)工程與設(shè)計，2015(09)：2395-2400．

[9]沙愛暉，黃樹成，李甜．一種基于網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)和模塊化函數(shù)的聚類算法[J]．計算機(jī)應(yīng)用與軟件，2014(04)：274-277．

[10]馬菲，,徐汀榮，孫龍．基于三角形的重疊社團(tuán)發(fā)現(xiàn)算法[J]．計算機(jī)應(yīng)用研究，2014(02)：348-350+368．

[11]蔡曉妍，戴冠中，楊黎斌．基于譜聚類的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法[J].計算機(jī)科學(xué)，2009(09)：49-50+95．

[12]謝鋒．基于GN算法的文獻(xiàn)聚類方法研究[J]．科技傳播，2013(02):194-195．

[13]Hong Jin,Shuliang Wang,Chenyang Li. Community detection in complex networks by density-based clustering[J]. Physica A: Statistical Mechanics and Its Applications,2013(3):9219:.

[14]Amiri B, Hossain L, Crawford J W, et al. Community Detection in Complex Networks:Multi-objective Enhanced Firefly Algorithm[J]. Knowledge-Based Systems, 2013, 46(Complete):1-11.

中圖分類號TP181

文獻(xiàn)標(biāo)識碼A

文章編號1672-4321(2016)01-0119-04

基金項目國家自然科學(xué)基金資助項目(60473125)

作者簡介吳衛(wèi)江 (1971-)，男，副教授，博士，研究方向：數(shù)據(jù)挖掘，E-mail：allan1226@163.com

收稿日期2015-12-29 *通訊作者周靜(1989-)，女，碩士生，研究方向：數(shù)據(jù)挖掘，E-mail：15101148869@126.com