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

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

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

0 引言

社區(qū)結(jié)構(gòu)是指網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中表現(xiàn)出來的社團(tuán)化特征，整個(gè)網(wǎng)絡(luò)由若干個(gè)社團(tuán)構(gòu)成。社區(qū)內(nèi)部連接緊密，社區(qū)與社區(qū)之間連接比較稀疏[1]。社區(qū)發(fā)現(xiàn)對(duì)研究網(wǎng)絡(luò)結(jié)構(gòu)有重要的應(yīng)用價(jià)值，社區(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é)點(diǎn)與遺傳算法中的遺傳基因相映射，而(量子)粒子群優(yōu)化社區(qū)發(fā)現(xiàn)算法將網(wǎng)絡(luò)的節(jié)點(diǎn)與算法中的粒子相映射。社區(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)算法對(duì)初始節(jié)點(diǎn)的位置敏感，如果初始節(jié)點(diǎn)處于社區(qū)邊緣，那么效果差，反之，則效果較好，這導(dǎo)致算法穩(wěn)定性較差。算法的收斂條件缺乏自適應(yīng)性，從網(wǎng)絡(luò)的種子節(jié)點(diǎn)度出發(fā)，每次更新社區(qū)節(jié)點(diǎn)只需用到社區(qū)內(nèi)部節(jié)點(diǎn)和邊緣節(jié)點(diǎn)的鄰節(jié)點(diǎn)的信息，算法的時(shí)間復(fù)雜度較低，但因沒考慮全局信息，容易受種子節(jié)點(diǎn)影響，這導(dǎo)致算法精度不是很高。本文采用一種離散量子粒子群優(yōu)化算法的社區(qū)發(fā)現(xiàn)(NQD-PSO)，將核心節(jié)點(diǎn)與鄰居的普通節(jié)點(diǎn)構(gòu)成模體，該模體為量子粒子群算法的初始值。本文利用了三角形模體來判斷社區(qū)的穩(wěn)定性度量問題，從而量化社區(qū)結(jié)構(gòu)穩(wěn)定性。同時(shí)，采用壓縮因子函數(shù)調(diào)節(jié)全局和局部搜索模型，結(jié)合量子粒子群算法，使該算法全局收斂。模擬和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(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é)點(diǎn)集合，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ù)，如果兩個(gè)節(jié)點(diǎn)的相關(guān)系數(shù)為正數(shù)，pr為正相關(guān)系數(shù)，如果兩個(gè)節(jié)點(diǎn)的相關(guān)系數(shù)為負(fù)數(shù)，nr為負(fù)相關(guān)系數(shù)。網(wǎng)絡(luò)中有節(jié)點(diǎn)數(shù)為n，邊數(shù)為m，如果節(jié)點(diǎn)vi與節(jié)點(diǎn)vj中間有邊相接，則eij=1，否則，eij=0，所以節(jié)點(diǎn)vi的度ki表示為：ki=∑vj∈Veij。節(jié)點(diǎn)vi的點(diǎn)權(quán)si定義為與節(jié)點(diǎn)i關(guān)聯(lián)的邊權(quán)之和，也稱為點(diǎn)強(qiáng)度。

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

Cij=neighbor(vi)∩neighbor(vj)

(1)

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

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

(2)

(3)

其中，vt為核心節(jié)點(diǎn)，則kt,st分別表示重新排序后的節(jié)點(diǎn)度和點(diǎn)強(qiáng)度。核心節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的運(yùn)行具有主導(dǎo)的作用。網(wǎng)絡(luò)中的節(jié)點(diǎn)的重要程度不同，核心節(jié)點(diǎn)具有較高重要性，而普通節(jié)點(diǎn)則是網(wǎng)絡(luò)中的參與者。社區(qū)是由核心節(jié)點(diǎn)和追隨的普通節(jié)點(diǎn)構(gòu)成，劃分網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，必須要找出網(wǎng)絡(luò)社區(qū)的核心節(jié)點(diǎn)。如果這樣單純依賴排序結(jié)果，選擇初始核心節(jié)點(diǎn)會(huì)帶來潛在風(fēng)險(xiǎn)，多個(gè)核心節(jié)點(diǎn)可能在相同社區(qū)，按從大到小的選擇，可能會(huì)把一個(gè)大的社區(qū)分解為若個(gè)小社區(qū)；為了避免這些問題，在核心節(jié)點(diǎn)選擇上附加一些約束：為了避免核心節(jié)點(diǎn)與外界節(jié)點(diǎn)連接較少，選擇核心節(jié)點(diǎn)的點(diǎn)強(qiáng)度必須大于網(wǎng)絡(luò)中所有的節(jié)點(diǎn)的平均點(diǎn)強(qiáng)度。先后選出的若干個(gè)網(wǎng)絡(luò)的模體在同一社區(qū)，當(dāng)前選擇的模體必須和已有模體是相鄰的。核心節(jié)點(diǎn)與普通節(jié)點(diǎn)相連接構(gòu)成模體，把網(wǎng)絡(luò)劃分為k個(gè)模體，記為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)化算法為背景知識(shí)解決網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題，將核心節(jié)點(diǎn)和鄰居的普通節(jié)點(diǎn)構(gòu)成的模體當(dāng)作量子粒子群的粒子，通過量子粒子群算法來改變粒子位置的歸屬，旨在挖掘出高質(zhì)量的社區(qū)結(jié)構(gòu)。下面是NQD-PSO算法流程圖，如圖1所示。

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

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

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

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

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

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

3.1 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

(11)

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

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

(12)

3.2 算法比較結(jié)果評(píng)價(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é)點(diǎn)128個(gè)，含有1024條邊，而每個(gè)節(jié)點(diǎn)的平均點(diǎn)強(qiáng)度為8和平均度數(shù)為16，將所有的節(jié)點(diǎn)平均的劃分成4個(gè)社區(qū)，每個(gè)社區(qū)中含有32個(gè)節(jié)點(diǎn)。真實(shí)數(shù)據(jù)集的基本信息如下表：

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

網(wǎng)絡(luò)中含有一個(gè)模糊參數(shù)u，表示為任一節(jié)點(diǎn)vi與社區(qū)外節(jié)點(diǎn)vj形成的鏈接占節(jié)點(diǎn)vi之度的比率，每個(gè)節(jié)點(diǎn)vi和同一個(gè)社區(qū)內(nèi)的其他節(jié)點(diǎn)有1-u的連接率，和網(wǎng)絡(luò)其他社區(qū)的節(jié)點(diǎn)的連接率為u。該人工數(shù)據(jù)集在模糊參數(shù)u為增長0.05時(shí)，間隔隨機(jī)生成了11個(gè)不同的社區(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ū)的真實(shí)劃分情況是已知的，所以分別采用規(guī)范互信息量(NMI)和改進(jìn)的模塊度(SQ)作為評(píng)價(jià)算法準(zhǔn)確性的指標(biāo)。本文所提的算法和其他算法得到平均NMI值比較結(jié)果、SQ值最大時(shí)對(duì)應(yīng)的網(wǎng)絡(luò)劃分社區(qū)結(jié)構(gòu)、SQ值比較結(jié)果和真實(shí)數(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值很小時(shí)，意味網(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í)數(shù)據(jù)集得到的SQ值都在0.4以上，具有較清楚的網(wǎng)絡(luò)劃分社區(qū)結(jié)構(gòu)。當(dāng)u>0.4時(shí)，網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)相對(duì)的模糊，探測(cè)的難度更高，MOGA-net算法得到的NMI值接近為0，它已經(jīng)不能檢測(cè)出網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，但本文所提的算法依然比其他算法具有較高地平均NMI值。整體上，隨著模糊參數(shù)的增大，網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)模糊度就越高，所有的算法的性能表現(xiàn)就越低；但實(shí)驗(yà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ù)評(píng)價(jià)模體與社區(qū)的穩(wěn)定性，從而量化社區(qū)的穩(wěn)定性。NQD-PSO算法在模擬網(wǎng)絡(luò)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行性能實(shí)驗(yàn)，NQD-PSO算法比其他算法劃分網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)較為清楚并且效果更好。但沒有考慮到重疊節(jié)點(diǎn)[17]的作用，重疊社區(qū)發(fā)現(xiàn)算法將是下一個(gè)重點(diǎn)研究的方向。