鄭浩原，黃 戰(zhàn)

（暨南大學 信息科學技術(shù)學院 計算機科學系，廣東 廣州 510632）

復雜網(wǎng)絡表示現(xiàn)實世界中具有網(wǎng)絡結(jié)構(gòu)特性的諸多系統(tǒng),它通常具有顯著的社區(qū)結(jié)構(gòu)，同質(zhì)頂點聚集在同一社區(qū)，異質(zhì)頂點分布于不同社區(qū)，表現(xiàn)為社區(qū)內(nèi)部頂點之間連接邊稠密，社區(qū)之間連接邊數(shù)量相對稀疏[1]。社區(qū)挖掘是復雜網(wǎng)絡分析領域的熱點問題，可以將現(xiàn)有的社區(qū)挖掘算法歸納為三大類[2]：基于優(yōu)化的算法、啟發(fā)式算法以及其他算法。基于相似度的層次聚類算法[3]屬于其他算法，這類算法不需要任何先驗知識就可以有效地發(fā)現(xiàn)復雜網(wǎng)絡中的社區(qū)結(jié)構(gòu)。當前的層次聚類算法的主要缺點是需要計算所有頂點對之間的相似度，時間復雜度為O(n2)，n表示圖中頂點數(shù)量，不適用于大規(guī)模網(wǎng)絡分析。針對這一缺點，受到社交網(wǎng)絡分析相關(guān)方法的啟發(fā)，本文提出一種改進的層次聚類算法。

社交網(wǎng)絡分析[4]是復雜網(wǎng)絡分析的一個分支，社交網(wǎng)絡中有一類Ego Networks，表現(xiàn)為有一個中心結(jié)點(即ego)，圖中所有其他結(jié)點（稱為alters）與中心結(jié)點直接連接，alter之間也有邊相連。社會學理論[5]指出，關(guān)系緊密的角色之間相似度偏高，如果兩個角色之間共同點越多，則這兩者就越有可能是朋友或者具有緊密的聯(lián)系。當與某確定角色比較，角色A與角色B的相似度值接近時，可以認為角色A與B具有某種同質(zhì)性?；谶@一理論，對層次聚類算法進行改進，在探測出網(wǎng)絡中扮演ego角色頂點的前提下，計算其他頂點與ego的相似度，而不是計算所有頂點對之間的相似度，此種情況下，算法時間復雜度為O(n)，計算負荷與網(wǎng)絡規(guī)模呈線性相關(guān)。實驗結(jié)果表明，該算法可能在準確性上稍有不足，但是能有效降低網(wǎng)絡分析規(guī)模、計算復雜度和大致發(fā)現(xiàn)網(wǎng)絡中的社區(qū)結(jié)構(gòu)。

1 算法準備

1.1 相似度計算

相似度[3-4]是對圖中頂點之間的相似或者相異程度的度量，是層次聚類算法的核心概念，可以大致將現(xiàn)有的相似度計算方法分為三大類：

第一類，可以將頂點嵌入到n維歐式空間中，通過給頂點分配合理的n維坐標，將網(wǎng)絡聚類問題轉(zhuǎn)化為空間點聚類問題。給定兩個頂點，A=(a1，a2，…，an)和 B=(b1，b2，…，bn)，則可以利用各種距離度量方法計算兩者的距離。例如，歐幾里得距離：

第二類，如果頂點不能嵌入到歐式空間中，這種情形下，還可以根據(jù)圖中頂點之間的鄰接關(guān)系計算相似度。一種方法將頂點間距離定義為：

A表示圖的鄰接矩陣。這是一種基于結(jié)構(gòu)同等概念的度量頂點相異度的方法。結(jié)構(gòu)同等指兩個頂點之間有相同的鄰接頂點，若 i和 j結(jié)構(gòu)同等，則 dij=0；頂點度高且存在較多不同鄰接頂點的頂點之間，相異度高。

根據(jù)圖的鄰接矩陣，可以利用行或列向量表示頂點之間的海明距離度量頂點間的匹配程度，也是相似度度量方法之一。例如，有如下鄰接矩陣A：

頂點 A=(0，1，1，1)、B=(1，0，0，1)，則兩者之間的海明距離是3，表示了兩者對應位置不同位的個數(shù)。其他度量頂點間匹配程度的方法還包括計算頂點間的杰卡德系數(shù)等。

第三類，根據(jù)圖本身的構(gòu)造和屬性特征設計的一些方法。例如，一種度量相似度的方法是利用兩個頂點間獨立于邊（或頂點）的路徑的數(shù)量。獨立路徑之間不共有任何邊（或頂點）。根據(jù)最大流/最小截理論，每條邊只能承載一個流單元，則獨立路徑數(shù)量等于兩個頂點間能夠傳遞的最大流。據(jù)此設計的算法(如增廣路徑算法)能夠在O(m)時間復雜度下計算最大流，m表示圖中邊的數(shù)量。

1.2 Ego角色的探測

復雜網(wǎng)絡分析中，中心度[6]是頂點在圖中重要性的度量，“重要”的具體含義要視具體情況而定，例如社交網(wǎng)絡中的中心人物角色。本文引入EgoNetworks中的概念，將重要頂點命名為ego。目前有四種中心度度量方法被廣泛使用。

(1)Degree Centrality，頂點的度指圖中與頂點相關(guān)聯(lián)的邊的數(shù)量（本文只討論無向圖）。用數(shù)學形式表示為，圖 G的鄰接矩陣 A，若 Aij=1，則存在連接 i和 j的邊；若Aij=0，則 i和 j無連接。 頂點數(shù)為 n時，頂點 i的度 ki：

雖然形式簡單，頂點的度經(jīng)常能有效地衡量頂點的重要性或影響力：在社交網(wǎng)絡中，擁有更多連接邊的角色往往更具影響力。

(2)Eigenvector Centrality，這種中心度量方法的基本思想是：給圖中所有頂點賦予相應的分值。賦分原則是：考慮某一頂點v，v的所有連接邊中，來自高分頂點的連接較來自低分頂點的連接給貢獻更多的分值。谷歌的PageRank算法即是這種度量方法的一個變種。

利用圖的鄰接矩陣計算Eigenvector Centrality：xi表示第i個頂點的分值，則xi與i的所有鄰接頂點的分值的和成正比：

上式中λ是常量。定義中心度的向量形式x=(x1，x2，…)，可以重寫上式為：

可見，x是鄰接矩陣A的特征向量，對應的特征值是λ。一個特征向量往往對應多個特征值，假設中心度值非負，根據(jù)Perron-Frobenius定量，λ則取所有特征值中最大的值，對應的特征向量為x。

(3)Betweenness Centrality，圖中那些位于更多的頂點對之間最短路徑上的頂點擁有更高的介度。頂點v的介度CB(v)：

σst表示 s與 t之間最短路徑的總數(shù)，σst(v)則是這些最短路徑中經(jīng)過頂點v的最短路徑數(shù)量。

(4)Closeness Centrality，定義為頂點v與圖中所有其他可達頂點之間的最短路徑的均值，表示為：

其中n≥2表示由v起始可以到達的網(wǎng)絡中的連接組件V的大小。親近度可以衡量圖中信息由給定的頂點傳播到其他可達頂點所需時間的長短。

1.3 模塊性標準

模塊性標準[7]由Newman等人引進，用以衡量算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)質(zhì)量。復雜網(wǎng)絡G=(V，E)，其中，V為頂點集合，E為邊集合，G包含了n個頂點，k個社區(qū)，定義模塊性：

式中，e是一個k×k維的對稱矩陣，eij表示連接社區(qū) i中角色（即頂點）和社區(qū)j中角色的邊的數(shù)量在邊總數(shù)中所占比例，表示與第i個社區(qū)中角色連接的邊在邊總數(shù)中所占比例。Q值介于0～1之間，Q值越接近1，說明發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)質(zhì)量越高。實際網(wǎng)絡中，Q值一般在0.3～0.7之間。

2 改進的層次聚類算法

用于表示現(xiàn)實網(wǎng)絡系統(tǒng)的復雜網(wǎng)絡通常具有的層次結(jié)構(gòu)特征，即較大的社區(qū)結(jié)構(gòu)包含較小的社區(qū)結(jié)構(gòu)。層次聚類算法能有效地發(fā)現(xiàn)這種層次結(jié)構(gòu)，被廣泛應用于社交網(wǎng)絡分析、生物工程、市場分析等領域。層次聚類算法可以分為兩大類：

(1)凝聚方法：采用自底向上的策略，首先將每個對象作為簇（cluster），然后合并這些原子簇成為更大的簇，直到所有對象都在一個簇中，或者滿足某終止條件。

(2)分裂方法：采用自頂向下的策略，首先將所有對象置于一個簇中，然后逐步細分為越來越小的簇，直到每個對象各為一簇，或滿足某終止條件，例如達到了希望的簇數(shù)或每個簇的直徑都在某個閾值內(nèi)。

由于分裂方法很少使用，本文討論的算法采用自底向上的策略。通?？梢杂脴錉顖D（dendrogram）表示層次聚類的過程，如圖1所示。

層次聚類算法將網(wǎng)絡劃分為幾個社區(qū)取決于在什么位置分割樹狀圖，如圖1中橫線位置將產(chǎn)生兩個社區(qū)結(jié)構(gòu)。實際網(wǎng)絡中通常依據(jù)模塊性標準來確定最佳的劃分位置。

傳統(tǒng)層次聚類算法在確定相似度計算方法后，計算所有頂點對之間的相似度。本文在傳統(tǒng)方法的基礎上，引入ego角色探測過程，根據(jù)復雜網(wǎng)絡具體特征，首先確定相似度計算方法，然后確定ego角色的探測方法，一旦扮演ego角色的頂點被確定，則只計算圖中所有其他頂點與ego頂點之間的相似度，這種情況下，時間復雜度取決于ego探測過程，例如，選定Degree Centrality作為ego探測策略，總的時間復雜度可表示為O(n)?？梢姡诖笠?guī)模網(wǎng)絡分析中，改進的層次聚類算法具有較大優(yōu)勢。算法步驟如下。

該算法可以有兩種應用用途：在較理想的情形下，例如復雜網(wǎng)絡表示的是現(xiàn)實的EgoNetworks，則算法能有效挖掘網(wǎng)絡中的社區(qū)結(jié)構(gòu)；對于準確度要求很高以及復雜網(wǎng)絡規(guī)模巨大、特征不明確的情形，本文算法可作為網(wǎng)絡預處理過程，用于降低網(wǎng)絡分析規(guī)模，此時算法只產(chǎn)生規(guī)模合適的粗糙的社區(qū)，再運用其他準確度較高的算法，劃分出更精確的社區(qū)。

3 實驗分析

3.1 EgoNetworks中的算法應用

該EgoNetworks數(shù)據(jù)采集自社交網(wǎng)站人人網(wǎng)，包含了一個Ego角色和49個alter角色。圖中頂點代表一個個體，邊表示個體之間的好友關(guān)系。由調(diào)查得知，該網(wǎng)絡包含三個同學群體，一個陌生人群體，一個親密好友群體。運用改進的層次聚類算法，成功地挖掘出了網(wǎng)絡中包含的五個社區(qū)，算法采用的相似度計算方法是頂點間海明距離，ego角色在初始狀態(tài)是已知的，第一次迭代后利用Degree Centrality探測新的ego角色。圖2描述了模塊度Q值隨社區(qū)個數(shù)變化的分布圖，x軸表示社區(qū)數(shù)量，y軸表示對應的Q值。

由圖2可見，當Q值取最大0.363時，對應的社區(qū)個數(shù)為5，此時劃分質(zhì)量最高，網(wǎng)絡中社區(qū)結(jié)構(gòu)圖如圖3所示。

3.2 “Zachary空手道俱樂部網(wǎng)絡”中的算法應用

Zachary空手道俱樂部網(wǎng)絡[8]是測試社區(qū)挖掘算法的經(jīng)典網(wǎng)絡，該網(wǎng)絡描述了美國一所大學空手道俱樂部的34名成員之間的關(guān)系，其中包含了兩個已知的社區(qū)結(jié)構(gòu)。圖4的劃分結(jié)果來自Girvan-Newman算法，不同社區(qū)用不同顏色頂點區(qū)分。

本文算法在選定Degree Centrality和海明距離分別作為ego角色探測和相似度計算策略后，劃分結(jié)果如表1所示。

表1中，除了10,12,32,28四個頂點劃分有誤，其他都正確。在這種非EgoNetworks中，根據(jù)網(wǎng)絡特征選取恰當?shù)南嗨贫扔嬎愫蚭go角色探測方法很重要，實驗中選擇了較簡單的方法，雖然在準確性上有不足，但是時間復雜度只有 O(n)，較傳統(tǒng)方法的 O(n2)，在大規(guī)模網(wǎng)絡中，改進的層次聚類算法優(yōu)勢明顯。

表1 改進的層次類聚算法的挖掘結(jié)果

社區(qū)挖掘是復雜網(wǎng)絡分析的重要手段之一。本文總結(jié)了復雜網(wǎng)絡中常用的頂點間相似度計算方法和頂點重要性度量方法，在此基礎上，對傳統(tǒng)的層次聚類算法進行改進，引入網(wǎng)絡中“ego”角色的探測過程，并在現(xiàn)實的EgoNetworks以及經(jīng)典實際網(wǎng)絡中驗證了算法的有效性。雖然改進的層次聚類算法能很好地提高社區(qū)挖掘效率，但是在準確性上仍有不足之處。如何提高算法準確度以及如何根據(jù)具體的網(wǎng)絡特征，制定合適的相似度計算和“ego”角色探測方法是以后研究的主要工作。

[1]GIRVAN M，NEWMAN M E J.Community structure in social and biological networks[C].Proc.Natl.Acad.Sci.USA 99，2002：7821-7826.

[2]Yang Bo,Liu Dayou,Liu Jiming,et al.Complex network clustering algorithms[J].Journal of Software,2009,20(1)：54-66.

[3]FORTUNATO S.Community detection in graphs[C].arXiv：0906.0612，2010.

[4]HANNEMAN R A，RIDDLE M.Introduction to social network methods[M/OL].Riverside，CA：Universityof California，Riverside,2005.http://faculty.ucr.edu/～hanneman/.

[5]ADAMIC L A，ADAR E.Friends and neighbors on the web[J].Social Networks,2007,25(2):211-230.

[6]NEWMAN M E J.Mathematics of networks[M].In The New Palgrave Encyclopedia of Economics,2nd edition.Palgrave Macmillan,Basingstoke,2007.

[7]NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,69,2004.

[8]ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(2):452-473.