李新建 楊繼紅

（1.湖北中煙工業(yè)有限責(zé)任公司信息中心 武漢 430030）（2.中國(guó)人民大學(xué)附屬中學(xué)朝陽(yáng)學(xué)校 北京 100028）

1 引言

人類社會(huì)中人與人的熟知關(guān)系、計(jì)算機(jī)領(lǐng)域中的Internet 終端設(shè)備的互連、生物領(lǐng)域中分子的相互作用都可以用網(wǎng)絡(luò)來(lái)抽象描述，網(wǎng)絡(luò)中的節(jié)點(diǎn)對(duì)應(yīng)系統(tǒng)中的個(gè)體，網(wǎng)絡(luò)的邊代表個(gè)體間的相互關(guān)系。這種抽象只保留了基本結(jié)構(gòu)，過(guò)濾了復(fù)雜的背景信息，有助于對(duì)網(wǎng)絡(luò)代表的系統(tǒng)內(nèi)在共同特征和性質(zhì)進(jìn)行研究。研究發(fā)現(xiàn)這些網(wǎng)絡(luò)并非隨機(jī)網(wǎng)絡(luò)［1］，它們的統(tǒng)計(jì)特性不同于傳統(tǒng)的隨機(jī)網(wǎng)絡(luò)結(jié)構(gòu)，是無(wú)尺度網(wǎng)絡(luò)。網(wǎng)絡(luò)中包含各種社團(tuán)，社團(tuán)是網(wǎng)絡(luò)中內(nèi)部比較致密，外部連接比較松散的子網(wǎng)絡(luò)。網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)是有現(xiàn)實(shí)意義的，例如：在人際關(guān)系網(wǎng)中，個(gè)體有相似愛(ài)好、職業(yè)的個(gè)體常具有社團(tuán)結(jié)構(gòu)特點(diǎn)［2～3］；在科學(xué)研究中，不同社團(tuán)可代表不同的研究領(lǐng)域［4～5］；在Internet 中，新聞、音樂(lè)，論壇內(nèi)容等可被劃分為分別不同主題的社團(tuán)［6～7］。合理有效地對(duì)網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分有助于發(fā)現(xiàn)不同的主題分組，對(duì)了解整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)、功能和特點(diǎn)有重要的意義［8～9］。

一般認(rèn)為，網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)是內(nèi)部連接稠密而外部連接稀疏的子網(wǎng)絡(luò)?！俺砻堋焙汀跋∈琛笔嵌ㄐ远x，在探索網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的過(guò)程中無(wú)法直接使用。因此，常用定量的強(qiáng)社團(tuán)和弱社團(tuán)定義。強(qiáng)社團(tuán)的定義為［10～11］：子圖v中任何一個(gè)頂點(diǎn)與v內(nèi)部頂點(diǎn)連接的度大于其與v 外部頂點(diǎn)連接的度。弱社團(tuán)的定義：子圖v 中所有頂點(diǎn)與v 內(nèi)部頂點(diǎn)的度之和大于v 中所有頂點(diǎn)與v 外部頂點(diǎn)連接的度之和。除此以外，還有派系［12］定義，是指由三個(gè)或三個(gè)以上頂點(diǎn)組成的全聯(lián)通子圖，即任何兩點(diǎn)之間都直接相連。在此基礎(chǔ)通過(guò)弱化連接條件可以進(jìn)行拓展，形成n-派系。例如：2-派系意味著子圖中任意兩個(gè)頂點(diǎn)不必直接相連，但最多通過(guò)一個(gè)中介點(diǎn)就可以連通。3-派系是指子圖中的任意兩個(gè)頂點(diǎn)，最多通過(guò)兩個(gè)中介點(diǎn)就能連通，以此類推，隨著n 值增加，n-派系的要求越來(lái)越弱。這些定義允許社團(tuán)間存在重疊：即單個(gè)頂點(diǎn)并非僅僅屬于一個(gè)社團(tuán)，還可以同時(shí)屬于兩個(gè)及兩個(gè)以上的社團(tuán)。本文關(guān)注完全相互獨(dú)立的社團(tuán)結(jié)構(gòu)，因此采用較為常用的基于相對(duì)頻數(shù)的社團(tuán)結(jié)構(gòu)定義。

在社團(tuán)定義的基礎(chǔ)上，在復(fù)雜網(wǎng)絡(luò)中進(jìn)行社團(tuán)結(jié)構(gòu)劃分的方法大致可以分為3 類：層次聚類方法、搜索方法和其他方法。層次聚類方法又可以進(jìn)一步分為凝聚過(guò)程和分裂過(guò)程，它們的主要區(qū)別在于是由底向上合并還是自頂向下分解。凝聚過(guò)程：即以頂點(diǎn)為基礎(chǔ)，通過(guò)一定方法逐步凝聚，最終形成社團(tuán)。主要步驟是：1）把網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)對(duì)象都看成一個(gè)單獨(dú)的社團(tuán)，網(wǎng)絡(luò)中有多少節(jié)點(diǎn)就有多少社團(tuán)；2）設(shè)定某種標(biāo)準(zhǔn)衡量社團(tuán)與社團(tuán)間的距離和相似度；3）逐步合并這些初始社團(tuán)進(jìn)而形成更大的社團(tuán)，直至所有節(jié)點(diǎn)都聚集到一個(gè)社團(tuán)中，或者滿足某個(gè)終結(jié)條件停止。分裂過(guò)程采用的層次分解方法為自頂向下，與凝聚相反。搜索方法是建立逐步優(yōu)化某個(gè)目標(biāo)的探索過(guò)程，社團(tuán)結(jié)構(gòu)直接由最后的優(yōu)化結(jié)果給出。代表性的方法有PageRank［13］和HIT［14］。不屬于這兩種方法的劃為其他類，代表的方法有譜方法［15］。現(xiàn)有方法在復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)挖掘中取得一定的效果，但是在應(yīng)用過(guò)程還是存在諸多問(wèn)題：1）現(xiàn)在很多算法雖然有效，但是復(fù)雜度很高，限制了在大網(wǎng)絡(luò)中進(jìn)行社團(tuán)結(jié)構(gòu)劃分的應(yīng)用。2）己有方法大多需要設(shè)置一些特定的參數(shù)，這些參數(shù)需要大量的相關(guān)領(lǐng)域的經(jīng)驗(yàn)，甚至需要專家提供指導(dǎo)。3）很多方法需要使用大型矩陣，需要大量計(jì)算或占用的大量存儲(chǔ)空間。

因此本文討論P(yáng)CA、K-Means 和PSO 三種原理簡(jiǎn)單且實(shí)現(xiàn)高效的社團(tuán)結(jié)構(gòu)劃分方法。

2 社團(tuán)結(jié)構(gòu)劃分方法

本文討論的PCA、K-Means 和PSO 三種劃分方法均需要利用到Girvan 和Newman 定義的模塊度［6］。模塊度指網(wǎng)絡(luò)中連接社團(tuán)結(jié)構(gòu)的內(nèi)部頂點(diǎn)的邊所占的比例與另外一個(gè)隨機(jī)網(wǎng)絡(luò)中連接社團(tuán)結(jié)構(gòu)內(nèi)部頂點(diǎn)的邊所占比例的期望值相減得到的差值。這個(gè)隨機(jī)網(wǎng)絡(luò)的構(gòu)造方法是：保持每個(gè)頂點(diǎn)的社團(tuán)屬性不變，頂點(diǎn)間的邊根據(jù)頂點(diǎn)的度隨機(jī)連接。評(píng)判社團(tuán)結(jié)構(gòu)劃分好壞的標(biāo)準(zhǔn)是看社團(tuán)內(nèi)部鏈接的稠密程度和隨機(jī)連接網(wǎng)絡(luò)的期望水平之間的關(guān)系。如果社團(tuán)結(jié)構(gòu)劃分的好，則社團(tuán)內(nèi)部連接的稠密程度應(yīng)該高于隨機(jī)連接網(wǎng)絡(luò)的期望水平。用Q函數(shù)定量描述社團(tuán)劃分的模塊化水平：

其中Aij為網(wǎng)絡(luò)中連接矩陣的元素，如果i，j兩點(diǎn)有邊相連，Aij=1，否則Aij=0。ci為頂點(diǎn)i所屬的社團(tuán)，若ci=cj則?(ci，cj) =1，否則為零。m 為網(wǎng)絡(luò)的邊數(shù)，ki為頂點(diǎn)i 的度。如果社團(tuán)內(nèi)部頂點(diǎn)間的邊沒(méi)有隨機(jī)連接得到的邊多，則Q 為負(fù)值，如果Q 接近1時(shí)，表明相應(yīng)的社團(tuán)結(jié)構(gòu)劃分得很好。

2.1 PCA

PCA方法是一種從對(duì)象中提取主要信息，忽略相對(duì)次要信息的多元統(tǒng)計(jì)分析方法。利用該方法將一個(gè)網(wǎng)絡(luò)劃分為幾個(gè)不同的社團(tuán)，其本質(zhì)是在最大化提取網(wǎng)絡(luò)本身的主要信息。它是一種自底向上的方法。應(yīng)用PCA 方法實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)多社團(tuán)的劃分可以通過(guò)對(duì)一次劃分后所得到的社團(tuán)不斷重復(fù)進(jìn)行二社團(tuán)結(jié)構(gòu)的劃分來(lái)實(shí)現(xiàn)。在對(duì)一次劃分所得的社團(tuán)繼續(xù)劃分時(shí)，因?yàn)樵撋鐖F(tuán)始終是整個(gè)網(wǎng)絡(luò)的一部分，這樣就需要把它放到整個(gè)網(wǎng)絡(luò)中去考慮，而不能把它作為一個(gè)獨(dú)立的網(wǎng)絡(luò)來(lái)處理。可以通過(guò)按網(wǎng)絡(luò)的協(xié)方差矩陣中最大的特征值所對(duì)應(yīng)的特征向量在各維取值的正負(fù)，將目標(biāo)劃分兩個(gè)社團(tuán)。劃分結(jié)果的優(yōu)劣可用模塊度來(lái)衡量。在不斷重復(fù)劃分的過(guò)程中，模塊度最大的社團(tuán)結(jié)構(gòu)劃分狀態(tài)一般認(rèn)為是網(wǎng)絡(luò)實(shí)際所具有的社區(qū)結(jié)構(gòu)。

2.2 K-Means

假設(shè)網(wǎng)絡(luò)G有n個(gè)節(jié)點(diǎn)和m條邊。為了衡量節(jié)點(diǎn)傳輸信息的有效性，引入網(wǎng)絡(luò)效率NE 的概念。假設(shè)網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的信息總是沿著最短路徑傳播的，則節(jié)點(diǎn)i和j之間的信息傳輸效率εij為它們之間最短路徑長(zhǎng)度dij的倒數(shù)（如果節(jié)點(diǎn)i和j之間不存在路徑，則最短路徑長(zhǎng)度為∞，εij=0）。

整個(gè)網(wǎng)絡(luò)G 的信息有效率定義為各節(jié)點(diǎn)對(duì)的信息傳輸有效率的平均值NE［G］，即

邊eij的信息中心度Ceij，定義為移除該邊后整個(gè)網(wǎng)絡(luò)的信息有效率減少的相對(duì)量，即

社團(tuán)間的邊的信息中心度比社團(tuán)內(nèi)部邊的信息中心度大。節(jié)點(diǎn)i 與j 之間的邊的信息中心度越小，它們的關(guān)聯(lián)度就越大，屬于同一個(gè)團(tuán)的概率就越大，兩個(gè)相鄰節(jié)點(diǎn)的關(guān)聯(lián)度：

非相鄰節(jié)點(diǎn)間的關(guān)聯(lián)度可用最短路徑上所有節(jié)點(diǎn)對(duì)的關(guān)聯(lián)度乘積表示。

應(yīng)用K-Means方法進(jìn)行社團(tuán)劃分的主要思想：以最小關(guān)聯(lián)度原則選取新的聚類中心，以最大關(guān)聯(lián)度原則進(jìn)行模式歸類，直到所有的節(jié)點(diǎn)都劃分完為止，最后根據(jù)模塊度來(lái)確定理想的社團(tuán)數(shù)，即k值。

2.3 PSO

PSO 算法具有進(jìn)化計(jì)算和群智能的特點(diǎn)，和其他進(jìn)化算法相似，PSO 也是通過(guò)個(gè)體間的協(xié)作與競(jìng)爭(zhēng)，實(shí)現(xiàn)復(fù)雜空間中最優(yōu)解的搜索。PSO 先產(chǎn)生一個(gè)初始種群，種群中每個(gè)粒子都是優(yōu)化問(wèn)題的一個(gè)可行解，并由目標(biāo)函數(shù)確定一個(gè)適應(yīng)度值，種群中的粒子將追隨當(dāng)前的最優(yōu)粒子運(yùn)動(dòng)，并經(jīng)過(guò)不斷進(jìn)化得到最優(yōu)解：在每一次進(jìn)化中，粒子將追蹤兩個(gè)極值，一個(gè)是粒子本身迄今找到的最優(yōu)解pbest，一個(gè)是整個(gè)種群迄今找到的最優(yōu)解gbest。在劃分問(wèn)題中，PSO 中每個(gè)粒子包含一個(gè)適應(yīng)值f，速度和位置更新定義為粒子的移動(dòng)方向v。v 是由當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)所屬社團(tuán)的情況決定。初始時(shí)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)獨(dú)立為一個(gè)社團(tuán)。在算法迭代過(guò)程中，粒子的移動(dòng)方向v 選擇為向任意一個(gè)與該粒子所在節(jié)點(diǎn)有邊，且不屬于同一個(gè)社團(tuán)的下一個(gè)節(jié)點(diǎn)移動(dòng)。當(dāng)粒子到達(dá)新節(jié)點(diǎn)后，計(jì)算新的適應(yīng)值f'，若新適應(yīng)值f'大于原有值f，則把新節(jié)點(diǎn)的社團(tuán)標(biāo)號(hào)標(biāo)為原有節(jié)點(diǎn)的社團(tuán)標(biāo)號(hào)，否則保持不變。直到粒子運(yùn)動(dòng)前后模塊Q不變或者達(dá)到進(jìn)化迭代數(shù)。

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

本文實(shí)驗(yàn)所用的硬件環(huán)境是：CPU Intel I5-4440（3.1GHz），內(nèi)存為8GB，三種方法在Windows 7 下用C#實(shí)現(xiàn)。

為了比較三種方法，本文設(shè)計(jì)了兩組實(shí)驗(yàn)。實(shí)驗(yàn)一采用的數(shù)據(jù)集是Zachary Club 數(shù)據(jù)集。20 世紀(jì)70 年代初，Wayne Zachary 觀察了美國(guó)大學(xué)空手道俱樂(lè)部成員間的人際關(guān)系，并依據(jù)俱樂(lè)部成員間平時(shí)的交往狀況建立了一個(gè)網(wǎng)絡(luò)。這個(gè)網(wǎng)絡(luò)包含34 個(gè)頂點(diǎn)，代表了俱樂(lè)部成員；包含了78 條邊，代表他們之間的人際關(guān)系。由于突發(fā)的原因，俱樂(lè)部管理者與俱樂(lè)部主要教師之間針對(duì)是否提高收費(fèi)這一問(wèn)題產(chǎn)生了激烈的爭(zhēng)論，并最終導(dǎo)致俱樂(lè)部分裂成兩部分。該網(wǎng)絡(luò)己知網(wǎng)絡(luò)結(jié)構(gòu)，便于比較得到劃分方法的準(zhǔn)確性。實(shí)驗(yàn)二采用計(jì)算機(jī)隨機(jī)生成網(wǎng)絡(luò)圖，可以通過(guò)擴(kuò)大社團(tuán)成員規(guī)模，比較幾種算法對(duì)不同規(guī)模網(wǎng)絡(luò)的運(yùn)行時(shí)間和正確率。

圖1 Zachary Karate Club的社團(tuán)圖。圓形節(jié)點(diǎn)代表管理者社團(tuán)，方形節(jié)點(diǎn)代表教師社團(tuán)。

實(shí)驗(yàn)結(jié)果為PCA方法的準(zhǔn)確率為97%，錯(cuò)分了第6號(hào)節(jié)點(diǎn)。圖2是該網(wǎng)絡(luò)協(xié)方差矩陣的最大特征值所對(duì)應(yīng)的單位特征向量q 在各維上的數(shù)值。特征向量q 各維的數(shù)值大小一定程度反映了其所對(duì)應(yīng)的網(wǎng)絡(luò)中節(jié)點(diǎn)所屬于社團(tuán)的力度。

圖2 Zachary Karate Club網(wǎng)絡(luò)協(xié)方差矩陣最大特征值對(duì)應(yīng)的單位向量在各維上的值。三角形節(jié)點(diǎn)代表管理者社團(tuán)，圓形節(jié)點(diǎn)代表教師社團(tuán)

K-Means 方法的結(jié)果隨k 取值的不同，劃分的社團(tuán)個(gè)數(shù)與隸屬情況也不一樣。由圖3 可知，當(dāng)k取2 時(shí)，Q 值最大，表明劃分為2 個(gè)社團(tuán)時(shí)是最合適的。

圖3 K-Means 對(duì)Zachary Karate Club網(wǎng)絡(luò)中不同社團(tuán)劃分?jǐn)?shù)對(duì)應(yīng)的Q值

PSO 在多次計(jì)算中，還存在極少數(shù)進(jìn)化搜索失敗的可能，對(duì)Zachary Karate Club進(jìn)行劃分時(shí)，節(jié)點(diǎn)10被錯(cuò)誤劃分，其余的均正確。

圖4 隨機(jī)擴(kuò)展網(wǎng)絡(luò)規(guī)模，三種方法的時(shí)間消耗與正確率。圓形代表PSO，三角代表K-Means，十字代表PCA，實(shí)線是相應(yīng)方法的時(shí)間消耗，虛線是正確率。

實(shí)驗(yàn)2 通過(guò)不斷擴(kuò)大社團(tuán)成員規(guī)模，比較三種算法對(duì)不同規(guī)模網(wǎng)絡(luò)的運(yùn)行時(shí)間和正確率。從圖4 可以看出，PCA、K-Means 和PSO 都保持著較低的運(yùn)行時(shí)間、不低于0.8的較高的正確率。其中，PCA在運(yùn)行時(shí)間上表現(xiàn)最為突出，K-Means 次之，基于PSO 消耗時(shí)間較長(zhǎng)。但是，PSO 在時(shí)間上的消耗可以獲得更好的正確率，在正確率方面，PSO 表現(xiàn)的最好，K-Means次之，PCA 最差。因此，三種方法應(yīng)用場(chǎng)景側(cè)重點(diǎn)不同有關(guān)。可根據(jù)不同社團(tuán)規(guī)模進(jìn)行選擇。當(dāng)社團(tuán)規(guī)模較小，對(duì)正確率要求較高時(shí)候選擇PSO；當(dāng)社團(tuán)規(guī)模較大的時(shí)候，選擇PCA 會(huì)有優(yōu)勢(shì)。K-Means是折中的方法。

4 結(jié)語(yǔ)

本文介紹了網(wǎng)絡(luò)中社團(tuán)劃分的方法，特別針對(duì)PCA、K-Means 和PSO 三種簡(jiǎn)潔實(shí)用的方法進(jìn)行了討論，并在Chary Karate Club 網(wǎng)絡(luò)和人工變尺度網(wǎng)絡(luò)上進(jìn)行社團(tuán)結(jié)構(gòu)探測(cè)的性能比較，證明了三種方法劃分有效性和性能特點(diǎn)。