基于Ｋ－ｍｅａｎｓ聚類算法的復雜網絡社團發現新方法

摘 要：提出了一種基于K-means 聚類算法的復雜網絡社團結構劃分方法。算法基于Fortunato等人提出的邊的信息中心度，定義了節點的關聯度，并通過節點關聯度矩陣來進行聚類中心的選擇和節點聚類，從而將復雜網絡劃分成k個社團，然后通過模塊度來確定網絡理想的社團結構。該算法有效地避免了K-means 聚類算法對初始化選值敏感性的問題。通過Zachary Karate Club和College Football Network兩個經典模型驗證了該算法的可行性。

關鍵詞：復雜網絡；社團結構；K-means聚類算法；節點關聯度

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)06-2041-03

doi:10.3969/j.issn.1001-3695.2009.06.012

Detecting community in complex networks using K-means cluster algorithm

ZHAO Feng-xia，XIE Fu-ding

(College of Computer Information Technology， Liaoning Normal University， Dalian Liaoning 116029， China)

Abstract:

This paper proposed a new detecting method based on K-means cluster algorithm.Through the definition of node link based on information centrality which Fortunato proposed and the selection of the clustering center and the clustering of the node according node link， the approach identified the network to k communities， then identified the ideally community structure according modularity.The algorithm could find clustering center better and it is robust to initialization， so the quality of detecting was improved greatly.It tested the algorithm on the two network data named Zachary Karate Club and College Football Network.

Key words:complex network; community structure; K-means cluster algorithm; node link

0 引言

隨著對復雜網絡性質的物理意義和數學特性的深入研究，人們發現許多實際網絡都具有一個共同性質，即社團結構。也就是說，整個網絡是由若干個群或團構成的。每個群內部節點之間的連接相對非常緊密，而各個群之間的連接相對來說卻比較稀疏。復雜網絡社團結構的研究對于控制疾病傳播、網絡病毒的傳播等具有重大意義。尋找網絡社團結構的算法一般可分為社會學中的分級聚類^[1~3]和計算機科學中的圖分割兩類。分級聚類是探測網絡社團的傳統方法， 算法基于各個節點間連接的相似性或強度將網絡劃分成若干個子群， 且根據劃分時是向網絡中添加還是移除邊可分為凝聚算法^[4]和分裂算法兩類。應用比較廣泛的分級聚類方法是由Girvan等人提出的基于邊介數的分裂算法(簡稱GN算法)。圖分割算法的代表是Kernighan-Lin算法^[5]和譜平分法^[6]。其中 Kernighan-Lin算法是根據使社團內部及社團間的邊最優化的原則對原始的網絡進行分類；譜平分法是根據網絡圖的 Laplace矩陣向特征向量空間進行譜映射。

K-means聚類算法^[7，8]是由MacQueen提出的基于劃分的聚類算法，該算法是目前應用最為廣泛的聚類算法之一，它具有算法簡單且收斂速度快的特點。但是該算法的性能依賴于聚類中心的初始位置，即對于隨機的初始值選取可能導致不同的聚類結果，甚至存在無解的情況，而且算法對孤立點和噪聲數據很敏感。

本文首先定義了網絡中節點關聯度，并構建了節點關聯度矩陣，在此基礎上給出了一種基于K-means聚類算法的復雜網絡社團發現方法。該算法以最小關聯度原則選取新的聚類中心，以最大關聯度原則進行模式歸類，直到所有的節點都劃分完為止，最后根據模塊度來確定理想的社團數。該算法根據節點關聯度特征值，能夠較好地找到聚類中心，有效地避免了對初始化選值敏感性的問題，從而使得社團發現質量大大提高。實驗結果說明了該算法的可行性。

1 關聯度與模塊度

1.1 節點關聯度

網絡中兩個相鄰節點之間的關聯度是由它們所共享的邊來決定的。兩個相鄰節點之間共享的邊的信息中心度越小，它們不是社團間傳輸信息的路徑的可能性就越大，則它們屬于同一個社團的概率就越大，它們之間的連接就越緊密，關聯度就越高。

Fortunato等人^[9]提出了一種基于信息中心度的社團探測算法。假設網絡G有n個節點和m條邊。為了衡量節點傳輸信息的有效性，引入網絡效率NE的概念。假設網絡中兩個節點之間的信息總是沿著最短路徑傳播的，則節點i和j之間的信息傳輸效率εij為它們之間最短路徑長度dij的倒數（如果節點i和j之間不存在路徑，則最短路徑長度為∞，εij=0）。整個網絡G的信息有效率定義為各節點對的信息傳輸有效率的平均值NE[G]，即NE[G]=i≠j∈Gεij/[n(n-1)]=

1/[n(n-1)]i≠j∈G1/dij(1)

邊eij的信息中心度Ceij定義為移除該邊后整個網絡的信息有效率減少的相對量，即

Ceij=ΔNE/NE=(NE[G]-NE[G′eij])/

NE[G](2)

通過分析可以看出，社團間的邊的信息中心度比社團內部邊的信息中心度大。顯然節點i與j之間的邊的信息中心度越小，它們的關聯度就越大，屬于同一個社團的概率就越大，則可定義兩個相鄰節點vi、vj的關聯度:

nodeLink(vi，vj)=1-Ceij(3)

其中:eij∈E（E為網絡的邊的集合）；Ceij為邊eij的信息中心度。



一般來說，網絡中非相鄰節點之間可能有多條路徑或者沒有路徑。顯然，兩個節點之間的路徑越長，它們的關聯度就越小。 假設網絡中每條邊的權值都為1，則求兩個非相鄰節點的關聯度的問題可轉換為求最短路徑問題。兩個非相鄰節點之間的最短路徑定義為含有最少邊的那條路徑，即節點間的最短路徑是連接兩點的所有路徑中節點數最少的路徑。因此，為求網絡中所有非相鄰節點之間的最大關聯度，需要找出圖中所有非相鄰節點之間的最短路徑。這可以通過廣度優先搜索算法求得，每進行一次廣度優先搜索就可以得到一個節點與其他各節點間的所有最短路徑。

記網絡中非相鄰節點vi和節點vj之間的最短路徑為shortPath(vi，vj)={(vi，vk)，(vk，vm)，…，(vn，vj)}，則非相鄰節點間的關聯度可用最短路徑上所有節點對的關聯度的乘積表示。如果非相鄰節點間的最短路徑數為s，則選擇其中乘積最大的作為非相鄰節點的關聯度，即

nodeLink(vi，vj)=maxs{(vi，vk)∈shortPath(vi，vj)nodeLink(vi，vk)}(4)

通過式（3）和（4）能夠構造網絡的節點關聯度矩陣L=[nodeLink(vi，vj)]|V|×|V|，顯然L是一個對稱矩陣。鑒于節點與其自身的關聯度nodeLink(vi，vi)=1，不影響社團劃分結果，故為了節省空間，置矩陣L主對角線上元素的值為相應節點的度，因而有

L|V|×|V|=deg(vi) i=j且vi，vj∈V

nodeLink(vi，vj)i≠j且vi，vj∈V(5)

1.2 社團模塊度

社團模塊度^[1]是Newman等人引進的一個衡量網絡劃分質量的度量標準。假設有某種劃分形式，將網絡劃分為k個社團。 定義一個k×k維的對稱矩陣E=(eij)。其中eij表示網絡中連接兩個不同社團的節點的邊在所有邊中所占的比例，這兩個節點分別位于第i和第j個社團。在這里所說的所有的邊是指原始網絡中的。因此模塊度衡量標準是利用完整的網絡來計算的。模塊度Q表示為

Q=i(eii-ai2)=Tre-‖e2‖

(6)

其中：Tre=ieii為矩陣E對角線上各元素之和，它表示網絡中連接某一個社團內部各節點的邊在所有邊的數目中所占比例；ai=jeij每行中各元素之和，它表示與第i個社團中的節點相連的邊在所有邊中所占的比例。Q值越大說明社團結構越明顯。

2 K-means復雜網絡社團發現算法

一般地，K-means聚類算法是在模式特征矢量集中，以最大距離原則選取新的聚類中心， 以最小距離原則進行模式歸類。將該原則應用到復雜網絡社團發現中，可以解釋為以最小關聯度原則選取新的聚類中心，再以最大關聯度原則進行模式歸類，直到所有的節點都劃分完為止。這樣選取的作為聚類中心的節點不僅具有與同類其他節點較強的連接強度， 而且與之相連的節點之間也具有較大的相互連接密度和強度，即具有較強的局部聚集性。克服了傳統的K-means 聚類算法對初始選值敏感性的缺點， 提高了社團劃分質量。K-means社團發現算法的具體步驟如下：

輸入：網絡的鄰接矩陣

輸出：網絡的社團結構

a）設core=(聚類中心節點集合)，V1=V-core（聚類中心以外的節點集合），k=2。根據式（3）和（4）求出網絡的節點關聯度矩陣L。

b）選擇節點集V1中度最大的節點c1作為第一個聚類中心：

core=core∪{c1}，V1=V1-{c1}

c)if |core|≠k，goto 步驟d）;else 步驟e）。

d)根據關聯度矩陣L，求出待劃分節點集V1中的節點vj(j=1，2，…，|V1|)與聚類中心節點集core中各個節點ci(i=1，2，…，|core|) 之間的平均節點關聯度的最小值lmin所對應的節點v∈V1作為新的聚類中心添加到core中。如果用lji表示節點vj與聚類中心ci的節點關聯度，lj表示節點vj與聚類中心core各節點關聯度的平均值，則

lj=|core|i=1lli/|core|，lmin=minj(lj)core=core∪{v}，V1=V1-{v}

轉步驟c)。

e)if V1≠，計算節點vj(j=1，2，…，|V1|)與哪個聚類中心節點的關聯度最大，它就屬于哪個聚類。一個聚類就是一個社團，輸出社團劃分結果。

f)計算當前社團劃分下的模塊度Q值。ifQk≥Qk-1 then k=k+1，轉步驟c);else結束（最大的模塊度對應社團劃分就是實際的社團劃分）。

3 算法例證及分析

為了測試本文算法的可行性，首先給出了一個具有明顯社團結構的簡單網絡說明算法；然后針對兩個經典模型Zachary Karate Club和College Football Network進行了計算。實驗結果表明，該復雜網絡社團發現算法是行之有效的，且具有較高的精度。

3.1 算法例證

例1 圖1為一個具有明顯社團結構的簡單網絡，由 12個節點組成，理想社團數為3，L為其對應的節點關聯度矩陣。

先按式(3)和(4)求得網絡節點的關聯度矩陣L(如式(7))。由于L是對稱陣，只列出上三角和主對角線上的元素。基于該矩陣，利用本文給出的算法（當k=3時），首先把度最大的9號節點作為聚類中心，然后找到與9號節點關聯度最小的8號節點作為第二個聚類中心，接著找到與已有聚類中心平均關聯度最小的4號節點作為第三個聚類中心，則求得聚類中心節點集為core=(9，8，4)；在此基礎上，進一步聚類網絡中其余節點，節點與哪個聚類中心關聯度最大就歸屬于哪個聚類中心所屬的社團。通過聚類的社團劃分結果為cum1={9，10，11，12}，cum2={6，7，8}，cum3={1，2，3，4，5}。當聚類數k={1，2，3，4，5}時，對應的模塊度分別為Q={0，0.1150，0.3775，0.2350，0.0101}。可以看出，當網絡分成三個社團時的模塊度Q最大，就認為理想的社團劃分應該是聚成三類時對應的社團劃分結果。

例2 Zachary Karate Club^[10]。

20世紀70年代初期，Zachary用了兩年的時間來觀察美國一所大學中的空手道俱樂部成員間的相互社會關系。基于這些成員在俱樂部內部及外部的社會關系，他構造了他們之間的關系網。在調查過程中，該俱樂部的主管與校長之間因是否提高俱樂部收費的問題產生了爭執。結果，該俱樂部分裂成了兩個分別以主管和校長為核心的小俱樂部。在復雜網絡的社區結構分析中，Zachary Karate Club網絡已經成為一個經典的問題，很多分析網絡社區結構的算法中都用到了這個例子。圖2為聚類結果，當聚成兩個社團時，對應的模塊度最高，與實際符合。聚類結果與其他文獻結果幾乎一致，只是3號節點歸屬社團與其不同，因為3號節點本身有歧義。

例3 College Football Network^[11]。

College Football Network模型是美國大學生足球聯賽抽出來的一個復雜網絡模型。足球聯賽中有若干支球隊，網絡的節點代表一只足球隊，兩個節點之間的邊表示兩支球隊之間進行過一場比賽。聯賽中存在若干的聯盟，每個球隊都屬于其中一個聯盟。聯盟內部的球隊之間進行的比賽次數多于聯盟之間的球隊之間進行的比賽次數。該模型數據收集于2000年賽季的真實比賽情況，由Girvan與Newman收集整理而成，存在115支球隊（節點）及616場比賽（邊），包含了12個聯盟。圖3為College Football Network模型的網絡圖，圖4為用本算法將網絡劃分為k個社團時所對應的模塊度，可以看出劃分為12個社團時對應的模塊度最高。通過本文算法解決球隊聯盟劃分的問題，當劃分為12個社團時，再次表現出為一種切實可行的方法。根據結論對比聯賽的真實劃分情況，正確率超過83%。相比較Newman快速社區結構檢測算法^[4]，針對此模型，該算法只有78%。

3.2 算法分析

影響算法效率的因素主要有節點相關度矩陣L的求取、聚類中心的確立以及網絡中其余節點的歸類三方面。假設網絡中有n個節點、m條邊，希望的社團數為k。其中，矩陣L的求取要求找出網絡中所有非相鄰節點之間的最短路徑，可以通過廣度優先搜索算法求得。每進行一次廣度優先搜索就可以得到一個節點與其他各節點間的所有最短路徑，且算法復雜度為O（m）;聚類中心的確立時間復雜度為O(kn);其余節點歸類的時間復雜度為O(n)；則算法的時間復雜度為O((k+1)n+m)，為線性階。

4 結束語

發現復雜網絡的社團結構已經成為當今一個非常具有挑戰性的研究領域。本文創新點在于結合Fortunato等人提出的邊的信息中心度的定義，給出了節點相關度的定義，并求出了節點相關度矩陣，該矩陣形象地表現了節點間的相似度。將社團發現轉換成節點的聚類，可以把模式識別中的很多已有方法移植過來。通過實驗可以看出，社團劃分正確時的模塊度與錯誤劃分時的模塊度有明顯的差距。可以將聚類的各種算法的優勢加以結合開發出一種在初始化敏感度、準確率和運算耗時三方面都能表現良好的算法，并擴展到探測模糊社團，這都是今后要進一步深入研究的方向。

參考文獻：

［1］NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks[J].Phys Rev E， 2004，69(2):026113.

[2]CLAUSET A，NEWMAN M E J，MOORE C.Finding community structure in very large networks[J].Phys Rev E，2004，70(6):066111.

[3]BEZDEK J C，BOGGAVARAPU S，HALL L O，et al.Genetic algorithm guided clustering[C]//Proc of the 1st Conference on Evolutionary Computation.[S.l.]:IEEE Press，1994:34-39.

[4]NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Phys Rev E，2004，69(6):066133.

[5]KERNIGHAN B W，LIN S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970，49(1):291-307.

[6]POTHEN A，SIMON H，LIOU K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM J Matrix Anal Appl，1990，11(3):430-452.

[7]HAN Jia-wei，KANBER M.Data mining:concepts and techniques[M].San Francisco:Morgan Kaufmann Publishers，2000.

[8]ORDONEZ C，OMIECINSKI E.Efficient disk-based K-means clustering for relational databases [J].IEEE Trans on Knowledge and Data Engineering，2004，16(8):909-921.

[9]FORTUNATO S，LATORA V，MARCHIORI M.A method to find community structures based on information centrality[J].Phys Rev E，2004，70:056104.

[10]ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research，1977，33:452-473.

[11]GIRAN M，NEWMAN M E J.Community structure in social and biological networks [J].Proc of National Academy of Science，2002，99:7821-7826.

[12]BREIGER R L， BOORMAN S A， ARABIE P. An algorithm for clustering relations data with applications to social network analysis and comparison with multidimensional scaling[J].Journal of Mathema-tical Psychology，1975，12:328-383.