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

喬健，楊昆朋

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

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

喬健，楊昆朋

（北京交通大學(xué)計(jì)算機(jī)與信息技術(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ò)都具有共同特點(diǎn)，即復(fù)雜的內(nèi)部結(jié)構(gòu)，因此被稱為復(fù)雜網(wǎng)絡(luò)。在復(fù)雜網(wǎng)絡(luò)中，每一個(gè)節(jié)點(diǎn)表示網(wǎng)絡(luò)中的個(gè)體，節(jié)點(diǎn)之間的連邊表示個(gè)體之間的相互關(guān)系以及相互作用。已有研究表明：這些網(wǎng)絡(luò)中包含著一些潛在的社區(qū)結(jié)構(gòu)［4］。通常，社區(qū)內(nèi)的節(jié)點(diǎn)具有相似的特性，在網(wǎng)絡(luò)中扮演著相似的角色，通過社區(qū)劃分來識別網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，有助于我們更深入地理解網(wǎng)絡(luò)的本質(zhì)，認(rèn)識網(wǎng)絡(luò)結(jié)構(gòu)與其功能之間的關(guān)系［5］。目前，社區(qū)劃分方法已被應(yīng)用于恐怖組織識別、社會網(wǎng)絡(luò)分析、蛋白質(zhì)交互網(wǎng)絡(luò)分析［6］、Web文檔聚類和論文引證網(wǎng)絡(luò)等各個(gè)方面。

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

1　K-means基礎(chǔ)

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

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

算法：K-means算法

輸入：點(diǎn)集合NodeList，簇的個(gè)數(shù)K

輸出：簇列表CommunityList；

（1）隨機(jī)選擇K個(gè)簇的初始中心節(jié)點(diǎn)；

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

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

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

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

2　相關(guān)定義

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

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

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

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

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

3　算法提出

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

給定無向連通圖G=（V，E），用n，m，K表示G中的節(jié)點(diǎn)數(shù)、連邊數(shù)以及社團(tuán)數(shù)。基于中心度的K-means型社團(tuán)檢測算法如下步驟實(shí)現(xiàn)：

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

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

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

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

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

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

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

4　實(shí)驗(yàn)效果展示

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

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

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

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

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

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

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

Modularity的定義如下：

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

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

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

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

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

5　結(jié)語

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

［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é)報(bào)，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-），男，寧夏固原人，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、模式識別

2015-01-15

2015-03-11

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

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

楊昆朋（1988-），男，河南鄧州人，碩士研究生，研究方向?yàn)闄C(jī)器學(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.