喬健，楊昆朋

（北京交通大學(xué)計算機與信息技術(shù)學(xué)院，北京　100044）

一種基于節(jié)點中心度的社區(qū)劃分新算法

喬健，楊昆朋

（北京交通大學(xué)計算機與信息技術(shù)學(xué)院，北京100044）

0　引言

人類社會中很多的系統(tǒng)都可以抽象為網(wǎng)絡(luò)，如人際關(guān)系網(wǎng)［1］、論文引征網(wǎng)、科學(xué)家合作關(guān)系網(wǎng)［2］、微博用戶關(guān)系網(wǎng)、互聯(lián)網(wǎng)［3］等。這些網(wǎng)絡(luò)都具有共同特點，即復(fù)雜的內(nèi)部結(jié)構(gòu)，因此被稱為復(fù)雜網(wǎng)絡(luò)。在復(fù)雜網(wǎng)絡(luò)中，每一個節(jié)點表示網(wǎng)絡(luò)中的個體，節(jié)點之間的連邊表示個體之間的相互關(guān)系以及相互作用。已有研究表明：這些網(wǎng)絡(luò)中包含著一些潛在的社區(qū)結(jié)構(gòu)［4］。通常，社區(qū)內(nèi)的節(jié)點具有相似的特性，在網(wǎng)絡(luò)中扮演著相似的角色，通過社區(qū)劃分來識別網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，有助于我們更深入地理解網(wǎng)絡(luò)的本質(zhì)，認識網(wǎng)絡(luò)結(jié)構(gòu)與其功能之間的關(guān)系［5］。目前，社區(qū)劃分方法已被應(yīng)用于恐怖組織識別、社會網(wǎng)絡(luò)分析、蛋白質(zhì)交互網(wǎng)絡(luò)分析［6］、Web文檔聚類和論文引證網(wǎng)絡(luò)等各個方面。

由于社區(qū)劃分就是對網(wǎng)絡(luò)中的節(jié)點進行分組，因此社區(qū)劃分的本質(zhì)是一個聚類問題［7］。如果定義了網(wǎng)絡(luò)中節(jié)點之間的相似度，那么就可以使用任意一種聚類算法對網(wǎng)絡(luò)中的節(jié)點進行聚類，從而達到網(wǎng)絡(luò)社區(qū)劃分的目的。因此，許多聚類算法都可以用來對網(wǎng)絡(luò)進行社區(qū)劃分，如K-means［8］算法、AP［8］、NMF［9］算法等。其中K-means算法是一種受到廣泛使用的，最為經(jīng)典的基于劃分的聚類方法，有著效率好、易于理解、算法靈活等優(yōu)點。

1　K-means基礎(chǔ)

K-means算法的基本思想是：以空間中K個點為中心進行聚類，將最靠近它們的節(jié)點歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。

假設(shè)要把樣本集分為K個簇，算法描述如下：

算法：K-means算法

輸入：點集合NodeList，簇的個數(shù)K

輸出：簇列表CommunityList；

（1）隨機選擇K個簇的初始中心節(jié)點；

（2）在第t次迭代中，對每一個點，求其到K個中心的相似度，將該點歸到相似度最大的中心節(jié)點所在的簇中；

（3）利用均值等方法更新簇的中心值；

（4）對于所有的K個聚類中心，如果利用步驟（2），（3）的迭代法更新后，這K個聚類中心在某個精度范圍內(nèi)不變化或者達到最大迭代次數(shù)，則算法結(jié)束，否則重復(fù)執(zhí)行步驟（2）。

K-means算法的時間復(fù)雜度為O（tKNd），空間復(fù)雜度為O（（d+K）N），其中，t為迭代次數(shù)，K為所期望劃分的簇的個數(shù)，N為節(jié)點數(shù)，d為特征向量的維度。傳統(tǒng)的K-means算法也有很大的缺陷，其劃分結(jié)果對初始中心節(jié)點十分敏感，而隨機選取初始中心節(jié)點的方法會導(dǎo)致K-means算法劃分結(jié)果不穩(wěn)定、度差、劃分結(jié)果中很容易出現(xiàn)空社團等問題。本文針對K-means算法的上述缺點，提出了一種基于中心度的中心節(jié)點選取法的K-means改進算法——CDK（Center Degree K-Means）算法?；舅枷胧歉鶕?jù)節(jié)點的中心度（degree centrality）以及節(jié)點之間的最短路徑來選取初始社團的中心節(jié)點。優(yōu)先選擇中心度較大的節(jié)點為初始中心點，并且通過節(jié)點之間的最短路徑來保證各中心節(jié)點之間的距離最遠。CDK算法保證了劃分結(jié)果有較高的精確度和穩(wěn)定性，避免出現(xiàn)空的社團，并且由于使用中心度來刷新中心節(jié)點，避免了每次迭代都需要計算質(zhì)心以及相似度，因此降低了時間復(fù)雜。

2　相關(guān)定義

給定圖G（V，E），V=｛v1，v2，…，vn｝表示圖中的節(jié)點集合，E?｛（vi，vj）|vi，vj∈V｝表示節(jié)點之間的鏈接集合，圖G可以用鄰接矩陣描述。

定義1鄰接矩陣：鄰接矩陣描述圖中各節(jié)點兩兩之間的關(guān)系。鄰接矩陣A=｛aij｝的元素aij定義為如果（vi，vj∈V），元素aij=1，否則aij=0。

定義2節(jié)點中心度：節(jié)點中心度基本思想是重要的節(jié)點是那些擁有與其他節(jié)點有較多連接邊數(shù)的節(jié)點。一個網(wǎng)絡(luò)圖中節(jié)點的重要性可依據(jù)它們度分布的大小進行排序。相應(yīng)的，節(jié)點vi的中心度［6］定義如下：

其中D表示節(jié)點的度，n表示網(wǎng)絡(luò)中的節(jié)點個數(shù)。

定義3節(jié)點相似度：節(jié)點相似度用來衡量兩個節(jié)點之間的相似性，來決定它們是否屬于同一類別。基于節(jié)點鄰居信息的Jaccard［11］相似度定義如下：

3　算法提出

節(jié)點中心度描述了節(jié)點在網(wǎng)絡(luò)中處于中心的程度。如果網(wǎng)絡(luò)看做一個社團，那么節(jié)點中心度最大的節(jié)點應(yīng)該是社團的中心節(jié)點［11］。根據(jù)這個思想，我們可以將網(wǎng)絡(luò)中的節(jié)點按照節(jié)點中心度進行排序，然后選取中心度最大的節(jié)點作為第一個中心節(jié)點，而對于其他的中心節(jié)點，我們除了要考慮節(jié)點自身的中心度之外，還需要考慮節(jié)點與其他中心節(jié)點的距離，必須要保證中心節(jié)點之間的距離盡可能遠，這樣才能保證社團之間的相似度盡可能小。因此我們可以使用節(jié)點之間的最短路徑來保證中心節(jié)點之間的距離盡可能的遠。我們可以使用一個臨界值μ，如果候選與已選中心節(jié)點的最短路徑均大于μ則可以選為新的中心節(jié)點，否則放棄該節(jié)點。

給定無向連通圖G=（V，E），用n，m，K表示G中的節(jié)點數(shù)、連邊數(shù)以及社團數(shù)?；谥行亩鹊腒-means型社團檢測算法如下步驟實現(xiàn)：

輸入：社團數(shù)目K，臨界值μ；

輸出：網(wǎng)絡(luò)G的社區(qū)劃分結(jié)構(gòu)；

（1）排序：對網(wǎng)絡(luò)中的節(jié)點按照中心度大小進行降序排序；

（2）選擇初始中心節(jié)點：找出網(wǎng)絡(luò)中中心度最大的節(jié)點作為第一個初始節(jié)點并加入社團中心點集C；按中心度的順序迭代網(wǎng)絡(luò)中的節(jié)點，對于節(jié)點vi，如果它與C中的節(jié)點的最短路徑均大于μ則選vi為新的中心節(jié)點并且加入C，否則查看下一節(jié)點，直至找到K個初始中心節(jié)點。

（3）節(jié)點劃分：迭代網(wǎng)絡(luò)中的非中心節(jié)點，對于節(jié)點vi，通過公式（2）計算vi于C中的中心節(jié)點的相似度，將vi劃分與相似度最大的那個中心點所在的社團中。

（4）刷新中心節(jié)點：對每一個社團中的節(jié)點按照中心度進行排序，選取當(dāng)前社團中中心度最大的節(jié)點作為新的中心節(jié)點。

（5）判斷結(jié)束條件：比較刷新后得到的中心節(jié)點比起上一次的中心節(jié)點，如果沒有發(fā)生變動或者達到算法最大迭代次數(shù)T則結(jié)束，否則循環(huán)執(zhí)行第（3）步。

4　實驗效果展示

為了驗證本算法的性能，本文將DCK算法和傳統(tǒng)的K-means算法以及GN［6］算法同時應(yīng)用在Citeseer和Cora網(wǎng)絡(luò)進行了比較，用ACC、NMI、PWF和Modularity這四個指標(biāo)來輔助評價劃分效果。

假設(shè)網(wǎng)絡(luò)G的社區(qū)結(jié)構(gòu)C=｛C1，C2，…，Ck｝表示真實的社區(qū)結(jié)構(gòu)，Ck表示第k個社團，Ck中包含一系列節(jié)點。C'=｛C1'，C2'，…，Ck'｝表示由一個社區(qū)劃分算法劃分出的社區(qū)結(jié)構(gòu)。因此標(biāo)準化互信息NMI定義如下：

其中p（Ck）表示從網(wǎng)絡(luò)中隨機抽取一個節(jié)點，該節(jié)點屬于社團Ck的概率，p（Ck，Cl'）表示隨機抽取的節(jié)點屬于社團Ck和Cl'的聯(lián)合概率。

假設(shè)T表示在劃分C中，屬于同一個社區(qū)的節(jié)點對（i，j）的集合。S表示在劃分C'中，屬于同一個社區(qū)的節(jié)點對（i，j）的集合。因此PWF的計算公式定義如下：

其中Npre=|S∩T|/|S|和Nre=|S∩T|/|T|。

假設(shè)節(jié)點i的真實類標(biāo)簽是si，由劃分C分配；ri由劃分C'分配的類標(biāo)簽，則劃分C'的精確度ACC定義如下：

其中Nset表示網(wǎng)絡(luò)G的節(jié)點集合，δ（x，y）是狄利克雷函數(shù)，如果x=y函數(shù)值為1，否則為0，|Nset|表示節(jié)點個數(shù)。

Modularity的定義如下：

其中dout（i）和din（j）分別表示節(jié)點i和j的出度和入度，e表示網(wǎng)絡(luò)中的有向邊的個數(shù)，ci表示節(jié)點i所在的社團，δ（ci，cj）表示克羅內(nèi)克函數(shù)，Modularity值越大，說明效果越好。

用 Java1.7編寫算法程序，在Lenovo ThinkPad T420筆記本電腦上進行了實現(xiàn)。結(jié)果如下：

表1　Citeseer數(shù)據(jù)集各項指標(biāo)

表2　Cora數(shù)據(jù)集各項指標(biāo)

由表1和表2的數(shù)據(jù)，我們可以看出使用DCK算法進行社區(qū)劃分的精度以及模塊度要遠遠好于K-means算法和GN算法，并且同樣的數(shù)據(jù)DCK算法運行時間要遠遠小于K-means算法和GN算法。

5　結(jié)語

本文給出了一種基于節(jié)點中心度的社區(qū)劃分新算法，該算法利用了節(jié)點中心度的思想結(jié)合節(jié)點間最短路徑，通過臨界值μ來保證初始中心節(jié)點的之間的距離盡可能的遠。把該算法應(yīng)用在Citeseer和Cora數(shù)據(jù)集上，并與K-means算法和GN算法做了比較，實驗表明DCK算法在運行效率和效果上比起傳統(tǒng)的K-means算法和GN算法具有明顯的優(yōu)勢。但是DCK算法適合于社團特征較為明顯的網(wǎng)絡(luò)，若社團結(jié)構(gòu)不明顯，不但社團數(shù)K難以確定，對初始中心點的選取也會有一定偏差，如何解決此問題是本文進一步要做的工作。

［1］Amaral LAN，Scala A，Barthelemy M，et al．Classes of Small-World Networks［J］．Proc．Natl.Acad.Sci.USA，2000，97（21）：11149～11152

［2］Redner S．How Popular is Your Paper.An Empirical Study of the Citation Distribution［J］．EurPhys JB，1998，4：131～134

［3］楊博，劉大有，劉繼明等．復(fù)雜網(wǎng)絡(luò)聚類方法［J］．軟件學(xué)報，2009，20（1）：54～66

［4］Watts D J，Strogatz Steven H．Collective Dynamics of Small-World'Networks［J］．Nature，1998,393（6684）：440～442

［5］Albert R，Barabasi A-L.Emergence of Scaling in Random Networks［J］.Scinece，1999，286（5439）：509～512

［6］Girvan M，Newman M E J.Community Structure in Social and Biological Networks［J］.Proc.Natl.Acad.Sci.，2002，99（12）：7821～7826

［7］Yawen Jiang，Caiyan Jia，Jian Yu.An Efficient Community Detection Method Based on Rank Centrality［J］.Physica A，2013，392：2182～2194

［8］J.B.MacQueen.Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability，Berkeley，University of California Press，1：281～297（1967）

［9］Frey B.J.and Dueck D.Science，315，972～976（2007）

［10］C.Ding，X.He，Horst D.Simon，SDM（2004）

［11］Liu Zhi-yuan，Li Peng，Zheng Ya-bin，et al.Community Detection by Affinity Propagation［R］，2008

Degree Centrality；K-means；Community Detecting

New Algorithm of Detecting Community Structure Based on Degree Centrality

QIAO Jian，YANG Kun-peng
（School of Computer and Information Technology，Beijing Jiaotong University，Beijing 100044）

1007-1423（2015）08-0022-04

10.3969/j.issn.1007-1423.2015.08.005

喬健（1984-），男，寧夏固原人，碩士研究生，研究方向為數(shù)據(jù)挖掘、模式識別

2015-01-15

2015-03-11

針對傳統(tǒng)的K-means算法的劃分結(jié)果受初始中心節(jié)點影響較大，以及每次刷新中心節(jié)點均需要進行計算，使得算法運行時間較高等問題，提出一種基于中心度的K-means改進算法CDK算法。該算法根據(jù)節(jié)點的中心度以及節(jié)點之間的最短路徑來確定初始社團的中心節(jié)點，然后根據(jù)節(jié)點之間的Jaccard相似度，將非中心節(jié)點劃分到K個社團中。CDK算法避免了傳統(tǒng)的K-means算法由于隨機選取初始中心點而造成劃分結(jié)果不穩(wěn)定、精度較差的問題，同時CDK算法在刷新中心節(jié)點的時候無須進行計算，具有更低的時間復(fù)雜度。

中心度；K-means；社區(qū)發(fā)現(xiàn)

楊昆朋（1988-），男，河南鄧州人，碩士研究生，研究方向為機器學(xué)習(xí)、深度學(xué)習(xí)

Dividing the result for the traditional K-means algorithm is influenced by the initial central node,and each refresh center nodes need to be calculated,cause the higher algorithm running time and other issues.Proposes an improved algorithm based on centrality of K-means, CDK algorithm.The algorithm is based on the shortest path between the node and the node to the center of the central node determining the initial associations,then according to Jaccard similarity between nodes,will be divided into K non-central node in societies.CDK algorithm avoids the traditional K-means algorithm due to the random selection of initial results of the center divide and cause instability, poor accuracy problems,while CDK refresh algorithm when the central node without calculation,has a lower time complexity.