李艷靈，劉先省

(1.河南大學(xué) 環(huán)境規(guī)劃學(xué)院， 河南 開封 475004;2.信陽師范學(xué)院 計(jì)算機(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é)點(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ò)按照相似的研究課題分類;社會網(wǎng)絡(luò)按照興趣愛好、職業(yè)進(jìn)行分類.因此網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)能力對于實(shí)際應(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é)點(diǎn)確定的隸屬于一個社團(tuán).但是現(xiàn)實(shí)世界中，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以同時隸屬于不同的社團(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).最后通過實(shí)驗(yàn)驗(yàn)證文章所提算法的有效性.

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

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

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

v=const.

(1)

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

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

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

(3)計(jì)算新的運(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)計(jì)算細(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àn)來尋找最優(yōu)值，因此該算法有如下的缺陷:第一，單個細(xì)菌必須在解空間中通過搜索不同的點(diǎn)以修正和模擬其形成的梯度信息，因此，在很多問題上，BC算法的優(yōu)化速度慢;第二，當(dāng)函數(shù)的梯度變化小于一定的值時，細(xì)菌個體將無法得到合適的梯度信息，從而進(jìn)入隨機(jī)搜索.隨著精度的提高，BC算法的搜索范圍將很難保證限定在全局最優(yōu)解的附近.為此，我們提出細(xì)菌群體趨藥性算法(Bacterial colony chemotaxis, BCC).該算法引入精英保持策略，該策略保證了BCC的執(zhí)行效率，并且避免丟棄那些具有較好位置的點(diǎn).經(jīng)過若干步后，具有較差位置的節(jié)點(diǎn)向較好位置的點(diǎn)移動.公式如下：

其中，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)之間的非類同指數(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)的度.非類同指數(shù)定義為：

其中|Sk|為社團(tuán)中的節(jié)點(diǎn)個數(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)就是為了揭示不同類型復(fù)雜網(wǎng)絡(luò)中存在的真實(shí)社團(tuán)結(jié)構(gòu).為了定量地刻畫社團(tuán)發(fā)現(xiàn)算法，2004年Newman等[9]提出了網(wǎng)絡(luò)模塊性評價函數(shù)——模塊度(Q)，其定義如下：

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

為驗(yàn)證本文所提算法的有效性，將該算法用于簡單網(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é)點(diǎn).

圖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é)果.該俱樂部的主管與校長之間因是否提高俱樂部收費(fèi)的問題產(chǎn)生了爭執(zhí).結(jié)果，該俱樂部分裂成了兩個分別以主管和校長為核心的小俱樂部.圖2中方形節(jié)點(diǎn)與圓形節(jié)點(diǎn)代表實(shí)際分裂而成的兩個小俱樂部，而陰影和非陰影代表應(yīng)用本文算法得到社團(tuán)劃分結(jié)果.

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

圖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àn)知識即可有效地確定最優(yōu)的社團(tuán)個數(shù)和每個社團(tuán)的中心點(diǎn).如何將模糊聚類和其他群體智能算法進(jìn)行結(jié)合，并用于探測復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)是值得進(jìn)一步研究的課題.