復(fù)雜網(wǎng)絡(luò)聚類算法綜述

李建 鄭曉艷

摘要：隨著復(fù)雜網(wǎng)絡(luò)應(yīng)用的日益廣泛，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)聚類算法越來越多。這導(dǎo)致在實(shí)際應(yīng)用中根據(jù)實(shí)際的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)選擇合適的聚類算法成為一大難題。針對這種情況，根據(jù)復(fù)雜網(wǎng)絡(luò)聚類算法的求解策略，通過介紹各個經(jīng)典的復(fù)雜網(wǎng)絡(luò)聚類算法的基本原理、實(shí)現(xiàn)步驟以及優(yōu)缺點(diǎn)，對這些算法進(jìn)行歸類和比較，得出了它們對應(yīng)的更好的適用范圍，有助于在復(fù)雜網(wǎng)絡(luò)聚類分析中選取合適的算法解決問題，為相關(guān)領(lǐng)域的研究者提供了參考。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)； 簇結(jié)構(gòu)；聚類

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）05-0037-05

Survey of Complex Network Clustering Algorithms

LI Jian， ZHENG Xiao-yan

（College of Information Technology Engineering， Tianjin University of Technology and Education， Tianjin 300222， China）

Abstract：Complex network clustering algorithms which aim to discover network communities are increasing along with the wide application of complex networks， so it is hard to select the appropriate clustering algorithm based on the actual structure of complex networks in application. In view of this situation， it classifies and compares the classical complex network clustering algorithms through introducing the basic principle， the implement steps， the advantages and disadvantages as well as the solving strategy of the complex network clustering algorithms. Finally， it gets the better scope of application， which is beneficial to selecting the appropriate algorithms for the complex network clustering analysis and providing a reference for researchers.

Key words：complex network； community structure； clustering

近幾年隨著復(fù)雜網(wǎng)絡(luò)的發(fā)展，現(xiàn)實(shí)世界中的各種網(wǎng)絡(luò)大量涌現(xiàn)，許多復(fù)雜系統(tǒng)直接或間接地以復(fù)雜網(wǎng)絡(luò)的形式存在，如社會關(guān)系網(wǎng)、新陳代謝網(wǎng)等。網(wǎng)絡(luò)簇結(jié)構(gòu)（network community structure）是復(fù)雜網(wǎng)絡(luò)最普遍和最重要的拓?fù)浣Y(jié)構(gòu)屬性之一，具有同簇節(jié)點(diǎn)相互連接密集、異簇節(jié)點(diǎn)相互連接稀疏的特點(diǎn)，復(fù)雜網(wǎng)絡(luò)聚類是為了找到復(fù)雜網(wǎng)絡(luò)中真實(shí)存在的全部簇[1]。

研究復(fù)雜網(wǎng)絡(luò)聚類算法有助于挖掘出復(fù)雜網(wǎng)絡(luò)的內(nèi)在規(guī)律、拓?fù)浣Y(jié)構(gòu)、各類功能以及發(fā)展趨勢，具有重要的理論意義和廣闊的應(yīng)用前景。在此背景下，本文概述了各復(fù)雜網(wǎng)絡(luò)聚類算法的基本思想、實(shí)現(xiàn)步驟和優(yōu)缺點(diǎn)。

目前，復(fù)雜網(wǎng)絡(luò)聚類算法有兩種求解方法，第一種是啟發(fā)式方法，將復(fù)雜網(wǎng)絡(luò)聚類問題轉(zhuǎn)化成預(yù)定義啟發(fā)式規(guī)則的設(shè)計問題；第二種是基于優(yōu)化的方法，通過最優(yōu)化預(yù)定義的目標(biāo)函數(shù)來計算復(fù)雜網(wǎng)絡(luò)的簇結(jié)構(gòu)從而將復(fù)雜網(wǎng)絡(luò)聚類問題轉(zhuǎn)化成優(yōu)化問題[2]。

1 啟發(fā)式方法

典型的啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類算法有hyperlink induced topic search（HITS）算法[3]、maximum flow community（MFC）算法[4]、Girvan-Newman（GN）算法[5]及其改進(jìn)、Wu-Huberman（WH）算法[6]、clique percolation method（CPM）算法[7]、finding and extract-ing communities（FEC）算法[8]、基于標(biāo)簽傳播的網(wǎng)絡(luò)聚類算法和基于仿生計算的網(wǎng)絡(luò)聚類算法。以上算法都是利用某種直觀假設(shè)，可快速找到大多數(shù)復(fù)雜網(wǎng)絡(luò)的最優(yōu)解或近似最優(yōu)解，但是卻不能保證對于任意網(wǎng)絡(luò)都可以得出很好的解。

1.1 HITS算法

1999年，Kleinberg等人提出了HITS算法[3]，認(rèn)為web頁面有權(quán)威性（Authority）和樞紐性（Hub），取值依次用 和 表示。HITS算法利用頁面之間的引用鏈來發(fā)現(xiàn)隱含在WWW中的網(wǎng)絡(luò)簇結(jié)構(gòu)，計算簡單且效率高，已被廣泛應(yīng)用。HITS算法的實(shí)現(xiàn)步驟簡述如下：（1）選取根集； （2）構(gòu)造基集； （3）構(gòu)造鄰接圖； （4）迭代得出結(jié)果。

HITS算法雖然能很好地描述Web的組織特點(diǎn)，但易出現(xiàn)主題漂移現(xiàn)象，導(dǎo)致不同的查詢算法要重新運(yùn)行，開銷過大，因此HITS算法不能用于實(shí)時系統(tǒng)。

1.2 MFC算法

2002年，GW.Flake 等人提出了MFC算法[4]，它的提出思想是簇內(nèi)邊的密度遠(yuǎn)遠(yuǎn)大于簇間邊的密度。簇間連接構(gòu)成網(wǎng)絡(luò)“瓶頸”，其容量決定最大流量，可由最小截集計算得出，反復(fù)識別、刪除簇間連接，可以逐漸分離網(wǎng)絡(luò)簇，當(dāng)前計算最小截集最快需要。Flake等人把MFC算法應(yīng)用于基于鏈接的Web網(wǎng)頁聚類研究，為基于主題詞的Web網(wǎng)頁/文本聚類研究開闊了思路。

1.3 GN算法及其改進(jìn)

2002年，Girvan和Newman提出了著名的GN算法[5]。GN算法以簇間連接的邊介數(shù)應(yīng)大于簇內(nèi)連接的邊介數(shù)為啟發(fā)式規(guī)則，不斷刪除邊介數(shù)最大的邊，最終把整個網(wǎng)絡(luò)劃分成若干個網(wǎng)絡(luò)簇[1]。邊介數(shù)定義成， 表示為起點(diǎn)， 作終點(diǎn)的路徑中經(jīng)過的最短路徑的數(shù)量，是網(wǎng)絡(luò)中經(jīng)過的所有最短路徑的數(shù)量。GN算法的實(shí)現(xiàn)步驟簡述如下：（1）計算全部邊的介數(shù)； （2）刪除介數(shù)最大的邊； （3）更新剩余邊的介數(shù)； （4）重復(fù)（2）、（3），直到刪除所有的邊。

通常在聚類數(shù)目已知的情況下應(yīng)用GN算法，該算法最大的缺點(diǎn)是計算速度慢、開銷大，時間復(fù)雜度很高，所以其不適合處理大規(guī)模的網(wǎng)絡(luò)。針對該問題，學(xué)者們對GN算法進(jìn)行改進(jìn)，而后提出了采用節(jié)點(diǎn)集的GN算法和自包含GN算法等。

1.4 WH算法

2004 年，Wu和 Huberman結(jié)合物理學(xué)知識，提出了WH算法[6]，在該算法中，整個網(wǎng)絡(luò)被看作一個電阻網(wǎng)絡(luò)，每條邊被看作一個電阻，位置不同的節(jié)點(diǎn)電位勢不同。選取位于不同簇中的兩個節(jié)點(diǎn)作為正負(fù)極，根據(jù)簇內(nèi)電阻遠(yuǎn)遠(yuǎn)小于簇間電阻得出異簇節(jié)點(diǎn)位勢不同而同簇節(jié)點(diǎn)位勢近似相同[6]。WH算法利用最大位勢差來識別網(wǎng)絡(luò)簇，該過程可在線性時間內(nèi)完成，但是WH算法往往需要大量難以獲取的先驗(yàn)知識。

1.5 CPM算法

復(fù)雜網(wǎng)絡(luò)的快速發(fā)展使更多的研究者投入到重疊網(wǎng)絡(luò)的研究。2005年，Palla等人提出了CPM算法[7]，他們認(rèn)為網(wǎng)絡(luò)簇可以看作由若干重疊的團(tuán)組成，通過搜索相鄰的團(tuán)可檢測網(wǎng)絡(luò)的簇結(jié)構(gòu)。CPM算法的實(shí)現(xiàn)步驟簡述如下：（1）確定參數(shù)，找到復(fù)雜網(wǎng)絡(luò)中所有的-團(tuán)；（2）把每個團(tuán)看作一個頂點(diǎn)，若兩個-團(tuán)共享個節(jié)點(diǎn)，則對應(yīng)的頂點(diǎn)有邊相連，否則無邊相連；（3）構(gòu)建重疊矩陣，計算網(wǎng)絡(luò)簇結(jié)構(gòu)。

雖然CPM算法是首個可以識別重疊網(wǎng)絡(luò)簇結(jié)構(gòu)的算法，但是參數(shù)不同則聚類結(jié)果不同，且參數(shù)不易確定[1]。除此之外，CPM算法的時間復(fù)雜度近似指數(shù)階。

1.6 FEC算法

2007年，Yang等人針對符號網(wǎng)絡(luò)聚類問題，在Markov隨機(jī)游走理論的基礎(chǔ)上提出了FEC算法[8]，符號網(wǎng)絡(luò)包含正、負(fù)兩種關(guān)系，在復(fù)雜系統(tǒng)中普遍存在。FEC算法的基本假設(shè)是：如果從網(wǎng)絡(luò)中任意一個簇出發(fā)進(jìn)行隨機(jī)游走，結(jié)果到達(dá)起始簇內(nèi)節(jié)點(diǎn)的概率應(yīng)大于到達(dá)剩余簇中節(jié)點(diǎn)的概率[9]。在此基礎(chǔ)上，F(xiàn)EC算法的實(shí)現(xiàn)步驟簡述如下：（1）任選目的節(jié)點(diǎn)，計算其步轉(zhuǎn)移概率分布；（2）將與所有節(jié)點(diǎn)相對應(yīng)值按降序排序，尋找使截函數(shù)（Cut Criterion）最大的二分分裂點(diǎn)；（3）若算法已滿足基于截函數(shù)的終止條件，遞歸結(jié)束；否則，按分裂點(diǎn)把當(dāng)前網(wǎng)絡(luò)分成兩個子網(wǎng)絡(luò)，遞歸執(zhí)行上述步驟。

隨機(jī)游走步長是FEC算法唯一的參數(shù)，其取值影響聚類，經(jīng)驗(yàn)取值區(qū)間是[6， 20]。FEC算法較好的精度和時間性能使其適用于簇結(jié)構(gòu)模糊和噪聲高的復(fù)雜網(wǎng)絡(luò)，但該算法沒有從理論上給出設(shè)置[l]的通用方法。

1.7 基于標(biāo)簽傳播的網(wǎng)絡(luò)聚類算法

2002年，Zhu等人提出了LPA算法[10]，其使用已被標(biāo)記的節(jié)點(diǎn)標(biāo)簽信息來預(yù)測未被標(biāo)記的節(jié)點(diǎn)標(biāo)簽信息。LPA算法的實(shí)現(xiàn)步驟簡述如下[11]：（1）構(gòu)造邊權(quán)重矩陣，得出數(shù)據(jù)之間的相似度；（2）計算節(jié)點(diǎn)之間的傳播概率；（3）定義標(biāo)注矩陣；（4）根據(jù)（2）、（3）更新概率分布；（5）更新初始矩陣，重復(fù)（4），直到收斂。

2007年，Raghavan等人提出RAK算法[12]，第一次把LPA的思想應(yīng)用到復(fù)雜網(wǎng)絡(luò)聚類中。

2009年，Leung等人[13]通過研究發(fā)現(xiàn)LPA算法有很大潛力處理大規(guī)模網(wǎng)絡(luò)的聚類問題。

2009年，Barber對LPA算法的目標(biāo)函數(shù)進(jìn)行修正，提出了帶約束的LPAm算法[14]，改善了LPA算法的聚類性能。

2010年，Liu等人考慮到LPAm算法易陷入局部最優(yōu)解，在層次貪婪算法MSG和LPAm算法的基礎(chǔ)上，提出了LPAm+算法[15]，進(jìn)一步改善了標(biāo)簽傳播類算法的聚類性能。

1.8 基于仿生計算的網(wǎng)絡(luò)聚類算法

2007年，Liu等人在研究螞蟻行為的基礎(chǔ)上提出了蟻群聚類算法[16]，該算法應(yīng)用于郵件社會網(wǎng)絡(luò)。

2010年，劉大有等人在Markov隨機(jī)游走的基礎(chǔ)上提出了RWACO算法[17]，之后對RWACO算法進(jìn)行了改進(jìn)。

2011年，公茂果等人提出了密母算法[18]，該算法可以有效探測網(wǎng)絡(luò)中的層次簇結(jié)構(gòu)。

2012年，何東曉等人提出多層蟻群算法（MABA算法）[19]，該算法可發(fā)現(xiàn)網(wǎng)絡(luò)中的層次簇結(jié)構(gòu)，其實(shí)現(xiàn)步驟簡述如下：（1）運(yùn)行其子算法，發(fā)現(xiàn)網(wǎng)絡(luò)簇結(jié)構(gòu)；（2）把簇看作節(jié)點(diǎn)，簇間鏈接看作加權(quán)邊，構(gòu)建上層網(wǎng)絡(luò)，并將子算法用于此網(wǎng)絡(luò)；（3）重復(fù)以上步驟，直到模塊度函數(shù)不再增加。

2 基于優(yōu)化的算法

在基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類算法中，兩種經(jīng)典的代表算法是譜聚類算法和局部搜索算法。

2.1 譜聚類算法

譜聚類算法基于譜圖理論，把各個樣本數(shù)據(jù)視為頂點(diǎn)，通過利用數(shù)據(jù)之間的相似度給點(diǎn)之間的邊賦權(quán)值得到一個無向加權(quán)圖，如此把聚類的問題轉(zhuǎn)化成對圖的劃分問題。其劃分準(zhǔn)則是使子圖內(nèi)部的相似度最大、子圖之間的相似度最小[20]。常見的劃分準(zhǔn)則有Mini cut、Average cut、Normalized cut、Min-max cut、Ratio cut和MNcut等。根據(jù)不同的準(zhǔn)則函數(shù)及譜映射方法，譜聚類算法可以分為二路譜聚類算法和多路譜聚類算法。

經(jīng)典的二路譜聚類算法有Freeman和Peron提出的PF算法[21]、Shi和Malik提出的SM 算法[20]、Scott和Languet Higgins提出的SLH算法[22]、Kannan R和Vempala S提出的KVV算法[23]以及Ding提出的Mcut算法[24]。經(jīng)典的多路譜聚類算法有Ng，Jordan等人提出的NJW算法[25]以及Meila提出的MS算法[26]。上述典型算法的比較，如表1所示。這些算法的實(shí)現(xiàn)步驟都可用以下三個重要步驟表示：（1）構(gòu)建表示樣本集的矩陣[Z]；（2）計算[Z]的前個特征值與特征向量，構(gòu)建特征向量空間；（3）利用經(jīng)典的聚類算法對特征向量進(jìn)行聚類。

譜聚類算法可發(fā)現(xiàn)不規(guī)則形狀的網(wǎng)絡(luò)簇，應(yīng)用于各種形狀的樣本空間，且結(jié)果收斂于全局最優(yōu)解。近幾年譜聚類算法的研究雖有了一定的成果，但仍有以下需要解決的問題：（1）如何構(gòu)造相似矩陣[W]；（2）如何處理特征向量；（3）如何自動確定聚類數(shù)目；（4）如何選取Laplacian矩陣；（5）如何運(yùn)用到大規(guī)模學(xué)習(xí)問題中。

2.2 局部搜索算法

目前，比較經(jīng)典的基于局部搜索優(yōu)化技術(shù)的復(fù)雜網(wǎng)絡(luò)聚類算法有Kernighan-Lin（KL）算法[27]、快速Newman（FN）算法[28]、Guimera-Amaral（GA）算法[29]、Fast Unfolding Algorith-m（FUA）[30]和Fast Network Clustering Algorithm（FNCA）[17]。

2.2.1 KL算法

1970 年，Kernighan和Lin提出KL算法[27]，該算法是一種基于貪婪思想的優(yōu)化算法，其基本思想是引入增益函數(shù)，表示簇內(nèi)與簇間連接數(shù)目的差值，將網(wǎng)絡(luò)劃分成給定大小的兩個簇，交換滿足條件的不同簇間的節(jié)點(diǎn)對，使得簇間連接最稀疏，簇內(nèi)連接最緊密，即使得值最大。使用KL算法必須事先知道簇的節(jié)點(diǎn)數(shù)量，否則不能進(jìn)行正確地聚類，這是KL算法最大的局限性。除此之外，KL算法得出的解通常是局部最優(yōu)解。

2.2.2 FN算法

2004年，Girvan和Newman提出網(wǎng)絡(luò)模塊度函數(shù)，定量地描述網(wǎng)絡(luò)簇結(jié)構(gòu)的優(yōu)劣。函數(shù)定義為簇內(nèi)實(shí)際連接數(shù)目與隨機(jī)連接情況下簇內(nèi)期望連接數(shù)目之差[31]。同年，Newman提出以極大化函數(shù)作為優(yōu)化目標(biāo)的FN算法[28]。FN算法的實(shí)現(xiàn)步驟簡述如下：（1）初始化每個節(jié)點(diǎn)為獨(dú)立的簇，模塊度；（2）按序合并有邊連接的簇對，計算并使每次合并沿著最小或最大的方向執(zhí)行；（3）更新

FUA算法

2008年，Blondel等人基于局部優(yōu)化和層次聚類提出了FUA算法[30]，該算法的計算時間優(yōu)于其他大多數(shù)的網(wǎng)絡(luò)聚類算法，尤其對于稀疏網(wǎng)絡(luò)，其時間復(fù)雜度為。除此之外，以模塊度函數(shù)衡量聚類結(jié)果，該算法聚類結(jié)果的質(zhì)量和準(zhǔn)確性都表現(xiàn)的很好，被評定為當(dāng)前性能最佳的模塊性優(yōu)化算法。FUA算法的實(shí)現(xiàn)步驟簡述如下：（1）把每個節(jié)點(diǎn)看作一個簇；（2）將各個節(jié)點(diǎn)移至它的鄰節(jié)點(diǎn)所在的簇中，計算函數(shù)的增量；（3）把每個簇看作一個超級節(jié)點(diǎn)，簇間的鏈接看作加權(quán)邊，構(gòu)建上層網(wǎng)絡(luò)；（4）重復(fù)以上過程，直到函數(shù)不再增加。

FNCA算法

2011年，劉大有等人提出了FNCA 算法[17]。他們在模塊度函數(shù)的基礎(chǔ)上，得出了局部目標(biāo)函數(shù)。FNCA算法的實(shí)現(xiàn)步驟簡述如下：（1）給每個節(jié)點(diǎn)定義一個簇；（2）對所有節(jié)點(diǎn)隨機(jī)排序；（3）每個節(jié)點(diǎn)對其所有鄰居節(jié)點(diǎn)標(biāo)簽來計算對應(yīng)的值，將使其值最大的標(biāo)簽作為自身標(biāo)簽；（4）迭代運(yùn)行次，算法結(jié)束。該算法聚類質(zhì)量好且運(yùn)行效率高，適合應(yīng)用于分布式網(wǎng)絡(luò)聚類。

2.2.3 基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類算法的分析

基于優(yōu)化的網(wǎng)絡(luò)聚類算法還有很多，這些算法的優(yōu)化目標(biāo)大多是最大化函數(shù)，研究發(fā)現(xiàn)函數(shù)是有偏的，導(dǎo)致得出的網(wǎng)絡(luò)簇結(jié)構(gòu)和真實(shí)的網(wǎng)絡(luò)簇結(jié)構(gòu)存在偏差，因此這些算法往往并不能準(zhǔn)確地識別出真實(shí)存在的網(wǎng)絡(luò)簇結(jié)構(gòu)。

3 其他復(fù)雜網(wǎng)絡(luò)聚類算法

除上述主要的網(wǎng)絡(luò)聚類算法外，還有其他的網(wǎng)絡(luò)聚類算法。如Gudkov等人提出的基于動力學(xué)的演化算法[32]；Bagrow和Bollt提出的局部聚類算法—L-shell算法[33]；Papadopoulos等人提出的和L-shell算法相似的橋邊界算法等[34]。

4 結(jié)束語

本文主要對幾個經(jīng)典的復(fù)雜網(wǎng)絡(luò)聚類算法進(jìn)行了綜述，介紹了它們的基本原理、實(shí)現(xiàn)步驟以及優(yōu)缺點(diǎn)?，F(xiàn)將上述典型的復(fù)雜網(wǎng)絡(luò)聚類算法的性能做比較如表2所示，其中表示網(wǎng)絡(luò)連接數(shù)， 為節(jié)點(diǎn)數(shù)， 為節(jié)點(diǎn)的平均度，為聚類結(jié)果的平均簇規(guī)模。

盡管復(fù)雜網(wǎng)絡(luò)聚類算法已經(jīng)取得了一些成果，但是還有一些需要解決的問題，如：（1）關(guān)于網(wǎng)絡(luò)簇結(jié)構(gòu)，目前還沒有一個明確客觀的定義，只能借助目標(biāo)函數(shù)或啟發(fā)式規(guī)則識別網(wǎng)絡(luò)簇結(jié)構(gòu)。這樣會使刻畫的網(wǎng)絡(luò)簇結(jié)構(gòu)與真實(shí)存在的網(wǎng)絡(luò)簇結(jié)構(gòu)存在一定的偏差，因此，我們亟待解決的問題之一是能否以復(fù)雜網(wǎng)絡(luò)的自身屬性為依據(jù)，得出一個明確客觀的理論來刻畫復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)。（2）簇結(jié)構(gòu)具有重疊性和層次性，它們之間存在“沖突”，大部分算法只能解決一方面。（3）現(xiàn)有的聚類算法都有一定的限制，不能同時具有效率高、不依賴先驗(yàn)知識、對參數(shù)不敏感、聚類結(jié)果精確且適用于大規(guī)模數(shù)據(jù)集等優(yōu)點(diǎn)。因此，我們需要研究出一種復(fù)雜網(wǎng)絡(luò)聚類算法，該算法能夠在沒有先驗(yàn)知識的條件下快速刻畫出真實(shí)的網(wǎng)絡(luò)簇結(jié)構(gòu)。

參考文獻(xiàn)：

[1] 楊博，劉大有.復(fù)雜網(wǎng)絡(luò)聚類方法[J].軟件學(xué)報，2009，20（1）：54-66.

[2] 周斌，程慧.基于貪婪算法的符號網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)快速發(fā)現(xiàn)算法[J].大眾科技，2009，（12）：48-49.

[3] Kleinberg JM.Authoritative sources in a hyperlinked environment[J].Journal of the ACM，1999，46（5）：604-632.

[4] Flake GW，Lawrence S，Giles CL，et al.Self-Organizationand identification of Web communiti-es[J].IEEE Computer，2002，35（3）：66-71.

[5] Girvan M，Newman MEJ.Community structure in socialland biological networks[J].Proc.of the National Academy of Science，2002，9（12）：7821-7826.

[6] Wu F，Huberman BA.Finding communities in linear time：A physics approach[J].European Phy-sical Journal B，2004，38（2）：331-338.

[7] Palla G，Derenyi I，F(xiàn)arkas I，et al.Uncovering the overlapping community structures of com-plex networks in nature and society[J].Nature，2005，435（7043）：814-818.

[8] Yang B，Cheung W K，Liu J.Community mining from signed social networks[J].IEEE Trans.on Kn-owledge and Data Engineering，2007，19（10）：1333-1348.

[9] 陳登峰.多屬性無向加權(quán)圖上的聚類方法研究[D].黑龍江：黑龍江大學(xué)，2011.

[10] Zhu Xiao-Jin，Ghanramani Z.Learning from labeled and unlabeled data with label propagati-on [R].Pittsburghers：Carnegie Mellon U-niversity，2002.

[11] 羅秋濱.標(biāo)簽傳播算法在社會網(wǎng)絡(luò)中的應(yīng)用研究[J].智能計算機(jī)與應(yīng)用，2013（3）：37-43.

[12] Rahavan U N，Albert R，Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E，2007，76（3）：036106.

[13] Leung I X Y，Hui P，Liò P，et al.Towards real time community detection in large networks[J].Physical Review E，2009，79（6）：066107.

[14] Barber M J，Clark J W.Detecting network communitiesby propagating labels under constrain-ts[J].Physical Review E，2009，80（2），026129.

[15] Liu X，Murata T.Advanced modularity-specialized labelpropagateon algorithm for detecting communities in networks[J].Physica A，2010，389（7）：1493-1500.

[16] Liu Y，Wang Q X，Wang Q，et al.Email community detection using artificial ant colony clust-ering[C]//Proc of Joint the 9th Asia-Pacific Web Conf and the 8th Int Conf on Web-Age Information Management Workshops.Berlin：Springer，2007，287-298.

[17] 金弟，楊博，劉杰，等.復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)探測—基于隨機(jī)游走的蟻群算法[J].軟件學(xué)報，2012，23（3）：451-464.

[18] Gong M，F(xiàn)u B，Jiao L，Memetic algorithm for community detection in networks[J].Physical Re-view E，2011，84（5）：056101.

[19] He D，Liu J，Liu D，et al.An ant-based algorithm with local optimization for community det-ection in large-scale networks[J].advances in Complex Systems，2012，15（8）：1250036-1-26.

[20] Shi J，Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern An-alysis and Machine Intelligence，2000，22（8）：888-905.

[21] Perona P，F(xiàn)reeman W T.A factorization approach to grouping[C].In 5th European Conf on C-omputer Vision Proceedings，1998，1：665-670.

[22] Scott G L，Longuet-Higgins H C.Feature grouping by relocalization of eigenvectors of theproximity matrix[C].Proc.British Machine Vision Conference.1990：103-108.

[23] Kannan R，Vempala S，Vetta A.On clusterings：good，badand spectra1[J].Journal of ACM，2004，51（3），497-515.

[24] Ding C，He X F，Zha H Y，et a1.A min-max cut algorithm for graph partitioning and data clu-stering[C]//Proceedings of IEEE International Conference on Data mining.San Jose：IEEE，2001：107-114.

[25] Ng A Y，Jordan M I，Weiss Y.On spectral clustering： Analysis and an algorithm[J].Proceedi-ngs of Advancesin Neural Information Processing Systems.Cambridge，MA：MIT Press，2002，14：849-856.

[26] Meila M，Shi J.Learning segmentation by random wal-ks[C]//Advancesin Neural Information Processing Systems，Cambridge，2000：873-879.

[27] Newman MEJ.Detecting community structure in networks[J].European Physical Journal B，2004，38（2）：321-330.

[28] Newman MEJ.Fast algorithm for detecting communitystructure in networks [J].Physical Rev-iew E，2004，69（6）：066133.

[29] Guimera R，Amaral LAN.Functional cartography of complex metabolic networks[J].Nature，2005，433（7028）：895?900.

[30] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large netw-orks[J].Journal of Statistical Mechanics：Theory and Experiment，2008，（10）：10008.

[31] Newman MEJ，Girvan M.Finding and evaluating community structure in networks[J].Physical Review E，2004，69（2）：026113.

[32] Gudkov V，Montealegre V，Nussinov S，et al.Communitydetection in complex networks by dynam-ical simplexevolution[J].Physical Review E.2008，78（1）：016113.

[33] Bagrow J P，Bollt E M.Local method for detecting communities[J].Physical Review E，2005，72（4）：046108.

[34] Symeon Papadopoulos AS，Yiannis Kompatsiaris，Athena Vakali，etal.Bridge bounding a local approach for efficient community discovery in complex networks[J].Physics and Society，2009.