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

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

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

?

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

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

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

摘要指出了通過(guò)挖掘復(fù)雜網(wǎng)絡(luò)中存在的社團(tuán)結(jié)構(gòu)，可以分析整個(gè)復(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é)點(diǎn)重要度矩陣和聚類矩陣，結(jié)合圖的特征譜平分法和模塊度函數(shù)，提出了一種基于節(jié)點(diǎn)重要度的社團(tuán)劃分算法(CDNIM).通過(guò)在空手道俱樂(lè)部、海豚關(guān)系網(wǎng)絡(luò)等多個(gè)經(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)實(shí)世界中，存在著各式各樣的網(wǎng)絡(luò)，如科技網(wǎng)、社會(huì)網(wǎng)絡(luò)、生物網(wǎng)等,它們都可以抽象成復(fù)雜網(wǎng)絡(luò).小世界[1]和無(wú)標(biāo)度[2]特性是研究復(fù)雜網(wǎng)絡(luò)理論的開(kāi)創(chuàng)性標(biāo)志，隨著人們對(duì)復(fù)雜網(wǎng)絡(luò)的研究不斷深入，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的另外一個(gè)特性，即社團(tuán)結(jié)構(gòu)[3]特性.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)表征為：存在于單個(gè)社團(tuán)內(nèi)部的各個(gè)節(jié)點(diǎn)之間的邊較多，分布比較有地域密集性，而社團(tuán)之間相互連接的邊比較少.這種社團(tuán)結(jié)構(gòu)暗示著同一社團(tuán)內(nèi)的節(jié)點(diǎn)具有相同的屬性或者是有其他相似的方面.對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，可以更好地了解現(xiàn)實(shí)網(wǎng)絡(luò)中的內(nèi)部組織結(jié)構(gòu)：依據(jù)復(fù)雜網(wǎng)絡(luò)中劃分的各個(gè)社團(tuán)的功能，可以推測(cè)出整個(gè)網(wǎng)絡(luò)的實(shí)際功能；研究網(wǎng)絡(luò)中某些節(jié)點(diǎn)的功能，可以推測(cè)在與該節(jié)點(diǎn)同一社團(tuán)內(nèi)其他節(jié)點(diǎn)的功能；研究網(wǎng)絡(luò)中劃分的各個(gè)社團(tuán)之間的聯(lián)系，可以清晰地認(rèn)知網(wǎng)絡(luò)的整體布局.因此，能夠有效地挖掘出復(fù)雜網(wǎng)絡(luò)中存在的社團(tuán)結(jié)構(gòu)，對(duì)于現(xiàn)實(shí)網(wǎng)絡(luò)的研究具有非常重要的意義.

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

1相關(guān)定義

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

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

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

(1)

(2)

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

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

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

2CDNIM算法

2.1CDNIM算法概述

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

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

輸入：具有n個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò)G=，需要?jiǎng)澐值纳鐖F(tuán)個(gè)數(shù)為k；

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

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

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

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

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

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

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

聚類分析中的k-means算法的k值需要根據(jù)經(jīng)驗(yàn)得到，本文提出的CDNIM算法輸入也包含復(fù)雜網(wǎng)絡(luò)中的社團(tuán)個(gè)數(shù)k，這里k值需要根據(jù)模塊度Q值確定.對(duì)于一個(gè)復(fù)雜網(wǎng)絡(luò)，我們事先并不知道該網(wǎng)絡(luò)中到底存在多少個(gè)社團(tuán)，更不知道該網(wǎng)絡(luò)應(yīng)該被劃分成多少個(gè)社團(tuán)才是符合現(xiàn)實(shí)情況的.本文算法中的k值可以通過(guò)Newman和Girvan提出的模塊度函數(shù)Q[9]確定，函數(shù)Q作為網(wǎng)絡(luò)劃分的一個(gè)衡量標(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ì)量越好時(shí)模塊度Q值越大.當(dāng)CDNIM算法運(yùn)行結(jié)束時(shí)，不同的社團(tuán)劃分個(gè)數(shù)對(duì)應(yīng)不同的模塊度Q值，Q值最大時(shí)對(duì)應(yīng)的網(wǎng)絡(luò)社團(tuán)劃分方案就是最佳的社團(tuán)劃分結(jié)果，即最佳的k值.

3算法驗(yàn)證及分析

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

3.1實(shí)驗(yàn)數(shù)據(jù)集

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

(2)海豚關(guān)系網(wǎng)絡(luò).另外一個(gè)檢測(cè)網(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é)點(diǎn)代表海豚，159條邊代表海豚之間有頻繁的往來(lái)關(guān)系.海豚關(guān)系網(wǎng)初始分裂為2個(gè)社團(tuán).

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

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

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

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

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

3.3CDNIM算法劃分足球隊(duì)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

3.5實(shí)驗(yàn)結(jié)果分析

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

接時(shí)，該節(jié)點(diǎn)的度值發(fā)生變化，其負(fù)載和重要度也會(huì)變化，通過(guò)與鄰居節(jié)點(diǎn)之間的傳遞，形成了重要度貢獻(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個(gè)數(shù)據(jù)集上的劃分結(jié)果的準(zhǔn)確率Fig.2　The accuracy of different algorithms on five data sets of the partition result

4結(jié)束語(yǔ)

本文借鑒了譜平分法的思想，將節(jié)點(diǎn)重要度矩陣與k-means算法相結(jié)合，提出了一種新的社團(tuán)劃分算法，然后利用一個(gè)聚類度量函數(shù)—模塊度函數(shù)來(lái)查找出網(wǎng)絡(luò)中最佳社團(tuán)的數(shù)目，得到網(wǎng)絡(luò)的最佳社團(tuán)劃分結(jié)果.CDNIM社團(tuán)發(fā)現(xiàn)算法在多個(gè)經(jīng)典的數(shù)據(jù)集上得到了正確的驗(yàn)證，證明了該算法在復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)中的有效性和正確性；通過(guò)實(shí)驗(yà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é)點(diǎn)傳播影響力分析[J]．計(jì)算機(jī)學(xué)報(bào)，2014(04)：753-766．

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

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

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

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

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

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

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

[11]蔡曉妍，戴冠中，楊黎斌．基于譜聚類的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法[J].計(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.

中圖分類號(hào)TP181

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

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

基金項(xiàng)目國(guó)家自然科學(xué)基金資助項(xiàng)目(60473125)

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

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