楊忠保，楚楊杰，洪 葉，江登英

(1.黔南民族師范學(xué)院數(shù)學(xué)統(tǒng)計學(xué)院，貴州 都勻 558000；2.武漢理工大學(xué)理學(xué)院,武漢430070)

0 引言

社區(qū)結(jié)構(gòu)是指網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中表現(xiàn)出來的社團(tuán)化特征，整個網(wǎng)絡(luò)由若干個社團(tuán)構(gòu)成。社區(qū)內(nèi)部連接緊密，社區(qū)與社區(qū)之間連接比較稀疏[1]。社區(qū)發(fā)現(xiàn)對研究網(wǎng)絡(luò)結(jié)構(gòu)有重要的應(yīng)用價值，社區(qū)發(fā)現(xiàn)致力于有效地尋找到網(wǎng)絡(luò)中準(zhǔn)確的社區(qū)結(jié)構(gòu)[2]，靜態(tài)網(wǎng)絡(luò)環(huán)境下，網(wǎng)絡(luò)中的非重疊社區(qū)發(fā)現(xiàn)算法，大約分為三類：劃分的非重疊社區(qū)發(fā)現(xiàn)算法，優(yōu)化的非重疊社區(qū)發(fā)算法和其他非重疊社區(qū)發(fā)現(xiàn)算法。經(jīng)典的劃分的非重疊社團(tuán)挖掘算法,如GN算法。然而優(yōu)化的非重疊社區(qū)發(fā)算法中，其經(jīng)典算法是遺傳方法(GA-net)[3]；多目標(biāo)遺傳方法(MOGA-net)[4]；離散粒子群方法(DPSO)[5]；多目標(biāo)離散粒子群方法(MODPSO)[6]；多目標(biāo)量子粒子群方法(QDM-PSO)[7]。遺傳算法優(yōu)化社區(qū)發(fā)現(xiàn)算法將網(wǎng)絡(luò)的節(jié)點與遺傳算法中的遺傳基因相映射，而(量子)粒子群優(yōu)化社區(qū)發(fā)現(xiàn)算法將網(wǎng)絡(luò)的節(jié)點與算法中的粒子相映射。社區(qū)發(fā)現(xiàn)算法從不同角度出發(fā)，結(jié)合復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，解決復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題。

社區(qū)發(fā)現(xiàn)算法對初始節(jié)點的位置敏感，如果初始節(jié)點處于社區(qū)邊緣，那么效果差，反之，則效果較好，這導(dǎo)致算法穩(wěn)定性較差。算法的收斂條件缺乏自適應(yīng)性，從網(wǎng)絡(luò)的種子節(jié)點度出發(fā)，每次更新社區(qū)節(jié)點只需用到社區(qū)內(nèi)部節(jié)點和邊緣節(jié)點的鄰節(jié)點的信息，算法的時間復(fù)雜度較低，但因沒考慮全局信息，容易受種子節(jié)點影響，這導(dǎo)致算法精度不是很高。本文采用一種離散量子粒子群優(yōu)化算法的社區(qū)發(fā)現(xiàn)(NQD-PSO)，將核心節(jié)點與鄰居的普通節(jié)點構(gòu)成模體，該模體為量子粒子群算法的初始值。本文利用了三角形模體來判斷社區(qū)的穩(wěn)定性度量問題，從而量化社區(qū)結(jié)構(gòu)穩(wěn)定性。同時，采用壓縮因子函數(shù)調(diào)節(jié)全局和局部搜索模型，結(jié)合量子粒子群算法，使該算法全局收斂。模擬和真實數(shù)據(jù)集上的實驗結(jié)果均表明，相比于其他算法，NQD-PSO算法可以挖掘更高質(zhì)量的社區(qū)結(jié)構(gòu)。

1 基本概念

含權(quán)的復(fù)雜網(wǎng)絡(luò)G=(V,E,W)中，V={vij|i,j=1,2,…,n}表示網(wǎng)絡(luò)中的節(jié)點集合，E={eij|i,j=1,2,…,n}表示網(wǎng)絡(luò)中的邊集合，W={wij|i,j=1,2,…,n}表示網(wǎng)絡(luò)中的邊權(quán)集合,其中，wij∈{pr,nr}表示相關(guān)系數(shù)，如果兩個節(jié)點的相關(guān)系數(shù)為正數(shù)，pr為正相關(guān)系數(shù)，如果兩個節(jié)點的相關(guān)系數(shù)為負(fù)數(shù)，nr為負(fù)相關(guān)系數(shù)。網(wǎng)絡(luò)中有節(jié)點數(shù)為n，邊數(shù)為m，如果節(jié)點vi與節(jié)點vj中間有邊相接，則eij=1，否則，eij=0，所以節(jié)點vi的度ki表示為：ki=∑vj∈Veij。節(jié)點vi的點權(quán)si定義為與節(jié)點i關(guān)聯(lián)的邊權(quán)之和，也稱為點強(qiáng)度。

定義2節(jié)點vi與節(jié)點vj的共同鄰居定義為

Cij=neighbor(vi)∩neighbor(vj)

(1)

其中，neighbor(vi)表示核心節(jié)點vi的鄰居節(jié)點集。網(wǎng)絡(luò)的模體結(jié)構(gòu)介于節(jié)點與社區(qū)結(jié)構(gòu)之間，少數(shù)幾個節(jié)點連接構(gòu)成(共同鄰居)，模體是社區(qū)內(nèi)部成員之間基本的連接模式,，是網(wǎng)絡(luò)中一種重要的結(jié)構(gòu)特征。模體作為網(wǎng)絡(luò)的一種連續(xù)基元，基元(節(jié)點與模體)是網(wǎng)絡(luò)的基本組成部分，它能揭示網(wǎng)絡(luò)的演化規(guī)律。

定義3設(shè)核心節(jié)點的標(biāo)簽集為：Ω(t)=(v1,v2,…,vk);則最大核心節(jié)點的度定義為：

(2)

(3)

其中，vt為核心節(jié)點，則kt,st分別表示重新排序后的節(jié)點度和點強(qiáng)度。核心節(jié)點對網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的運行具有主導(dǎo)的作用。網(wǎng)絡(luò)中的節(jié)點的重要程度不同，核心節(jié)點具有較高重要性，而普通節(jié)點則是網(wǎng)絡(luò)中的參與者。社區(qū)是由核心節(jié)點和追隨的普通節(jié)點構(gòu)成，劃分網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，必須要找出網(wǎng)絡(luò)社區(qū)的核心節(jié)點。如果這樣單純依賴排序結(jié)果，選擇初始核心節(jié)點會帶來潛在風(fēng)險，多個核心節(jié)點可能在相同社區(qū)，按從大到小的選擇，可能會把一個大的社區(qū)分解為若個小社區(qū)；為了避免這些問題，在核心節(jié)點選擇上附加一些約束：為了避免核心節(jié)點與外界節(jié)點連接較少，選擇核心節(jié)點的點強(qiáng)度必須大于網(wǎng)絡(luò)中所有的節(jié)點的平均點強(qiáng)度。先后選出的若干個網(wǎng)絡(luò)的模體在同一社區(qū)，當(dāng)前選擇的模體必須和已有模體是相鄰的。核心節(jié)點與普通節(jié)點相連接構(gòu)成模體，把網(wǎng)絡(luò)劃分為k個模體，記為G={u1,u2,…,uk}且ui∩uj=φ。

圖1 NQD-PSO算法流程圖Fig.1 Flow chart of NQD-PSO

2 量子粒子群優(yōu)化社區(qū)發(fā)現(xiàn)方法

本文以量子粒子群優(yōu)化算法為背景知識解決網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題，將核心節(jié)點和鄰居的普通節(jié)點構(gòu)成的模體當(dāng)作量子粒子群的粒子，通過量子粒子群算法來改變粒子位置的歸屬，旨在挖掘出高質(zhì)量的社區(qū)結(jié)構(gòu)。下面是NQD-PSO算法流程圖，如圖1所示。

NQD-PSO算法的第1行至第2行屬于核心節(jié)點的模體從網(wǎng)絡(luò)中劃分出來；第3行至第16行屬于量子粒子群優(yōu)化社區(qū)發(fā)現(xiàn)方法，其中，第5行至第14行屬于算法的循環(huán)過程，第10行屬于社區(qū)擴(kuò)展過程，第13行屬于模體獨立構(gòu)成新的社區(qū)。時間復(fù)雜度分析：n表示網(wǎng)絡(luò)節(jié)點數(shù)目，m表示社區(qū)結(jié)構(gòu)的數(shù)目，k表示網(wǎng)絡(luò)中的模體的數(shù)目。NQD-PSO算法的第1行至第2行用時間為O(n)，第3行至第16行屬于量子粒子群優(yōu)化社區(qū)發(fā)現(xiàn)過程，其中，粒子解碼用時間為O(k)，循環(huán)過程用時間為O(m·k)，粒子種群為p，迭代次數(shù)為g。則NQD-PSO算法時間復(fù)雜度為：O(gplog(m+m·k+n))。NQD-PSO算法流程框架如表1所示。

2.1 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是測量網(wǎng)絡(luò)拓?fù)湫缘哪繕?biāo)函數(shù)，它是依賴于社區(qū)的三角形模體(三個節(jié)點的模體)決定該社區(qū)的穩(wěn)定性，從而量化社區(qū)結(jié)構(gòu)質(zhì)量。該系數(shù)與適應(yīng)度系數(shù)的關(guān)系，即構(gòu)造模體加權(quán)社區(qū)聚類定義如下[10]：

(4)

其中，t(u,NP)表示模體u與節(jié)點集合NP構(gòu)成三角形模體的數(shù)目；vt(u,V)表示模體u與節(jié)點集合V至少構(gòu)成一個三角形模體的節(jié)點數(shù)目；|NPu|表示節(jié)點集合NP除去節(jié)點u的模體的數(shù)目。

2.2 粒子群算法基本原理

本文采用的是壓縮函數(shù)代替加速因子[11]，主要調(diào)節(jié)全局和局部搜索模型。離散粒子群算法的粒子位置更新如下：

(5)

其中，sigmoid(x)為壓縮因子函數(shù)定義：

(6)

(7)

2.3 量子粒子群更新規(guī)則

為了避免粒子群算法收斂于局部極值，結(jié)合量子粒子群[12]，量子粒子群更新策略保證全局收斂。粒子平均最優(yōu)位置更新策略數(shù)學(xué)描述如下：

(8)

(9)

(10)

2.4 粒子編碼與解碼

粒子編碼采用NQD-PSO中基于模體鄰居的有序表的編碼方法。計算各個模體的適應(yīng)性函數(shù)，選擇模體合并或分離。如果兩個模體合并，那么加權(quán)社區(qū)聚類函數(shù)的值會增加，反之，兩個模體會分離。采用字符串編碼方式來表示社區(qū)標(biāo)簽，其初始標(biāo)簽為NP(i)(i=1,2,…,k)，設(shè)NP(1)=1，如果NP(1)=NP(2)，社區(qū)與模體合并。如果NP(1)≠NP(2)，那么NP(2)=2，模體獨立成社區(qū)，以此類推，如果此時為k時是算法最大社區(qū)標(biāo)簽值才結(jié)束。如圖2中，選擇節(jié)點1與節(jié)點7為核心節(jié)點。確定模體數(shù)目，如果核心節(jié)點1與節(jié)點2，3，4，8相連，構(gòu)成模體，則核心節(jié)點1的鄰居節(jié)點集合為{2,3,4,8}；則該模體的加權(quán)社區(qū)聚類函數(shù)的值為：5/7。另一個模體的加權(quán)社區(qū)聚類為：1.兩個模體合并后，加權(quán)社區(qū)聚類函數(shù)的值會減少，所以分離成為兩個社區(qū)，不同社區(qū)的節(jié)點所屬的顏色不同。這樣的編碼方式可以保證每一個粒子都是有效的。解碼步驟是將編號進(jìn)行排序形成鄰居有序表，將該表轉(zhuǎn)化為與圖相應(yīng)的社區(qū)結(jié)構(gòu)，保證參與到同一個組中的節(jié)點被分配在一個集合中[13]。解碼操作可以在線性時間內(nèi)完成。該表示方法的主要優(yōu)點：社區(qū)的數(shù)目將在解碼時自動確定；避免非法粒子產(chǎn)生，能減少優(yōu)化問題中的約束條件，并且保證社區(qū)結(jié)構(gòu)的穩(wěn)定性。對粒子的編碼和解碼操作如圖2所示。

圖2 粒子編碼方式和解碼方式Fig.2 Particle′s coding and idecoding

3 實驗結(jié)果與分析

實證量子粒子群優(yōu)化算法的社區(qū)發(fā)現(xiàn)算法的性能評價，實驗環(huán)境設(shè)置為：windows 7操作系統(tǒng)，AMD A-82.10GHz,500GB內(nèi)存。根據(jù)量子粒子群算法參數(shù)實驗設(shè)置可知：它的控制參數(shù)β采用固定值：0.6或0.8時，對多數(shù)函數(shù)取得較好的優(yōu)化結(jié)果[12]；控制參數(shù)β的變化對規(guī)范互信息量和模塊度沒有影響[7]。所以本文控制參數(shù)β采用固定值為0.8.設(shè)置實驗參數(shù)與QDM-PSO算法相同，方便對比算法性能，實驗參數(shù)設(shè)為：N=Tmax=100,c1=c2=2,η1=η2=0.15，所有的算法均在Matlab(R2010b)編碼實現(xiàn)，各種算法的結(jié)果為運行50次取平均值。

3.1 評價標(biāo)準(zhǔn)

采用2種常用的社區(qū)發(fā)現(xiàn)算法評價指標(biāo)，包括規(guī)范互信息量(normalized mutual information,NMI)和模塊度(modularity)。

規(guī)范互信息量用來描述劃分結(jié)果與真實結(jié)構(gòu)之間的相關(guān)性，它的取值范圍為[01]，NMI的值越接近1表示劃分結(jié)果越好。數(shù)學(xué)描述如下：

(11)

其中，A表示真實網(wǎng)絡(luò)社區(qū)；B表示實驗得到的社區(qū)；cA與cB分別表示真實網(wǎng)絡(luò)社區(qū)個數(shù)和實驗得到的社區(qū)個數(shù)；N是混淆矩陣，Nij代表了ci(ci?cA)和cj(cj?cB)的公共節(jié)點數(shù)，Ni.與N.j分別代表該矩陣中第i行和第j列中的元素的和，且Nt=∑i∑jNij.

模塊度用來對社區(qū)劃分的整體質(zhì)量做出一個定量的評價，根據(jù)正負(fù)相關(guān)的邊權(quán)情況，采取合適性能的模塊度，根據(jù)文獻(xiàn)[14]改進(jìn)定義如下：

(12)

3.2 算法比較結(jié)果評價

N=128,k=kmax=16,u=0.1,cmin=cmax=32,On=Om=0

這就是生成Girvan和Newman所提出的GN基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)[16]，該數(shù)據(jù)集含有節(jié)點128個，含有1024條邊，而每個節(jié)點的平均點強(qiáng)度為8和平均度數(shù)為16，將所有的節(jié)點平均的劃分成4個社區(qū)，每個社區(qū)中含有32個節(jié)點。真實數(shù)據(jù)集的基本信息如下表：

表2 5個真實數(shù)據(jù)集的基本信息[6]Tab.2 Basic information for 5 real data sets[6]

網(wǎng)絡(luò)中含有一個模糊參數(shù)u，表示為任一節(jié)點vi與社區(qū)外節(jié)點vj形成的鏈接占節(jié)點vi之度的比率，每個節(jié)點vi和同一個社區(qū)內(nèi)的其他節(jié)點有1-u的連接率，和網(wǎng)絡(luò)其他社區(qū)的節(jié)點的連接率為u。該人工數(shù)據(jù)集在模糊參數(shù)u為增長0.05時，間隔隨機(jī)生成了11個不同的社區(qū)結(jié)構(gòu)。隨著該值的增大，則網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的模糊程度越高，越不易劃分社區(qū)結(jié)構(gòu)。本文設(shè)u值在0到0.5之間，表示所劃分的社區(qū)為強(qiáng)社區(qū)結(jié)構(gòu)。網(wǎng)絡(luò)中的社區(qū)的真實劃分情況是已知的，所以分別采用規(guī)范互信息量(NMI)和改進(jìn)的模塊度(SQ)作為評價算法準(zhǔn)確性的指標(biāo)。本文所提的算法和其他算法得到平均NMI值比較結(jié)果、SQ值最大時對應(yīng)的網(wǎng)絡(luò)劃分社區(qū)結(jié)構(gòu)、SQ值比較結(jié)果和真實數(shù)據(jù)NQD-PSO算法與QDM-PSO算法的SQ值比較如圖3所示。

圖3 NQDM-PSO算法與其他算法比較結(jié)果Fig.3 Comparison between NQDM-PSO and other algorithms

當(dāng)混合參數(shù)u值很小時，意味網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)是較清楚的。無論是傳統(tǒng)GN算法，還是其他算法，本文提到的NQD-PSO算法的性能均能比這些算法有更高的準(zhǔn)確值。當(dāng)u值在(0，0.4)之間，NQD-PSO算法得到的平均NMI均為1，模擬數(shù)據(jù)集和真實數(shù)據(jù)集得到的SQ值都在0.4以上，具有較清楚的網(wǎng)絡(luò)劃分社區(qū)結(jié)構(gòu)。當(dāng)u>0.4時，網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)相對的模糊，探測的難度更高，MOGA-net算法得到的NMI值接近為0，它已經(jīng)不能檢測出網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，但本文所提的算法依然比其他算法具有較高地平均NMI值。整體上，隨著模糊參數(shù)的增大，網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)模糊度就越高，所有的算法的性能表現(xiàn)就越低；但實驗結(jié)果表明了本文所提出的算法性能比其他算法社團(tuán)劃分效果較強(qiáng)。

4 結(jié)語

本文提出一種以模體為初始值的離散量子粒子群優(yōu)化算法的社區(qū)發(fā)現(xiàn)，構(gòu)造模體加權(quán)社區(qū)聚類函數(shù)為算法的適應(yīng)性函數(shù)；加權(quán)社區(qū)聚類函數(shù)評價模體與社區(qū)的穩(wěn)定性，從而量化社區(qū)的穩(wěn)定性。NQD-PSO算法在模擬網(wǎng)絡(luò)數(shù)據(jù)集和真實數(shù)據(jù)集進(jìn)行性能實驗，NQD-PSO算法比其他算法劃分網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)較為清楚并且效果更好。但沒有考慮到重疊節(jié)點[17]的作用，重疊社區(qū)發(fā)現(xiàn)算法將是下一個重點研究的方向。