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

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

?

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

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

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

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

關鍵詞復雜網(wǎng)絡； 社團結構； 譜平分； 聚類算法； 模塊度

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

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

1相關定義

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

定義1：設節(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表達式為：

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

(1)

(2)

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

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

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

2CDNIM算法

2.1CDNIM算法概述

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

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

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

輸出：網(wǎng)絡的社團集合S；

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

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

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

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

(5)根據(jù)以上步驟，可以得到k-1個Q值，社團的最佳社團結構即對應最大的Q值.

2.2網(wǎng)絡社團數(shù)目k值確定

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

綜上，網(wǎng)絡的社團劃分結構決定了模塊度的大小，即網(wǎng)絡劃分的社團結構強度越強，劃分質量越好時模塊度Q值越大.當CDNIM算法運行結束時，不同的社團劃分個數(shù)對應不同的模塊度Q值，Q值最大時對應的網(wǎng)絡社團劃分方案就是最佳的社團劃分結果，即最佳的k值.

3算法驗證及分析

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

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

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

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

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

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

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

3.2驗證社團個數(shù)k值實驗結果

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

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

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

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

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

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

表3　CDNIM算法在足球隊網(wǎng)絡上的社團劃分結果

3.4多種社團劃分算法實驗結果

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

3.5實驗結果分析

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

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

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

4結束語

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

參考文獻

[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)絡社團結構的節(jié)點傳播影響力分析[J]．計算機學報，2014(04)：753-766．

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

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

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

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

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

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

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

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

[12]謝鋒．基于GN算法的文獻聚類方法研究[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

文獻標識碼A

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

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

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

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