基于局部聚合的復(fù)雜網(wǎng)絡(luò)自動聚簇算法

湯 蓉，唐常杰，徐開闊，楊 寧

(1. 成都信息工程學(xué)院計算機學(xué)院 成都 610225; 2. 四川大學(xué)計算機學(xué)院 成都 610065)

現(xiàn)實世界中的諸多系統(tǒng)均可建模為復(fù)雜網(wǎng)絡(luò)(complex network)，如：WWW萬維網(wǎng)、人際關(guān)系網(wǎng)、流行病傳播網(wǎng)等。系統(tǒng)中的實體(entity)由節(jié)點(node)表示，而實體之間的關(guān)聯(lián)(interaction/relation)由邊(edge)表示，節(jié)點集和邊集構(gòu)成了復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)(network community/cluster structure)是描述復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的重要特性之一，具有社區(qū)內(nèi)部節(jié)點連接緊密而社區(qū)之間連接相對疏松的特點[1]。隨著計算機技術(shù)的發(fā)展，可得到的數(shù)據(jù)規(guī)模越來越大，從規(guī)模巨大的網(wǎng)絡(luò)數(shù)據(jù)中發(fā)現(xiàn)社區(qū)結(jié)構(gòu)從而挖掘網(wǎng)絡(luò)中隱藏的規(guī)律已變得越來越重要。

迄今為止，研究者們提出了諸多不同的發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的方法[1-6]，如：文獻(xiàn)[5]提出的快速啟發(fā)式算法，文獻(xiàn)[6]提出的基于子圖相似度的貪婪聚簇算法等，其中大部分為全局聚簇(global clustering)算法。很多文獻(xiàn)中使用的快速隨機遞歸搜索算法(fast stochastic and recursive search algorithm)[3-4,7-8]，根據(jù)特定的全局模塊性，如：Q函數(shù)(modularity)[2]和網(wǎng)絡(luò)最短描述長度(network minimum description length,NMDL)等[3-4]，利用全局信息(global information)，對所有的點和邊同時展開搜索從而揭示網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，導(dǎo)致聚簇時間和空間消耗偏高。因全局聚簇需預(yù)先掌握網(wǎng)絡(luò)的全局連接信息，有些還需預(yù)知簇數(shù)，使其對于動態(tài)網(wǎng)絡(luò)和大型網(wǎng)絡(luò)具有局限性。

文獻(xiàn)[7]首先提出了局部簇(local cluster)和局部模塊性(local modularity)的概念，并基于最大化局部模塊性提出了局部聚簇(local clustering)算法[7]。隨后研究者們又提出了其他局部模塊性定義，包括：Outwardness(OW)[9]、 ModularityM(MM)[10]和LMetric(LMe)[11]等。因局部聚簇?zé)o需全局信息，通過計算單個簇的模塊性搜索局部簇，特別適應(yīng)于動態(tài)網(wǎng)絡(luò)和大型網(wǎng)絡(luò)的已知區(qū)域。

針對全局聚簇算法空間和時間消耗偏高的缺陷，本文基于局部聚簇提出了一種兩段式(two-phase)的復(fù)雜網(wǎng)絡(luò)自動聚簇算法(local agglomeration and iterative clustering algorithm, LAICA)。該算法分為兩個階段：局部聚合(local agglomeration)階段和局部簇迭代聚簇(iteratively clustering of local clusters)階段。第一階段通過局部聚簇發(fā)現(xiàn)網(wǎng)絡(luò)中局部密集的節(jié)點集，獲得由局部簇構(gòu)成的復(fù)雜網(wǎng)絡(luò)局部簇結(jié)構(gòu)；第二階段通過迭代式全局聚簇網(wǎng)絡(luò)的局部簇結(jié)構(gòu)自動解析網(wǎng)絡(luò)的最優(yōu)社區(qū)結(jié)構(gòu)。本文選擇了4種局部模塊性作為局部簇搜索的評價標(biāo)準(zhǔn)；因Q函數(shù)存在分辨極限[12]，全局模塊性則采用基于信息論的網(wǎng)絡(luò)最短描述長度—Map Equation(ME, 映射方程式)[4]。使用多個真實網(wǎng)絡(luò)對LAICA算法進(jìn)行了聚簇實驗，兩個階段中不同的局部模塊性和全局模塊性的結(jié)合使用，使LAICA算法表現(xiàn)的聚簇性能不同。和其他全局聚簇算法比較，LAICA算法的聚簇?zé)o需所有節(jié)點參與，僅從一組初始節(jié)點開始發(fā)現(xiàn)局部簇；對局部簇的迭代聚合，使算法能夠自動解析網(wǎng)絡(luò)的社區(qū)數(shù)量，并同時精確地將節(jié)點分配至其所屬社區(qū)。實驗的聚簇精度(NM I值)最高達(dá)99.72%，表明LAICA是一個精確的復(fù)雜網(wǎng)絡(luò)自動聚簇算法。

1 復(fù)雜網(wǎng)絡(luò)聚簇基本概念

復(fù)雜網(wǎng)絡(luò)可建模為圖：X = (V，E), 其中：X為復(fù)雜網(wǎng)絡(luò)，V為節(jié)點集，E為邊集。復(fù)雜網(wǎng)絡(luò)中局部連接緊密的節(jié)點集形成了網(wǎng)絡(luò)的社區(qū)(community/cluster)。設(shè)X包含n個節(jié)點且分布于m個社區(qū)中，形成了X特定的社區(qū)結(jié)構(gòu)：M = {M1, M2,…,Mi,…, Mm}，其中：Mi(1≤i≤m)為X的任一社區(qū)且Mi∈V。

1.1 局部簇結(jié)構(gòu)模型

從單個節(jié)點出發(fā)，利用該節(jié)點的連接信息所發(fā)現(xiàn)的局部密集的節(jié)點集，稱為復(fù)雜網(wǎng)絡(luò)的局部簇[7]。局部簇Mi的節(jié)點集如圖1所示。局部簇中所有節(jié)點構(gòu)成其成員節(jié)點集(member nodes)，以Mi表示。成員節(jié)點又可分為兩個子集：邊界成員節(jié)點集(boundary nodes, Bi)和核心成員節(jié)點集(core nodes, Ci)，即：Mi= CiUBi，其中：邊界成員節(jié)點至少存在一條邊與簇外節(jié)點相連，而核心成員節(jié)點僅與簇內(nèi)成員節(jié)點相連。Mi的簇外節(jié)點，如果至少存在一條邊與Mi的成員節(jié)點相連，則為Mi的鄰居節(jié)點，Mi的鄰居節(jié)點集(shell nodes)以Si表示。連接不同節(jié)點集之間的邊形成了不同的邊集，包括：內(nèi)邊集(inlinks)、外邊集(outlinks)/邊界外邊集(outlinks/Boutlinks)和邊界內(nèi)邊集(boundary inlinks, Binlink)，其中：內(nèi)邊為連接Mi成員節(jié)點之間的邊；外邊(也稱為邊界外邊)為Mi的邊界成員節(jié)點與鄰居節(jié)點之間的邊。邊界內(nèi)邊集和邊界外邊集的并集稱之為邊界邊集，即：與邊界成員節(jié)點相連的所有邊的集合[11]。

圖1 局部簇Mi的節(jié)點集

1.2 局部模塊性

局部聚簇的基本思路如下：選擇初始節(jié)點vi，以vi建立初始局部簇Mi；搜索最大化Mi局部模塊性變化值的鄰居節(jié)點聚合到Mi中，更新Mi的成員節(jié)點集和鄰居節(jié)點集；直到Mi不再存在能改善其局部模塊性的鄰居節(jié)點，則停止對局部簇Mi的搜索和擴展[7]。如表1所示，以下4種不同的局部模塊性：Local Modularity(LM)[7]、 ModularityM(MM)[10]、 Lmetric(LMe)[11]和Outwardness(OW)[9]，均利用社區(qū)結(jié)構(gòu)中社區(qū)內(nèi)連接緊密而社區(qū)間連接疏松的特點，以簇內(nèi)連接與簇外連接之間的比值或差值來表示局部簇的局部模塊性；但卻采用局部簇的不同屬性值來量化簇內(nèi)連接與簇外連接。其中：LM、MM和LMe均采用簇內(nèi)連接與簇外連接之間的比值表示局部模塊性，但OW定義的不是局部簇Mi的模塊性，而是Mi的單個鄰居節(jié)點連接簇內(nèi)與簇外節(jié)點的邊數(shù)之差。

表1 局部模塊性評價標(biāo)準(zhǔn)的定義和計算公式

2 基于局部聚合與迭代的自動聚簇

LAICA算法分為兩個階段：局部聚合階段和局部簇迭代聚合階段。LAICA算法引入針對網(wǎng)絡(luò)聚簇問題的概念：子簇網(wǎng)絡(luò)結(jié)構(gòu)。

2.1 局部聚合算法

以每一個初始節(jié)點vi為首個成員建立初始局部簇Mi，然后逐步聚合最大化Mi局部模塊性的鄰居節(jié)點，直到Mi不再存在鄰居節(jié)點能改善其局部模塊性，則停止對Mi的搜索。當(dāng)Mi不存在鄰居節(jié)點能改善其局部模塊性時，稱Mi不可再擴展(un-expandable)。對于復(fù)雜網(wǎng)絡(luò)X，如果其所有局部簇都不可再擴展或其所有節(jié)點均已聚合到局部簇中，則稱X不可再擴展，此時停止搜索并輸出所得到的X的局部簇網(wǎng)絡(luò)結(jié)構(gòu)，如算法1所示。

2.2 局部簇迭代合并算法

通過局部聚簇X￠到一組局部簇。所有局部簇和未被聚合到局部簇的其他節(jié)點則構(gòu)成了X￠的局部簇網(wǎng)絡(luò)結(jié)構(gòu)X￠，其中每一個局部簇或節(jié)點均為X￠的聚簇單元(clustering unit)。局部簇迭代合并算法(iteratively clustering of local clusters, ICLC)通過最大化X￠的全局模塊性，迭代合并(iteratively merge)X￠的聚簇單元從而搜索X的最優(yōu)社區(qū)結(jié)構(gòu)。

2.1.1 全局模塊性

Q函數(shù)[2]已被文獻(xiàn)廣泛使用。而Map Equation是根據(jù)香農(nóng)的源編碼理論(source coding theorem)[14]提出的另一種全局模塊性[4]。設(shè)復(fù)雜網(wǎng)絡(luò)X包含n個節(jié)點和l條邊，且其節(jié)點分布在m個簇中，M表示包含該m個簇的特定社區(qū)結(jié)構(gòu)，Q函數(shù)和ME的定義和計算公式分別如下：

1) Network Modularity(Q函數(shù))

Q函數(shù)為社區(qū)內(nèi)實際連接數(shù)目與隨機連接情況下社區(qū)內(nèi)期望連接數(shù)目之差，如式(1)所示，式中：i表示第i個社區(qū)，lii為第i個社區(qū)的邊數(shù)，di為第i個社區(qū)節(jié)點的總度數(shù)(degree)。對于特定社區(qū)結(jié)構(gòu)M，Q值越大，則M的網(wǎng)絡(luò)模塊度越強：

2) Map Equation(ME, 映射方程式)

以L(M)表示社區(qū)結(jié)構(gòu)M的ME值。對于無向網(wǎng)絡(luò)，L(M)的定義如式(2)所示，式(2)中參數(shù)含義及計算公式參考文獻(xiàn)[4]。對于特定社區(qū)結(jié)構(gòu)M，L(M)的值越小，則M的網(wǎng)絡(luò)模塊度越強，能更精確描述網(wǎng)絡(luò)的社團結(jié)構(gòu)[4]。

2.1.2 局部簇迭代合并

定義每一個聚簇單元中節(jié)點的數(shù)量為聚簇單元的長度(length)。迭代聚簇的每一步，均選擇X￠中長度最短的聚簇單元Umin，通過計算Umin與每一個鄰居單元合并后X￠的全局模塊性變化值：DME。選擇最大化DME的鄰居單元與Umin聚合。直到X￠的小于某一個閾值e，即：DME，則終止迭代合并，并輸出所獲得的社區(qū)結(jié)構(gòu)，如算法2所示。

2.3 算法復(fù)雜度分析

首先分別對算法兩個階段的復(fù)雜度進(jìn)行分析。設(shè)m￠為局部簇個數(shù)(m￠

1) 局部聚合算法(LAA)的復(fù)雜度

對于LAA算法，ModularityM、LMetric和LocalModularity的復(fù)雜度均為O(k2d)[7,11,13]。對于真實網(wǎng)絡(luò)，添加新節(jié)點的時間消耗決定了局部簇搜索的復(fù)雜度為O(k)[7,11,13]。

因outwardness僅需在局部簇的鄰居節(jié)點中搜索outwardness值最大的節(jié)點v，且當(dāng)v聚合到局部簇時，僅v的簇外鄰居節(jié)點發(fā)生變化，所以聚合時僅需更新v的簇外鄰居節(jié)點的outwardness值。因為在v和每一個鄰居節(jié)點之間有且僅有一條邊，所以對于每一個簇外鄰居節(jié)點：Δoutwardness = -2/k (k為v的鄰居節(jié)點的度數(shù))。最大化outwardness的復(fù)雜度為O(kd2log|B|)，而對于稀疏網(wǎng)絡(luò)，則為O(k log|k|)[9]。

2) 子簇迭代合并算法(ICSC)的復(fù)雜度

ICSC算法中，每一步選擇長度最小的子簇，通過計算其與每一個鄰居子簇合并后網(wǎng)絡(luò)全局模塊性的變化值：ΔGlobalMod，搜索能最大化ΔglobalMod的合并單元。根據(jù)式(2)，因為是一個常量，所以，ΔGlobalMod的計算可分解為3部分：

式中：Δvalue1、Δvalue2和Δvalue3的計算分別如式(3)～(5)所示。設(shè)參與合并的兩個子簇為Mj和Mk，Mj和Mk合并后產(chǎn)生的子簇為Mjk，根據(jù)公式，每一次合并僅需通過合并前的參數(shù)值重新計算子簇Mjk的wjk和wjkD。所以，每一次合并的復(fù)雜度為O(kd)。對于有k個節(jié)點的復(fù)雜網(wǎng)絡(luò)，ICSC算法的復(fù)雜度為O(k2d)。

綜上所述，LAICA算法的復(fù)雜度為O(k2d)。

3 實 驗

為了驗證LAICA算法的有效性和可行性，使用Zachary空手道俱樂部網(wǎng)絡(luò)(Zachary karate club network)[15]、多學(xué)科網(wǎng)絡(luò)(multi-discipline network)[3]和美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)(American college football network)[16]等多個真實網(wǎng)絡(luò)進(jìn)行聚簇實驗。文獻(xiàn)[17]提出范化互信息(normalized mutual information,NM I)計算聚簇所得社區(qū)結(jié)構(gòu)和真實社區(qū)結(jié)構(gòu)的相似程度，本文也采用NM I作為聚簇精度對LAICA算法進(jìn)行了定量分析與評估。實驗采用兩種參數(shù)產(chǎn)生初始節(jié)點：并比較這兩種參數(shù)設(shè)置下LAICA的聚簇精度，其中：Dn0=0時所選擇的初始節(jié)點即為網(wǎng)絡(luò)中度數(shù)最高的節(jié)點。實驗所獲社區(qū)結(jié)構(gòu)將與文獻(xiàn)[4]中算法所獲社區(qū)結(jié)構(gòu)進(jìn)行比較。

3.1 Zachary空手道俱樂部網(wǎng)絡(luò)

Zachary空手道俱樂部網(wǎng)絡(luò)[15]由34個節(jié)點和78條邊構(gòu)成，其中：節(jié)點代表俱樂部成員、邊代表成員之間的社會交往。因意見分歧，俱樂部分裂成以俱樂部管理者和俱樂部教練為中心的兩個子俱樂部。此網(wǎng)絡(luò)標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)的ME值為4.409 3，而文獻(xiàn)[4]中算法發(fā)現(xiàn)的最佳社區(qū)結(jié)構(gòu)ME值為4.311 8。

表2 空手道俱樂部網(wǎng)絡(luò)的avgNM I統(tǒng)計

表2統(tǒng)計了采用不同的局部模塊性和全局模塊性聚簇空手道俱樂部網(wǎng)絡(luò)的平均NM I值(AvgNM I)。當(dāng)Dn0=0時，ME和Modularity兩種全局模塊性中，LMe、LM和MM均分別獲得了完全一致的AvgNM I值，其中：ME的AvgNM I值為0.991 6，而Modularity的AvgNM I值僅為0.342 7。當(dāng)時，不同的局部模塊性和全局模塊性的結(jié)合所獲AvgNM I值均高于90%。整體而言，在兩種初始節(jié)點選擇參數(shù)設(shè)置下，ME的聚簇精度高于Modularity。圖2為初始節(jié)點數(shù)從12到32，4種局部模塊性的AvgNM I曲線圖。

圖2 空手道俱樂部網(wǎng)絡(luò)不同初始節(jié)點數(shù)的AvgNM I

3.2 多學(xué)科網(wǎng)絡(luò)

多學(xué)科網(wǎng)絡(luò)(multi-discipline network)[3]以節(jié)點表示期刊、邊表示引用關(guān)系。如果一個期刊的某篇論文引用了另一期刊的某篇論文，則構(gòu)成了兩個期刊之間的一個引用關(guān)系。網(wǎng)絡(luò)包含4個領(lǐng)域：multidisciplinary physics、chem istry、bioloegy和ecology，每一個領(lǐng)域為一個社區(qū)。每一個領(lǐng)域選取10個期刊共40個期刊作為節(jié)點，期刊之間的189個引用關(guān)系作為邊。該網(wǎng)絡(luò)標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)的ME值是4.635 0，但文獻(xiàn)中[4]算法發(fā)現(xiàn)的最佳社區(qū)結(jié)構(gòu)的ME值為4.620 0。

表3 多學(xué)科網(wǎng)絡(luò)的AvgNM I統(tǒng)計

表3總結(jié)了初始節(jié)點個數(shù)由15逐一增加到40，兩種不同的初始節(jié)點參數(shù)設(shè)置下，算法結(jié)合不同的局部模塊性和全局模塊性對多學(xué)科網(wǎng)絡(luò)聚簇的AvgNM I值。對于多學(xué)科網(wǎng)絡(luò)數(shù)據(jù)顯示，Modularity的聚簇精度高于ME。對于Modularity和ME兩種全局模塊性，LMe、LM和MM這3種局部模塊性也分別獲得了完全一致的AvgNM I值。采用ME的LAICA算法在時聚簇精度明顯高于Dn0=0；而采用Modularity，則兩種不同的初始節(jié)點選擇策略的聚簇精度非常接近。圖3為時，初始節(jié)點數(shù)從12到40時，4種局部模塊性聚簇多學(xué)科網(wǎng)絡(luò)的AvgNM I曲線。

圖3 多學(xué)科網(wǎng)絡(luò)不同初始節(jié)點數(shù)的AvgNM I

3.3 美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)

美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)(American college football network)是根據(jù)2000年秋季常規(guī)賽季的比賽計劃構(gòu)建[16]，以節(jié)點表示球隊、邊表示兩個球隊之間常規(guī)賽季的一場比賽。 網(wǎng)絡(luò)共包含115個節(jié)點和613條邊。115個球隊分屬于12個聯(lián)合會(conference)，因處于同一個聯(lián)合會的球隊間的比賽次數(shù)要多于不同聯(lián)合會的球隊間的比賽次數(shù)，每一個聯(lián)合會建模為一個真實網(wǎng)絡(luò)社區(qū)。文獻(xiàn)[4]中算法聚簇得到了一個包含10個簇的社區(qū)結(jié)構(gòu)，其ME值為5.441 7。

表4 美國足球聯(lián)盟網(wǎng)絡(luò)的AvgNM I統(tǒng)計

表4為初始簇個數(shù)從20逐一增加到115，兩種不同初始節(jié)點選擇策略下，結(jié)合不同的局部模塊性和全局模塊性聚簇足球聯(lián)盟網(wǎng)絡(luò)聚簇的AvgNM I值。數(shù)據(jù)顯示對于該網(wǎng)絡(luò)，ME的聚簇精度高于Modularity。對于Modularity和ME兩種全局模塊性，LMe、LM和MM這3種局部模塊性也分別獲得了完全一致的AvgNM I值。使用ME的LAICA算法在兩種不同的初始節(jié)點選擇策略的聚簇精度明顯高于

圖4 美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)不同初始節(jié)點數(shù)的AvgNM I

3.4 實驗結(jié)果分析

實驗結(jié)果表明，LACIA算法的聚簇精度隨初始局部簇個數(shù)的增加而上升。當(dāng)初始簇個數(shù)與網(wǎng)絡(luò)的節(jié)點個數(shù)完全一致時，LACIA算法等同于快速隨機遞歸搜索算法[1,4]，即：所有節(jié)點同時參與聚簇。隨著初始簇個數(shù)的增加，LACIA算法準(zhǔn)確率升高，但計算消耗也增大。要實現(xiàn)準(zhǔn)確率與計算消耗之間的折衷，需要設(shè)置合理的初始簇個數(shù)。在4種局部模塊性評價標(biāo)準(zhǔn)中，OW的計算和維護相對簡單，卻獲得了相對較好的聚簇精度。任一真實網(wǎng)絡(luò)，在Dn0=0的初始節(jié)點選擇策略下，LMe、LM和MM獲得的聚簇精度完全一致，表明這3種局部模塊性雖使用不同的參數(shù)量化局部簇的簇內(nèi)和簇外連接數(shù)，但因其均采用簇內(nèi)連接與簇外連接之間的比值來表示局部模塊性，搜索局部簇時，這3種局部模塊性均聚合了與局部簇內(nèi)部連接最緊密的節(jié)點，導(dǎo)致最后獲得的局部簇結(jié)構(gòu)相同。

圖5 真實網(wǎng)絡(luò)度分布曲線圖

3個網(wǎng)絡(luò)節(jié)點的度分布(degree distribution)[18]如圖5a～圖5c所示，僅空手道俱樂部網(wǎng)絡(luò)嚴(yán)格遵循冪律發(fā)布(power law)[19]，而美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)節(jié)點的度分布則完全違背冪律分布。空手道俱樂部網(wǎng)絡(luò)的聚簇，當(dāng)Dn0=0時，其平均NM I值均超過0.99，實驗數(shù)據(jù)還顯示，初始節(jié)點數(shù)從16遞增至32，使用ME的LACIA算法均能100%準(zhǔn)確地搜索到該網(wǎng)絡(luò)的標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)。而對于美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)，LACIA算法的聚簇精度最低。所以，對于遵循冪律分布的網(wǎng)絡(luò)，使用ME的LACIA算法的聚簇精度最佳。

4 結(jié)論和未來工作

本文提出了基于局部聚簇的自動聚簇算法(LACIA)。LACIA算法的特點如下：1) 利用局部聚簇發(fā)現(xiàn)局部連接緊密的節(jié)點集，獲得聚簇粒度更大且具有一定聚簇精度的局部簇網(wǎng)絡(luò)結(jié)構(gòu)，從而減少全局聚簇的計算消耗；2) 迭代合并局部簇網(wǎng)絡(luò)的聚簇單元，自動決定網(wǎng)絡(luò)簇數(shù)并精確分配節(jié)點。4種局部模塊性評價標(biāo)準(zhǔn)：local modularity[7]、outwardness[9]、modularityM[10]和LMetric[11]，在LACIA算法中均顯示出較高的聚簇能力。前3者對3個真實網(wǎng)絡(luò)的聚簇結(jié)果基本一致，表明其聚簇能力相似。而Outwardness[9]僅考慮單個鄰居節(jié)點與簇內(nèi)和簇外的連接差異，計算簡單，卻獲得了相對較高的聚簇精度。實驗數(shù)據(jù)也表明，對于遵循冪律分布的網(wǎng)絡(luò)，使用ME的LACIA算法具有最佳聚簇精度。LACIA算法聚簇多個真實網(wǎng)絡(luò)，節(jié)點分配準(zhǔn)確率最高達(dá)99.72%，表明該算法能精確有效地聚簇復(fù)雜網(wǎng)絡(luò)。本文的下一步工作將對LACIA算法聚簇大型網(wǎng)絡(luò)進(jìn)行深入的探測和研究。

[1] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):066133.

[2] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E,2004, 69(2): 026113.

[3] ROSVALL M, BERGSTROM C. An information-theoretic framework for resolving community structure in complex networks[J]. Proceedings of the National Academy of Sciences, 2007, 104(18): 7327-7331.

[4] ROSVALL M, AXELSSON D, BERGSTROM C T. The map equation[J]. Eur Phys Journal, Special Topics,2009(178): 13-23.

[5] CHEN D, FU Y, SHANG M. A fast and efficient heuristic algorithm for detecting community structures in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2009, 388(13): 2741-2749.

[6] XIANG B, CHEN E, ZHOU T. Finding community structure based on subgraph sim ilarity[J]. Studies in Computational Intelligence, 2009(207): 73-82.

[7] CLAUSET A. Finding local community structure in networks[J]. Phys Rev E, 2005(72): 026132.

[8] WAKITA K, TSURUM I T. Finding community structure in mega-scale social networks[C]//In www'07: Proceedings of the 16th International Conference on World Wide Web.Banff(CANADA). NewYork: ACM Press, 2007: 1275-1276 .

[9] BAGROW J P. Evaluating local community methods in networks[J]. Journal of Statistical Mechanics, 2008(7):05001.

[10] LUO F, WANG J Z, PROM ISLOW E. Exploring local community structures in large networks[C]//Proceedings of the 2006 IEEE/W IC/ACM International Conference on Web Intelligence. Hongkong, China: IEEE Computer Society Press, 2006.

[11] CHEN J, ZA?ANE O R, GOEBEL R. Detecting communities in social networks using local information[C]//From Sociology to Computing in Social Networks:Thoeory, Foundation and Applications. New York:SPRINGER-VERLAG W IEN, 2010(1): 197- 214.

[12] FORTUNATO S, BARTHLEMY M. Resolution lim it in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.

[13] FREEMAN L. Centrality in social networks: conceptual clarification. social networks[M]. Lansanne: Elsevier sequoia S.A., 1979.

[14] SHANNON C E. A mathematical theory of communication[J]. Bell System Technical Journal, 1948(27): 379-432, 623-656.

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

[16] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

[17] DANON L, DAZ-GUILERA A, DUCH J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005(9): 09008.

[18] ALBERT R, BARABáSI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002,74(1): 47-97.

[19] BARABáSI A L. Linked: the new science of networks[M].Cambridge, MA, USA: Perseus Publishing, 2002.

編 輯 蔣 曉