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

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

現(xiàn)實(shí)世界中的諸多系統(tǒng)均可建模為復(fù)雜網(wǎng)絡(luò)(complex network)，如：WWW萬(wàn)維網(wǎng)、人際關(guān)系網(wǎng)、流行病傳播網(wǎng)等。系統(tǒng)中的實(shí)體(entity)由節(jié)點(diǎn)(node)表示，而實(shí)體之間的關(guān)聯(lián)(interaction/relation)由邊(edge)表示，節(jié)點(diǎn)集和邊集構(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é)點(diǎn)連接緊密而社區(qū)之間連接相對(duì)疏松的特點(diǎn)[1]。隨著計(jì)算機(jī)技術(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)中使用的快速隨機(jī)遞歸搜索算法(fast stochastic and recursive search algorithm)[3-4,7-8]，根據(jù)特定的全局模塊性，如：Q函數(shù)(modularity)[2]和網(wǎng)絡(luò)最短描述長(zhǎng)度(network minimum description length,NMDL)等[3-4]，利用全局信息(global information)，對(duì)所有的點(diǎn)和邊同時(shí)展開搜索從而揭示網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，導(dǎo)致聚簇時(shí)間和空間消耗偏高。因全局聚簇需預(yù)先掌握網(wǎng)絡(luò)的全局連接信息，有些還需預(yù)知簇?cái)?shù)，使其對(duì)于動(dòng)態(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需全局信息，通過計(jì)算單個(gè)簇的模塊性搜索局部簇，特別適應(yīng)于動(dòng)態(tài)網(wǎng)絡(luò)和大型網(wǎng)絡(luò)的已知區(qū)域。

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

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

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

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

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

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

1.2 局部模塊性

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

表1 局部模塊性評(píng)價(jià)標(biāo)準(zhǔn)的定義和計(jì)算公式

2 基于局部聚合與迭代的自動(dòng)聚簇

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

2.1 局部聚合算法

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

2.2 局部簇迭代合并算法

通過局部聚簇X￠到一組局部簇。所有局部簇和未被聚合到局部簇的其他節(jié)點(diǎn)則構(gòu)成了X￠的局部簇網(wǎng)絡(luò)結(jié)構(gòu)X￠，其中每一個(gè)局部簇或節(jié)點(diǎn)均為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個(gè)節(jié)點(diǎn)和l條邊，且其節(jié)點(diǎn)分布在m個(gè)簇中，M表示包含該m個(gè)簇的特定社區(qū)結(jié)構(gòu)，Q函數(shù)和ME的定義和計(jì)算公式分別如下：

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

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

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

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

2.1.2 局部簇迭代合并

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

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

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

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

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

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

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

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

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

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

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

為了驗(yàn)證LAICA算法的有效性和可行性，使用Zachary空手道俱樂部網(wǎng)絡(luò)(Zachary karate club network)[15]、多學(xué)科網(wǎng)絡(luò)(multi-discipline network)[3]和美國(guó)大學(xué)足球聯(lián)盟網(wǎng)絡(luò)(American college football network)[16]等多個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行聚簇實(shí)驗(yàn)。文獻(xiàn)[17]提出范化互信息(normalized mutual information,NM I)計(jì)算聚簇所得社區(qū)結(jié)構(gòu)和真實(shí)社區(qū)結(jié)構(gòu)的相似程度，本文也采用NM I作為聚簇精度對(duì)LAICA算法進(jìn)行了定量分析與評(píng)估。實(shí)驗(yàn)采用兩種參數(shù)產(chǎn)生初始節(jié)點(diǎn)：并比較這兩種參數(shù)設(shè)置下LAICA的聚簇精度，其中：Dn0=0時(shí)所選擇的初始節(jié)點(diǎn)即為網(wǎng)絡(luò)中度數(shù)最高的節(jié)點(diǎn)。實(shí)驗(yàn)所獲社區(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個(gè)節(jié)點(diǎn)和78條邊構(gòu)成，其中：節(jié)點(diǎn)代表俱樂部成員、邊代表成員之間的社會(huì)交往。因意見分歧，俱樂部分裂成以俱樂部管理者和俱樂部教練為中心的兩個(gè)子俱樂部。此網(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)計(jì)

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

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

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

多學(xué)科網(wǎng)絡(luò)(multi-discipline network)[3]以節(jié)點(diǎn)表示期刊、邊表示引用關(guān)系。如果一個(gè)期刊的某篇論文引用了另一期刊的某篇論文，則構(gòu)成了兩個(gè)期刊之間的一個(gè)引用關(guān)系。網(wǎng)絡(luò)包含4個(gè)領(lǐng)域：multidisciplinary physics、chem istry、bioloegy和ecology，每一個(gè)領(lǐng)域?yàn)橐粋€(gè)社區(qū)。每一個(gè)領(lǐng)域選取10個(gè)期刊共40個(gè)期刊作為節(jié)點(diǎn)，期刊之間的189個(gè)引用關(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)計(jì)

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

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

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

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

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

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

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

3.4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

編 輯 蔣 曉