李艷靈，劉先省

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

0 引言

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

盡管網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的概念非常簡單，但是構(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é)點確定的隸屬于一個社團(tuán).但是現(xiàn)實世界中，網(wǎng)絡(luò)中的節(jié)點可以同時隸屬于不同的社團(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).最后通過實驗驗證文章所提算法的有效性.

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

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

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

v=const.

(1)

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

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

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

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

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

σ=260(1-cosθ),

(5)

μ=620(1-cosθ),

(6)

cosθ=e-τcτpr,

(7)

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果分析

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

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

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

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

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

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

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

4 結(jié)語

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