吳 悠

（武漢理工大學(xué)，湖北 武漢430070）

0 引言

隨著對(duì)網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究， 人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有一個(gè)共同性質(zhì)，即社團(tuán)結(jié)構(gòu)。 近年來(lái)，社團(tuán)結(jié)構(gòu)分析在生物學(xué)、計(jì)算機(jī)圖形學(xué)和社會(huì)學(xué)中都有廣泛的應(yīng)用[2]。 目前關(guān)于復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)算法的研究有很多，本文將介紹幾種有代表性的方法。

1 Kernighan-Lin 算法

1.1 方法概述

Kernighan-Lin 算法是一種試探優(yōu)化法。 它是一種基于貪婪算法原理將網(wǎng)絡(luò)劃分為兩個(gè)大小已知的社團(tuán)的二分法。

1.2 實(shí)現(xiàn)過(guò)程及應(yīng)用[3]

K-L 算法可以描述為：首先，將網(wǎng)絡(luò)的節(jié)點(diǎn)隨機(jī)地劃分為已知大小的兩個(gè)社團(tuán)。在此基礎(chǔ)上，考慮所有可能的節(jié)點(diǎn)對(duì)，其中每個(gè)節(jié)點(diǎn)對(duì)的節(jié)點(diǎn)分別來(lái)自?xún)蓚€(gè)社團(tuán)。對(duì)每個(gè)節(jié)點(diǎn)對(duì)，如果交換這兩個(gè)節(jié)點(diǎn)的話(huà)，計(jì)算可能得到Q 的增益Q=Q交換前-Q交換后,然后交換最大的△Q 對(duì)應(yīng)的節(jié)點(diǎn)對(duì)，同時(shí)記錄交換后的Q 值。 規(guī)定每個(gè)節(jié)點(diǎn)只能交換一次。 重復(fù)這個(gè)交換過(guò)程，直到某個(gè)社團(tuán)內(nèi)所有的節(jié)點(diǎn)都被交換一次為止。 需要注意的是， 在節(jié)點(diǎn)對(duì)交換的過(guò)程中，Q 值并不一定是單調(diào)增加的。 不過(guò)，即使某一步的交換會(huì)使Q 值有所下降，也仍然可能在其后的步驟中出現(xiàn)一個(gè)更大的Q 值。 當(dāng)交換完畢后，便找到上述交換過(guò)程中所記錄的最大Q 值。 這時(shí)對(duì)應(yīng)的社團(tuán)結(jié)構(gòu)就認(rèn)為是該網(wǎng)絡(luò)實(shí)際的社團(tuán)結(jié)構(gòu)。

1.3 評(píng)價(jià)

該方法存在一個(gè)嚴(yán)重的缺陷，即必須事先知道該網(wǎng)絡(luò)的兩個(gè)社團(tuán)大小分別是多少，否則就很可能不會(huì)得到正確的答案。 K-L 算法的這個(gè)缺陷使得它在實(shí)際網(wǎng)絡(luò)分析中難以應(yīng)用。 而且，即使解決了這個(gè)問(wèn)題，它仍然面臨著如何事先知道網(wǎng)絡(luò)社團(tuán)數(shù)目，以確定二分法要重復(fù)到哪一步停止的問(wèn)題。

2 譜平分法

2.1 方法概述

該算法利用網(wǎng)絡(luò)結(jié)構(gòu)的Laplace 矩陣中不為0 的特征值所對(duì)應(yīng)的特征向量和同一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)對(duì)應(yīng)的元素近似值相等的原理對(duì)網(wǎng)絡(luò)社區(qū)進(jìn)行劃分。

譜平分法本質(zhì)上是一種二分法，在每次二分的過(guò)程中，網(wǎng)絡(luò)被分割成兩個(gè)近似平衡的子網(wǎng)絡(luò)。 當(dāng)網(wǎng)絡(luò)中含有多個(gè)社團(tuán)時(shí)，譜平分法遞歸地分割現(xiàn)存的子網(wǎng)絡(luò)，直到滿(mǎn)足預(yù)先定義的停止條件為止。

2.2 實(shí)現(xiàn)過(guò)程

該算法可以描述為：一個(gè)有n 個(gè)節(jié)點(diǎn)的無(wú)向圖G 的Laplace 矩陣是一個(gè)n×n 維的對(duì)稱(chēng)矩陣L。 如果節(jié)點(diǎn)i 和節(jié)點(diǎn)j 有邊相連，則lij=-1，否則lij=0.對(duì)角線(xiàn)上的元素lij表示節(jié)點(diǎn)i 的度。 由于Laplace 矩陣所有的行或列的和都為0，因此，該矩陣總有一個(gè)特征值為0，且其對(duì)應(yīng)的特征向量為I=（1，1，1,···，1）。 我們也可以將矩陣L 表示成L=K-A，其中K 是一個(gè)對(duì)角矩陣，其對(duì)角線(xiàn)上的元素對(duì)應(yīng)各個(gè)節(jié)點(diǎn)的度，而A則為該網(wǎng)絡(luò)的連接矩陣。 可以從理論上證明，不為零的特征值所對(duì)應(yīng)的特征向量的各元素中，同一個(gè)社團(tuán)內(nèi)的節(jié)點(diǎn)對(duì)應(yīng)的元素是近似相等的。 因此，可以根據(jù)復(fù)雜網(wǎng)絡(luò)的Laplace 矩陣次小特征值λ2對(duì)應(yīng)的特征向量，所有正元素對(duì)應(yīng)的那些節(jié)點(diǎn)都屬于同一社團(tuán)，而所有的負(fù)元素對(duì)應(yīng)的那些節(jié)點(diǎn)都屬于另一個(gè)社團(tuán)，這樣就將其分為兩個(gè)社團(tuán)。

2.3 評(píng)價(jià)及改進(jìn)方法

譜平分法主要缺陷是只能將圖分成2 個(gè)子圖， 若要分成多個(gè)子圖，則只能多次應(yīng)用該方法。即使這樣可行，我們預(yù)先也無(wú)法確定究竟將圖分割成多少個(gè)子圖才合適。

為了克服這一缺陷，Capocci 等人在傳統(tǒng)譜分析法的基礎(chǔ)上提出另一種算法。 傳統(tǒng)譜平分法是基于Laplace 矩陣L=K-A。Capocci 算法[4]則是基于標(biāo)準(zhǔn)矩陣N=K-1A。 利用行標(biāo)準(zhǔn)化的轉(zhuǎn)換可得，矩陣N 的最大特征值總是等于1，相應(yīng)的特征向量稱(chēng)為平凡特征向量。 在對(duì)社團(tuán)化明顯的網(wǎng)絡(luò)的分析中發(fā)現(xiàn)，如果網(wǎng)絡(luò)自然呈現(xiàn)g 個(gè)社團(tuán)，則標(biāo)準(zhǔn)矩陣就有g(shù)-1 個(gè)十分接近1 的第一非平凡特征值，而其余的特征值都與1有較大的距離。 這g-1 個(gè)特征值所對(duì)應(yīng)的特征向量（稱(chēng)為第一非平凡特征向量或者第二特征向量）有一個(gè)特性：在同一個(gè)社團(tuán)中的頂點(diǎn)所對(duì)應(yīng)的值較為接近。因此，特征向量中元素的值呈現(xiàn)階梯狀分布，并且階梯的級(jí)數(shù)與社團(tuán)的個(gè)數(shù)相匹配。

3 GN 算法

3.1 方法概述

Girvan 和Newman 提出了一種基于邊介數(shù)的分裂算法，即G-N 算法。 不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊。 邊介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過(guò)每條邊的最短路徑數(shù)目。

3.2 實(shí)現(xiàn)過(guò)程

首先，計(jì)算網(wǎng)絡(luò)中各條邊的邊介數(shù)，找出邊介數(shù)最大的邊，并將它移除（如果最大邊介數(shù)的邊不唯一，那么既可以隨機(jī)挑選一條邊斷開(kāi)也可以將這些邊同時(shí)斷開(kāi)）；然后，重新計(jì)算網(wǎng)絡(luò)中剩余各條邊的邊介數(shù)；接著重復(fù)上面的步驟，直到網(wǎng)絡(luò)中所有的邊都被移除。

3.3 評(píng)價(jià)及改進(jìn)方法

GN 算法彌補(bǔ)了一些傳統(tǒng)算法的不足，但是也存在一個(gè)缺陷，即它對(duì)于網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)并沒(méi)有一個(gè)量的定義。因此不能直接從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)判斷它所求得的社團(tuán)結(jié)構(gòu)是否是實(shí)際網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，從而需要一些附加的關(guān)于網(wǎng)絡(luò)意義的信息來(lái)判斷所得到的社團(tuán)結(jié)構(gòu)是否具有實(shí)際意義。

為了得到具有實(shí)際意義的社團(tuán)結(jié)構(gòu)，Newman 等人引進(jìn)了一個(gè)衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)——模塊度。 考慮某種劃分形式，它將網(wǎng)絡(luò)劃分為k 個(gè)社團(tuán)。 定義一個(gè)k×k 維的對(duì)稱(chēng)矩陣E=（eij），其中元素eij表示網(wǎng)絡(luò)中連接兩個(gè)不同社團(tuán)的節(jié)點(diǎn)的邊在所有邊中所占的比例，這兩個(gè)節(jié)點(diǎn)分別位于第i 個(gè)社團(tuán)和第j 個(gè)社團(tuán)。

4 結(jié)束語(yǔ)

復(fù)雜網(wǎng)絡(luò)中社區(qū)的劃分具有重要的使用價(jià)值。本文給出了三種經(jīng)典的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法，較為詳細(xì)的描述了各種算法的核心思想和基本過(guò)程，并對(duì)各算法進(jìn)行了適當(dāng)?shù)姆治龊捅容^，為影虎針對(duì)不同的復(fù)雜網(wǎng)絡(luò)選擇適合的社區(qū)劃分算法提供了一定的借鑒作用。

［1］韓瑞凱，孟嗣儀.基于興趣相似度的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法研究[J].鐵路計(jì)算機(jī)應(yīng)用，2010,19（10）：10-14.

［2］張聰，沈惠璋.復(fù)雜網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)的快速劃分算法[J].系統(tǒng)工程，2011,29（208）：93-98.

［3］汪小帆，劉亞冰.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述[J].電子科技大學(xué)學(xué)報(bào)，2009,38（5）：537-543.

［4］謝福鼎，張磊.一種基于譜平分法的社團(tuán)劃分算法[J].計(jì)算機(jī)科學(xué)，2009,36（11）：186-188.

［5］安娜，謝福鼎.一種基于GN 算法的文本概念聚類(lèi)新方法[J].計(jì)算機(jī)工程與應(yīng)用，2008,44（14）：142-144.