李艷靈，劉先省

(1.河南大學(xué) 環(huán)境規(guī)劃學(xué)院， 河南 開(kāi)封 475004;2.信陽(yáng)師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院, 河南 信陽(yáng) 464000)

0 引言

近年來(lái)，對(duì)復(fù)雜網(wǎng)絡(luò)性能的研究與理解，特別是對(duì)交通運(yùn)輸網(wǎng)、社交網(wǎng)絡(luò)、萬(wàn)維網(wǎng)、論文引用網(wǎng)絡(luò)的研究與理解日益重要[1-3].復(fù)雜網(wǎng)絡(luò)的重要特征之一是社團(tuán)結(jié)構(gòu).同一社團(tuán)內(nèi)部節(jié)點(diǎn)之間聯(lián)系緊密，不同社團(tuán)之間節(jié)點(diǎn)聯(lián)系稀疏.由于社團(tuán)結(jié)構(gòu)影響著組織的重要功能，因此社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)非常重要.例如,論文引用網(wǎng)絡(luò)按照相似的研究課題分類(lèi);社會(huì)網(wǎng)絡(luò)按照興趣愛(ài)好、職業(yè)進(jìn)行分類(lèi).因此網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)能力對(duì)于實(shí)際應(yīng)用具有重要的影響，并有助于我們理解網(wǎng)絡(luò)系統(tǒng).

盡管網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的概念非常簡(jiǎn)單，但是構(gòu)造有效的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法卻十分困難.為此，研究者們提出了一系列的算法[4-6]，取得了一定的效果.但是，目前大多數(shù)算法將復(fù)雜網(wǎng)絡(luò)中的關(guān)系確定化，這種方法強(qiáng)調(diào)網(wǎng)絡(luò)中的節(jié)點(diǎn)確定的隸屬于一個(gè)社團(tuán).但是現(xiàn)實(shí)世界中，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以同時(shí)隸屬于不同的社團(tuán).因此本文提出基于模糊均值的細(xì)菌群體趨藥性復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法.首先利用細(xì)菌群體趨藥性算法獲得模糊均值算法的初值，然后利用模糊C均值算法進(jìn)行社團(tuán)結(jié)構(gòu)發(fā)現(xiàn).最后通過(guò)實(shí)驗(yàn)驗(yàn)證文章所提算法的有效性.

1 細(xì)菌群體趨藥性算法

細(xì)菌趨藥性算法[7](Bacterial chemotaxis, BC)是新近提出的一種隨機(jī)梯度優(yōu)化算法.該算法只依賴于單個(gè)細(xì)菌的運(yùn)動(dòng)行為，通過(guò)不斷地感受其周?chē)h(huán)境的變化和只利用其過(guò)去的經(jīng)驗(yàn)尋找最優(yōu)點(diǎn).BC算法把單個(gè)細(xì)菌當(dāng)作是一個(gè)受其周?chē)h(huán)境影響而改變位置的個(gè)體，并且利用感知的信息改變細(xì)菌的移動(dòng)軌跡，并且在移動(dòng)過(guò)程中不斷修正前進(jìn)的角度和移動(dòng)的距離，以找到目標(biāo)函數(shù)的最優(yōu)值.算法步驟如下：

(1)計(jì)算細(xì)菌的移動(dòng)速度，假設(shè)其為常數(shù)；

v=const.

(1)

(2)計(jì)算細(xì)菌在新方向上的移動(dòng)時(shí)間τ，τ的值由概率分布決定：

其中T由下式?jīng)Q定：

其中T0是最小平均移動(dòng)時(shí)間，fpr為當(dāng)前點(diǎn)與上一個(gè)點(diǎn)之間的函數(shù)值的差，lpr為變量空間中連接當(dāng)前點(diǎn)和上一個(gè)點(diǎn)的向量的模，b是與參數(shù)無(wú)關(guān)的參數(shù).

(3)計(jì)算新的運(yùn)動(dòng)方向.原來(lái)軌跡和新方向之間的夾角根據(jù)新方向向左或向右偏轉(zhuǎn)分別服從以下兩個(gè)高斯概率分布：

其中，其方差和期望分別由下式?jīng)Q定：當(dāng)fpr/lpr<0時(shí)，

σ=260(1-cosθ),

(5)

μ=620(1-cosθ),

(6)

cosθ=e-τcτpr,

(7)

其中:τc為相關(guān)時(shí)間，τpr為細(xì)菌上一運(yùn)動(dòng)軌跡的持續(xù)時(shí)間.

(4)計(jì)算細(xì)菌在變量空間中的新位置：

上述算法中，T0,b,τc,v是需要設(shè)定的系統(tǒng)參數(shù).優(yōu)化過(guò)程中對(duì)參數(shù)的自適應(yīng)調(diào)整可以加速尋優(yōu)的過(guò)程.

BC算法作為一種隨機(jī)梯度搜索方法，具有一定的避免算法陷入局部?jī)?yōu)化的能力，并且該算法能夠防止算法過(guò)早收斂.然而，由于BC算法不是基于群體智能的優(yōu)化算法，它只依賴于單個(gè)細(xì)菌的運(yùn)動(dòng)行為，不斷感受其周?chē)h(huán)境的改變，并且只利用它過(guò)去的經(jīng)驗(yàn)來(lái)尋找最優(yōu)值，因此該算法有如下的缺陷:第一，單個(gè)細(xì)菌必須在解空間中通過(guò)搜索不同的點(diǎn)以修正和模擬其形成的梯度信息，因此，在很多問(wèn)題上，BC算法的優(yōu)化速度慢;第二，當(dāng)函數(shù)的梯度變化小于一定的值時(shí)，細(xì)菌個(gè)體將無(wú)法得到合適的梯度信息，從而進(jìn)入隨機(jī)搜索.隨著精度的提高，BC算法的搜索范圍將很難保證限定在全局最優(yōu)解的附近.為此，我們提出細(xì)菌群體趨藥性算法(Bacterial colony chemotaxis, BCC).該算法引入精英保持策略，該策略保證了BCC的執(zhí)行效率，并且避免丟棄那些具有較好位置的點(diǎn).經(jīng)過(guò)若干步后，具有較差位置的節(jié)點(diǎn)向較好位置的點(diǎn)移動(dòng).公式如下：

其中，rand()是(0,2)內(nèi)的正態(tài)分布.

2 基于模糊均值的細(xì)菌群體趨藥性復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法

2.1 相似性度量方法

文獻(xiàn)[8]中，定義了節(jié)點(diǎn)之間的非類(lèi)同指數(shù)，該指數(shù)用于網(wǎng)絡(luò)中節(jié)點(diǎn)之間接近程度的度量.復(fù)雜網(wǎng)絡(luò)可以表示成圖G(S,E)，其中S是節(jié)點(diǎn)的集合,E={e(x,y)}x,y∈S為帶權(quán)矩陣，e(x,y)為連接節(jié)點(diǎn)x和y的邊的權(quán)值.將復(fù)雜網(wǎng)絡(luò)描述成含隨機(jī)矩陣P=(p(x,y))的離散馬爾科夫鏈如下：

其中d(x)為節(jié)點(diǎn)的度.非類(lèi)同指數(shù)定義為：

其中|Sk|為社團(tuán)中的節(jié)點(diǎn)個(gè)數(shù).

2.2 基于模糊均值的細(xì)菌群體趨藥性社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法

復(fù)雜網(wǎng)絡(luò)中的社團(tuán)內(nèi)部節(jié)點(diǎn)之間聯(lián)系稠密，社團(tuán)之間節(jié)點(diǎn)聯(lián)系稀疏.社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)就是為了揭示不同類(lèi)型復(fù)雜網(wǎng)絡(luò)中存在的真實(shí)社團(tuán)結(jié)構(gòu).為了定量地刻畫(huà)社團(tuán)發(fā)現(xiàn)算法，2004年Newman等[9]提出了網(wǎng)絡(luò)模塊性評(píng)價(jià)函數(shù)——模塊度(Q)，其定義如下：

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

為驗(yàn)證本文所提算法的有效性，將該算法用于簡(jiǎn)單網(wǎng)絡(luò)和Zachary空手道俱樂(lè)部網(wǎng)絡(luò).圖1(取自文獻(xiàn)[10])為具有明顯3個(gè)社團(tuán)結(jié)構(gòu)的簡(jiǎn)單網(wǎng)絡(luò)，網(wǎng)絡(luò)中包含19個(gè)節(jié)點(diǎn).

圖1 三社團(tuán)網(wǎng)絡(luò)Fig. 1 Network with three communities

應(yīng)用本文算法對(duì)該簡(jiǎn)單網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，分別得到聚類(lèi)數(shù)k={1,2,3,4,5,6}對(duì)應(yīng)的模塊度值Q={0,0.159,0.574,0.441,0.344,0.335}.可知當(dāng)網(wǎng)絡(luò)被劃分三個(gè)社團(tuán)時(shí)，對(duì)應(yīng)的模塊度值Q達(dá)到最大，因此，網(wǎng)絡(luò)的最優(yōu)社團(tuán)劃分是聚類(lèi)數(shù)k=3所對(duì)應(yīng)的社團(tuán)劃分結(jié)果.

圖2是著名的Zachary空手道俱樂(lè)部網(wǎng)絡(luò)最終的劃分結(jié)果.該俱樂(lè)部的主管與校長(zhǎng)之間因是否提高俱樂(lè)部收費(fèi)的問(wèn)題產(chǎn)生了爭(zhēng)執(zhí).結(jié)果，該俱樂(lè)部分裂成了兩個(gè)分別以主管和校長(zhǎng)為核心的小俱樂(lè)部.圖2中方形節(jié)點(diǎn)與圓形節(jié)點(diǎn)代表實(shí)際分裂而成的兩個(gè)小俱樂(lè)部，而陰影和非陰影代表應(yīng)用本文算法得到社團(tuán)劃分結(jié)果.

圖3給出了不同聚類(lèi)數(shù)k下相應(yīng)的模塊度值Q，可知Zachary空手道俱樂(lè)部網(wǎng)絡(luò)被劃分成兩個(gè)社團(tuán)為最終的社團(tuán)劃分結(jié)果.可見(jiàn)本文算法具有更高的準(zhǔn)確率，而且把有歧義的3號(hào)節(jié)點(diǎn)同樣正確劃分.

圖2 Zachary空手道俱樂(lè)部網(wǎng)絡(luò)Fig. 2 Zachary’s karate club network

圖3 網(wǎng)絡(luò)劃分為k個(gè)社團(tuán)時(shí)所對(duì)應(yīng)的模塊度值Fig. 3 Modularity of network with k community structures

4 結(jié)語(yǔ)

本文提出基于模糊均值的細(xì)菌群體趨藥性算法用于復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn).該算法解決了復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)中的模糊性和不確定性問(wèn)題.新算法中，無(wú)須關(guān)于社團(tuán)結(jié)構(gòu)的先驗(yàn)知識(shí)即可有效地確定最優(yōu)的社團(tuán)個(gè)數(shù)和每個(gè)社團(tuán)的中心點(diǎn).如何將模糊聚類(lèi)和其他群體智能算法進(jìn)行結(jié)合，并用于探測(cè)復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)是值得進(jìn)一步研究的課題.