復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘——改進(jìn)的層次聚類算法

鄭浩原，黃 戰(zhàn)

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

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

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

1 算法準(zhǔn)備

1.1 相似度計(jì)算

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

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

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

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

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

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

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

1.2 Ego角色的探測(cè)

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

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

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

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

利用圖的鄰接矩陣計(jì)算Eigenvector Centrality：xi表示第i個(gè)頂點(diǎn)的分值，則xi與i的所有鄰接頂點(diǎn)的分值的和成正比：

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

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

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

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

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

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

1.3 模塊性標(biāo)準(zhǔn)

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

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

2 改進(jìn)的層次聚類算法

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

3.1 EgoNetworks中的算法應(yīng)用

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

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

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

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

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

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

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

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

[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.