應(yīng)用人工魚群算法的重疊社區(qū)檢測＊

王一萍，孫 明

（齊齊哈爾大學(xué)計(jì)算機(jī)與控制工程學(xué)院，黑龍江 齊齊哈爾161006）

1 引言

隨著大數(shù)據(jù)現(xiàn)象的涌現(xiàn)，復(fù)雜網(wǎng)絡(luò)已成為描述和量化復(fù)雜系統(tǒng)的工具，社區(qū)發(fā)現(xiàn)是重要問題之一。真實(shí)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)普遍存在，如社會(huì)網(wǎng)絡(luò)中各種小社團(tuán)；代謝網(wǎng)絡(luò)中的功能社區(qū)；引文網(wǎng)中的課題社區(qū)等。檢測社區(qū)結(jié)構(gòu)是理解網(wǎng)絡(luò)結(jié)構(gòu)和功能的基礎(chǔ)，發(fā)現(xiàn)社區(qū)對(duì)洞察、預(yù)測網(wǎng)絡(luò)功能和拓?fù)浣Y(jié)構(gòu)有重要意義，可用于研究病毒傳播、市場營銷，發(fā)現(xiàn)犯罪團(tuán)伙等。各種社區(qū)檢測算法的區(qū)別在于如何確認(rèn)社區(qū)集。根據(jù)各種領(lǐng)域需求提出了許多社區(qū)檢測方法，導(dǎo)致在不同真實(shí)或計(jì)算機(jī)生成網(wǎng)絡(luò)上測試算法時(shí)性能不同。已有算法基本假定每個(gè)節(jié)點(diǎn)只屬于一個(gè)社區(qū)，即各個(gè)社區(qū)不重疊，而有些節(jié)點(diǎn)天然屬于多個(gè)功能團(tuán)，社區(qū)重疊普遍存在于各種實(shí)際網(wǎng)絡(luò)中。例如，社會(huì)網(wǎng)絡(luò)中許多人同時(shí)屬于多個(gè)社團(tuán)，合作網(wǎng)絡(luò)中的作者可能與其他工作組研究者合作，Web中很多網(wǎng)頁同屬于多個(gè)主題等。重疊社區(qū)發(fā)現(xiàn)有一定現(xiàn)實(shí)意義。

2002年Girvan和Newman［1］首次給出社區(qū)定義：整個(gè)網(wǎng)絡(luò)由若干個(gè)“社區(qū)”或“組”構(gòu)成。社區(qū)內(nèi)節(jié)點(diǎn)間連接相對(duì)于社區(qū)間連接更加緊密。研究者已提出了很多社區(qū)發(fā)現(xiàn)算法，大致分為：（1）圖分割法，如譜分法［2］、K-L法［3］、派系過濾法［4］和電阻算法［5］等；（2）層次聚類法，如按節(jié)點(diǎn)相似度合并法［6］、基于邊介數(shù)分裂的 GN 法［1］、基于邊聚集系數(shù)分裂［7］；（3）模塊度法［8，9］、信息傳播法［10］等。關(guān)于復(fù)雜網(wǎng)絡(luò)社區(qū)檢測雖有很多研究，但還有很多待解決問題，如社區(qū)數(shù)學(xué)定義，有的算法雖性能好但計(jì)算量大等。復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)還需努力，尤其是重疊社區(qū)劃分。Palla提出的團(tuán)滲透法［4］（CMP）最先解決重疊社區(qū)劃分，以團(tuán)為單元發(fā)現(xiàn)重疊，對(duì)于真實(shí)網(wǎng)絡(luò)限制過于嚴(yán)格，只能發(fā)現(xiàn)少量重疊社團(tuán)，且k-派系k值不好定；Gregory提出的按節(jié)點(diǎn)度設(shè)置分裂值，可將節(jié)點(diǎn)劃分到多個(gè)社區(qū)的算法（CONGA），時(shí)間復(fù)雜度是O（n（n＋m）），其中n為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)，m為網(wǎng)絡(luò)的邊數(shù)，對(duì)于節(jié)點(diǎn)數(shù)多的網(wǎng)絡(luò)計(jì)算量過大。

本文提出了一種基于人工魚群的重疊社區(qū)檢測算法 AFSCDA（Artificial Fish-Swarm Community Detection Algorithm），在已有的文獻(xiàn)中還沒有被應(yīng)用到社區(qū)檢測的研究中。人工魚群算法是李曉磊等人［11，12］于2002年提出的一種尋優(yōu)算法，它是模仿魚群行為的基于動(dòng)物自治體隨機(jī)搜索優(yōu)化法，人工魚群算法從新角度開辟了解決復(fù)雜問題優(yōu)化的途徑。

2 社會(huì)網(wǎng)絡(luò)的人工魚模型

2.1 相關(guān)定義

假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為n，邊數(shù)為m，k為待劃分社區(qū)數(shù)，L＝n＊k表示每條人工魚維數(shù)。下面為關(guān)于社會(huì)網(wǎng)絡(luò)的人工魚模型AF的一些定義。

定義1 人工魚個(gè)體的狀態(tài)變量：X＝｛x1，x2，…，xn｝＝ ｛x11，…，x1k，x21，…，x2k，…，xn1，…，xnk｝，X由n段組成，每段長k，即X由n個(gè)行向量構(gòu)成，每個(gè)行向量表示對(duì)應(yīng)節(jié)點(diǎn)的劃分情況。其中xij（i＝1..n；j＝1..k）為欲尋優(yōu)變量，取值為0或1，值為1表示節(jié)點(diǎn)i被劃分到社區(qū)j中；反之沒被劃分到社區(qū)j中。人工魚個(gè)體狀態(tài)變量是一個(gè)二進(jìn)制串，在重疊社區(qū)劃分中，由于允許一個(gè)節(jié)點(diǎn)屬于多個(gè)社區(qū)，所以某個(gè)節(jié)點(diǎn)i可能同時(shí)屬于不止一個(gè)社區(qū)，即第i段中可能有多個(gè)值為1的分量。人工魚X當(dāng)前狀態(tài)的食物濃度表示為F＝f（X），其中F為目標(biāo)函數(shù)值；兩個(gè)人工魚個(gè)體X、Y 之 間 的 距 離 采 用 海 明 距 離：D（X，Y）＝X⊕Y ；visual表示人工魚的感知距離；trynumbers表示每條人工魚最多試探次數(shù)；step表示人工魚移動(dòng)的步長；δ表示擁擠度因子。前面幾個(gè)參數(shù)的取值、函數(shù)的設(shè)置根據(jù)實(shí)際問題確定。

定義2 設(shè)G為人工魚的集合，對(duì)于人工魚X，它的d-距離鄰域是指如果滿足條件：N（X，Y）＝ ｛Y｜D（X，Y）≤d，Y ∈G｝，d為正整數(shù)，則Y為X的一個(gè)鄰居。

定義3 設(shè)q為人工魚X的感知距離內(nèi)可看到的人工魚個(gè)數(shù)，則這q條人工魚X1，X2，… ，Xq的中心位置為：Center（X1，X2，…，Xq）＝ （s1，s2，…，sL），L為人工魚個(gè)體的維數(shù)，θ為設(shè)定的閥值，一般取0.5，其中每個(gè)分量值可表示為：

定義4 食物濃度F的定義為社區(qū)質(zhì)量的評(píng)價(jià)函數(shù)。社區(qū)質(zhì)量評(píng)價(jià)函數(shù)很多，本文為了便于重疊社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)，使用模塊度Q函數(shù)的拓展函數(shù)：

第i條人工魚所處的狀態(tài)Xi的食物濃度為Fi＝f（Xi）。公式（2）中，m 為網(wǎng)絡(luò)邊數(shù)；Oi表示包含節(jié)點(diǎn)i的社區(qū)數(shù)；A為網(wǎng)絡(luò)鄰接矩陣，無向圖中元素值A(chǔ)ij為1表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間有邊，0表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間沒有邊（有向圖中，Aij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的權(quán)重）；ki表示節(jié)點(diǎn)i的度；如果節(jié)點(diǎn)i在社區(qū)c中，σic取值為1，否則為0。

當(dāng)社區(qū)結(jié)構(gòu)不重疊時(shí)式（2）與原Q函數(shù)等價(jià)。式（2）表明網(wǎng)絡(luò)中連接兩個(gè)同種類型節(jié)點(diǎn)邊的比例減去在同樣的社區(qū)結(jié)構(gòu)下任意連接這兩個(gè)節(jié)點(diǎn)的邊的比例的期望值。f（X）越接近1，表示社區(qū)結(jié)構(gòu)越明顯，通常取值在0.3～0.7，表示所得社區(qū)質(zhì)量較好。通過此度量標(biāo)準(zhǔn)可建立起社區(qū)劃分質(zhì)量的全局度量函數(shù)。

2.2 人工魚群算法行為描述

設(shè)Xi表示第i條人工魚的當(dāng)前狀態(tài)，則該狀態(tài)的食物濃度為Fi，下面描述了社區(qū)劃分中人工魚群模型的各種行為：

（1）覓食行為。對(duì)于人工魚Xi所對(duì)應(yīng)的社區(qū)劃分，求食物濃度Fi（即Qov）極大值，在其visual-距離領(lǐng)域內(nèi)隨機(jī)選取一個(gè)狀態(tài)Xj：如果狀態(tài)Xj在可行域內(nèi)且Fj＞Fi，則Xi向Xj方向前進(jìn)一個(gè)step；否則，再重新隨機(jī)選取狀態(tài)Xj，判斷是否滿足前進(jìn)條件；如不滿足，則反復(fù)試trynumbers次后，如果仍不滿足前進(jìn)條件，則在可行域內(nèi)隨機(jī)移動(dòng)一步。

（2）聚集行為。人工魚Xi在其visual-距離領(lǐng)域內(nèi)，如果人工魚群中心位置Xc的食物濃度Fc更大且不擁擠，則Xi移到Xc，否則執(zhí)行覓食行為。

（3）追尾行為。若 Xb為人工魚 Xi在其visual-距離鄰域內(nèi)的最優(yōu)人工魚的狀態(tài)，其食物濃度為Fb，如果Xb所在位置的食物濃度更高且不太擁擠，則Xi向Xb方向移動(dòng)一個(gè)step，否則執(zhí)行覓食行為。

（4）隨機(jī)行為。指人工魚Xi在其visual-距離鄰域內(nèi)隨機(jī)移動(dòng)，這有利于跳出局部最優(yōu)解，而加快社區(qū)劃分全局最優(yōu)解的搜索。

（5）公告板。公告板中記錄了當(dāng)前時(shí)刻具有最優(yōu)質(zhì)量的人工魚的狀態(tài)Xi及其食物濃度Fi。

3 基于人工魚群算法的社區(qū)檢測算法

3.1 AFSCDA描述

算法初始化時(shí)，初始種群為p條人工魚，因?yàn)槊總€(gè)節(jié)點(diǎn)可能同時(shí)屬于多個(gè)社區(qū)，所以每個(gè)節(jié)點(diǎn)i隨機(jī)帶k個(gè)標(biāo)簽，標(biāo)志它的所屬社區(qū)，值為1表示它屬于對(duì)應(yīng)社區(qū)，否則不屬于該社區(qū)。每條人工魚的狀態(tài)尋優(yōu)變量X分量xij確定方法是：每個(gè)節(jié)點(diǎn)i隨機(jī)分配k個(gè)值（0或1），每條人工魚狀態(tài)變量對(duì)應(yīng)一種社區(qū)劃分，即每條人工魚就是一個(gè)解。為了保證這個(gè)解可行性，在執(zhí)行人工魚算法之前，對(duì)每條人工魚的狀態(tài)變量進(jìn)行調(diào)整，但同時(shí)必須有一定的策略確保在初始化隨機(jī)分配社區(qū)時(shí)，節(jié)點(diǎn)應(yīng)該盡可能按照網(wǎng)絡(luò)中連接關(guān)系進(jìn)行合理分配。如兩個(gè)節(jié)點(diǎn)之間存在邊，則在很大概率上這兩個(gè)節(jié)點(diǎn)在同一社區(qū)中，容易想到的做法是每個(gè)節(jié)點(diǎn)按照其鄰接點(diǎn)的社區(qū)情況來調(diào)整其所要加入的社區(qū)號(hào)?；诖怂枷耄仨殞?duì)初始分配的隨機(jī)值進(jìn)行調(diào)整，本文使用 Raghavan［13］提出的標(biāo)簽傳播算法（LPA）對(duì)每條人工魚的狀態(tài)變量分量進(jìn)行調(diào)整，使得每條人工魚能夠代表一個(gè)合理的社區(qū)劃分。

標(biāo)簽傳播算法LPA是半監(jiān)督學(xué)習(xí)算法，利用少量已標(biāo)記的標(biāo)簽去預(yù)測大量未標(biāo)記的標(biāo)簽，具有執(zhí)行速度快、擴(kuò)展性強(qiáng)、性能穩(wěn)定等特點(diǎn)。LPA的原理是每個(gè)節(jié)點(diǎn)分配唯一區(qū)號(hào)標(biāo)簽后（本文每個(gè)節(jié)點(diǎn)i所分配的社區(qū)號(hào)體現(xiàn)在第i段中，如果第j位為1，則j就為該節(jié)點(diǎn)的一個(gè)標(biāo)簽），再對(duì)每個(gè)節(jié)點(diǎn)的標(biāo)簽進(jìn)行調(diào)整。調(diào)整原則是每個(gè)節(jié)點(diǎn)標(biāo)簽與其鄰節(jié)點(diǎn)中相同標(biāo)簽數(shù)最多的一致。Leung等人［15］通過實(shí)驗(yàn)驗(yàn)證了LPA算法在大規(guī)模網(wǎng)絡(luò)上的有效性，但有時(shí)可能導(dǎo)致所有節(jié)點(diǎn)都分配到同一社區(qū)中，或出現(xiàn)社區(qū)規(guī)模很大的情況。為避免這一點(diǎn)，本文使用Leung增加的一個(gè)衰減因子，數(shù)學(xué)模型為：

其中，si（l）表示節(jié)點(diǎn)i上的標(biāo)簽評(píng)分；lj表示節(jié)點(diǎn)j的標(biāo)簽；Ni（l）表示節(jié)點(diǎn)i的鄰節(jié)點(diǎn)中標(biāo)簽為l的節(jié)點(diǎn)集；α為衰減因子，本文α取圖中節(jié)點(diǎn)最大度數(shù)的倒數(shù)。

初始時(shí)每個(gè)節(jié)點(diǎn)的評(píng)分都是1，隨著傳播評(píng)分會(huì)逐漸減小，當(dāng)評(píng)分降低到0時(shí)，這個(gè)標(biāo)簽將無法再傳遞給其他節(jié)點(diǎn)，從而有效避免大社區(qū)的形成。標(biāo)簽調(diào)整從節(jié)點(diǎn)1開始，對(duì)于圖中的每個(gè)節(jié)點(diǎn)v，其中v1，v2，…，vm，v（m＋1），…，vp為v 的鄰節(jié)點(diǎn)，將v的標(biāo)簽設(shè)置為新的標(biāo)簽使用異步函數(shù)：

其中，g函數(shù)返回節(jié)點(diǎn)v的鄰節(jié)點(diǎn)中出現(xiàn)次數(shù)最多的標(biāo)簽，如果這樣的標(biāo)簽存在多個(gè)，則從出現(xiàn)次數(shù)最多的標(biāo)簽中隨機(jī)選一個(gè)；t代迭代過程中節(jié)點(diǎn)i的新標(biāo)簽既和節(jié)點(diǎn)i的鄰節(jié)點(diǎn)t－1代迭代過程中的標(biāo)簽相關(guān)，也和節(jié)點(diǎn)i的鄰節(jié)點(diǎn)在t代迭代過程中的標(biāo)簽相關(guān)。異步方式比同步方式相比只需較少迭代次數(shù)就能趨向平衡，使算法盡早終止，有更好的性能。

基于人工魚群的社區(qū)檢測算法的終止條件是：如果連續(xù)執(zhí)行規(guī)定的迭代次數(shù)GEN 時(shí)公告板上用于表示社區(qū)劃分質(zhì)量Qov的人工魚食物濃度不再提高，或已達(dá)到算法所設(shè)置的最大迭代次數(shù)J，則認(rèn)為近似找到了最優(yōu)的社區(qū)劃分。

算法AFSCDA具體步驟如下：

輸入：社會(huì)網(wǎng)絡(luò)的鄰接矩陣A，待劃分的社區(qū)數(shù)k；

輸出：社區(qū)劃分結(jié)果。

步驟1 初始化魚群算法相關(guān)參數(shù)：魚群的規(guī)模p＝20，人工魚的感知范圍visual和最大移動(dòng)步長step＝1（此值為與當(dāng)前人工魚個(gè)體的海明距離）；擁擠度因子δ＝0.618，trynumbers＝10，GEN ＝10，J＝500，gen＝0，j＝0，N＝0，其中g(shù)en、j、N分別為公告板上食物濃度不變時(shí)的迭代次數(shù)、算法迭代次數(shù)、各人工魚的循環(huán)變量，最優(yōu)個(gè)體bestFish的食物濃度bestFitness＝0，即公告板上的Qov＝0。

步驟2 隨機(jī)產(chǎn)生初始種群，使用Leung改進(jìn)的LPA依次對(duì)每條人工魚的狀態(tài)變量進(jìn)行調(diào)整，保證每條人工魚是一個(gè)合法的社區(qū)劃分。

步驟3 j＋＋，若j＜J，執(zhí)行步驟4，否則執(zhí)行步驟7。

步驟4 計(jì)算各條人工魚當(dāng)前狀態(tài)的食物濃度Qov，將食物濃度最大的人工魚的食物濃度值largeFitness與公告板上記錄的目前最好的人工魚bestFish的bestFitness相比較，如果largeFitness＞bestFitness，則bestFitness＝largeFitness，gen＝0，同時(shí)將該人工魚個(gè)體存入動(dòng)態(tài)數(shù)組bestFish中，轉(zhuǎn)步驟6；若largeFitness＜bestFitness，gen＋＋。

步驟5 若gen＝＝GEN ，則轉(zhuǎn)至步驟7，否則執(zhí)行步驟6。

步驟6 對(duì)每條人工魚依次選擇執(zhí)行聚集、追尾、覓食和隨機(jī)等行為，轉(zhuǎn)步驟3。

步驟7 解碼輸出公告板上的bestFish中的每個(gè)社區(qū)的節(jié)點(diǎn)。

3.2 AFSCDA時(shí)間復(fù)雜度分析

在算法AFSCDA中，基本步驟是調(diào)整初始種群中所有人工魚的狀態(tài)變量，其時(shí)間復(fù)雜度是O（pm），p為魚群規(guī)模，m為網(wǎng)絡(luò)的邊數(shù)，計(jì)算食物濃度Qov時(shí)間復(fù)雜度為O（n＋m），n為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)，基本步驟時(shí)間復(fù)雜度O（pm）為線性時(shí)間。因此，AFSCDA的時(shí)間復(fù)雜度是O（pm＊J），仍為線性時(shí)間，稀疏網(wǎng)絡(luò)為O（n＊J），遠(yuǎn)遠(yuǎn)低于CMP和CONGA。

4 實(shí)驗(yàn)仿真

4.1 數(shù)據(jù)集

本文選擇測試社區(qū)發(fā)現(xiàn)算法常用的三個(gè)代表真實(shí)世界網(wǎng)絡(luò)的數(shù)據(jù)集［1］，Zachary Karate Club、College Football Network和Dolphin Network，這些數(shù)據(jù)集的社區(qū)結(jié)構(gòu)便于驗(yàn)證算法的準(zhǔn)確性。

Zachary Karate Club是 Zachary在研究美國一所大學(xué)空手道俱樂部過程中，發(fā)現(xiàn)管理員和教練關(guān)于某意見發(fā)生了分歧，之后導(dǎo)致管理員和教練各形成一個(gè)新的俱樂部，各自有一半的成員。Zachary構(gòu)造了空手道俱樂部成員之間的友誼網(wǎng)絡(luò)，圖1為該網(wǎng)絡(luò)的實(shí)際劃分情況圖，節(jié)點(diǎn)1和33分別代表管理員和教練。34個(gè)節(jié)點(diǎn)表示成員，78條連接邊表示成員的社會(huì)關(guān)系，使用各種措施來估計(jì)個(gè)人之間的關(guān)系強(qiáng)度，節(jié)點(diǎn)之間有邊意味著相應(yīng)的兩個(gè)成員之間至少是交往頻繁的朋友關(guān)系。

Figure 1 Real partition figure of Karate network圖1 Karate網(wǎng)絡(luò)實(shí)際劃分圖

College Football Network是美國大學(xué)橄欖球隊(duì)模型，源于美國大學(xué)橄欖球聯(lián)賽2000賽季的比賽情況數(shù)據(jù)。聯(lián)賽中有115支球隊(duì)，賽季中要進(jìn)行616場比賽，而聯(lián)賽中有若干個(gè)聯(lián)盟，每個(gè)球隊(duì)都屬于一個(gè)聯(lián)盟，為使每個(gè)隊(duì)平均進(jìn)行7次內(nèi)部比賽，隊(duì)間平均進(jìn)行4次比賽，模型中節(jié)點(diǎn)代表一支球隊(duì)，節(jié)點(diǎn)之間的邊表示其端點(diǎn)代表的兩個(gè)球隊(duì)間要有一場比賽，于是劃分了12個(gè)聯(lián)盟便于管理。

Dolphin Network是關(guān)于生活在新西蘭神奇灣的海豚社會(huì)關(guān)系網(wǎng)絡(luò)，網(wǎng)絡(luò)中有62個(gè)節(jié)點(diǎn)、159條邊，其中節(jié)點(diǎn)表示每只海豚，邊是科學(xué)家經(jīng)過幾年時(shí)間的觀察建立的這些海豚之間的社會(huì)關(guān)系，在觀察期間由于一只關(guān)鍵海豚離開而自動(dòng)地分化為兩個(gè)較小的群體。

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

表1為Karate網(wǎng)絡(luò)上的一次實(shí)驗(yàn)重疊社區(qū)劃分結(jié)果。用已有社區(qū)檢測算法劃分它，節(jié)點(diǎn)3、9、10、14、20、31所在的社區(qū)與實(shí)際有時(shí)不一致。AFSCDA算法實(shí)驗(yàn)多次時(shí)這些節(jié)點(diǎn)一個(gè)或兩個(gè)會(huì)出現(xiàn)在重疊社區(qū)中，經(jīng)分析，這些節(jié)點(diǎn)屬于兩個(gè)社區(qū)的程度基本相同，所以被兩個(gè)社區(qū)共享是合理的。例如，節(jié)點(diǎn)10與兩個(gè)社區(qū)各有一個(gè)連接邊，這樣把10劃分到哪個(gè)社區(qū)都合理，多次實(shí)驗(yàn)中10為重疊節(jié)點(diǎn)的次數(shù)較多。

Table 1 Result of AFSCDA in overlapping community partition表1 AFSCDA對(duì)Karate網(wǎng)絡(luò)重疊社區(qū)一次劃分結(jié)果

本文采用規(guī)范化互信息［16］對(duì)算法所劃分的社區(qū)進(jìn)行評(píng)價(jià)：

其中，M是一個(gè)二維矩陣，元素Mij表示真實(shí)社區(qū)i與算法劃分得到的社區(qū)j交集的基，M·j＝

I（Pr，Pf）表示算法得到的社區(qū)劃分與真實(shí)劃分差異的一個(gè)度量，其值越接近1，表示算法得到的社區(qū)劃分結(jié)果越準(zhǔn)確。

表2、表3分別為本文算法AFSCDA在上述三個(gè)測試集上所得劃分的Qov、I（Pr，Pf）對(duì)比表，分別從Qov和I（Pr，Pf）兩方面比較AFSCDA算法、CMP算法和CONGA算法。

Table 2 Several kinds of algorithm about Qovcontrast table表2 幾種算法關(guān)于Qov的對(duì)比表

Table 3 Several kinds of algorithm about I（pr，pf）contrast table表3 幾種算法關(guān)于I（pr，pf）的對(duì)比表 %

基于統(tǒng)計(jì)意義的考慮，對(duì)AFSCDA算法在三個(gè)數(shù)據(jù)集上重復(fù)進(jìn)行50次實(shí)驗(yàn)，表中結(jié)果是50次實(shí)驗(yàn)結(jié)果的平均值，可以看出Qov值高于其他兩個(gè)算法，表示劃分質(zhì)量要更高；I（Pr，Pf）不低于其他算法，表明AFSCDA算法對(duì)三個(gè)數(shù)據(jù)集上的社區(qū)劃分結(jié)果與真實(shí)社區(qū)相一致的程度不低于其他算法，驗(yàn)證了將人工魚群算法應(yīng)用到重疊社區(qū)劃分中的可行性和有效性。

仿真實(shí)驗(yàn)表明，對(duì)于Karate網(wǎng)絡(luò)，劃分出的重疊社區(qū)結(jié)構(gòu)和實(shí)際的社區(qū)結(jié)構(gòu)相比較合理，其他兩個(gè)網(wǎng)絡(luò)劃分的社區(qū)結(jié)構(gòu)質(zhì)量也不低于CMP算法和CONGA算法的運(yùn)行效果。

5 結(jié)束語

本文針對(duì)CMP算法的k值難以確定、CONGA算法在大型網(wǎng)絡(luò)中效率低的情況，提出了基于并行處理思想的人工魚群社區(qū)發(fā)現(xiàn)算法，用標(biāo)簽傳播方法對(duì)節(jié)點(diǎn)編碼調(diào)整，以避免不合理社區(qū)的產(chǎn)生，同時(shí)將模塊度優(yōu)化函數(shù)的變形用于衡量社區(qū)質(zhì)量，并應(yīng)用互信息度量劃分社區(qū)的效果。實(shí)驗(yàn)表明，本文所提算法是有效的、可行的，AFSCDA為重疊社區(qū)檢測的研究提供了新的方向。

［1］ Girvan M，Newman M E J.Community structure in social and biological networks［J］.PNAS，2001，99（12）：7821-7826.

［2］ Pothen A，Simon H，Liou K P.Partitioning sparse matrices with eigenvectors of graphs［J］.SIAM Journal on Matrix A-nalysis and Applications，1990，11（3）：430-452.

［3］ Kernighan B W，Lin S.An efficient heuristic procedure for portioning graphs［J］.Bell System Technical Journal，1970，49：291-307.

［4］ Palla G，Derenyi I，F(xiàn)arkas I，et al.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature，2005，435（7043）：814-818.

［5］ Wu F，Huberman B A.Finding communities in linear time：A physics approach［J］.European Physical Journal B，2004，38（2）：331-338.

［6］ Newman M E J.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69（6）：066133.

［7］ Tyler J，Wilkinson D，Huberman B.Email as spectroscopy：Automated discovery of community structure within organizations［C］∥Proc of International Conference on Communities and Technologies，2003：81-96.

［8］ Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69（2）：026113.

［9］ Clauset A，Newman M E J，Moore C.Finding community structure in very large networks［J］.Physical Review E，2004，E70：066111.

［10］ Dhilion S，Mallela S，Modha D S.Information-theoretic co-clustering［C］∥Proc of Knowledge Discovery in Databases，2003：89-98.

［11］ Li Xiao-lei，Shao Zhi-jiang，Qian Ji-xin.An optimizing method based on autonomous animats：Fish-swarm algorithm［J］.Systems Engineering-Theory ＆ Practice，2002，22（11）：32-38.（in Chinese）

［12］ Li Xiao-lei，Lu fei，Tian guo-hui，et al.Applications of artificial fish school algorithm in combinatorial optimization problems［J］.Journal of Shandong University，2004，43（5）：64-67.（in Chinese）

［13］ Raghavan 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.

［14］ Strehl A，Ghosh J.Cluster ensembles：A knowledge reuse framework combing multiple partitions［J］.Journal of Machine Learning Research，2003，3（3）：583-617.

［15］ Leung I X Y，Pan Hui，Liò，et al.Towards real-time community detection in large networks［J］.Physical Review E，2009，79（6）：066107.

［16］ Strehl A，Ghosh J.Cluster ensembles：A knowledge reuse framework combing multiple partions［J］.Journal of Machine Learning Research，2003，3：583-617.

附中文參考文獻(xiàn)：

［11］ 李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚群算法［J］.系統(tǒng)工程理論與實(shí)踐，2002，22（11）：32-38.

［12］ 李曉磊，路飛，田國會(huì)，等.組合優(yōu)化問題的人工魚群算法應(yīng)用［J］.山東大學(xué)學(xué)報(bào)，2004，43（5）：64-67.