韓存鴿，陳展鴻，吳俊杰，郭昆

(1武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院,福建 南平 354300；2.武夷學(xué)院福建省茶產(chǎn)業(yè)大數(shù)據(jù)應(yīng)用與智能化重點(diǎn)實(shí)驗(yàn)室,福建 南平 354300；3.福州大學(xué)計(jì)算機(jī)與大數(shù)據(jù)學(xué)院,福建 福州 350108 )

0 引言

現(xiàn)實(shí)生活中的許多復(fù)雜系統(tǒng)都可以建模為復(fù)雜網(wǎng)絡(luò)，如社交關(guān)系、廣告營(yíng)銷、蛋白質(zhì)交互等.社區(qū)發(fā)現(xiàn)的目的就是將復(fù)雜網(wǎng)絡(luò)中諸多節(jié)點(diǎn)劃分為若干社區(qū)，使得同社區(qū)內(nèi)的節(jié)點(diǎn)間連接較為緊密，而不同社區(qū)間的節(jié)點(diǎn)連接相對(duì)稀疏[1].社區(qū)發(fā)現(xiàn)技術(shù)現(xiàn)已應(yīng)用在疾病預(yù)測(cè)、異常檢測(cè)、商品推薦等各領(lǐng)域.

在復(fù)雜網(wǎng)絡(luò)中找到最優(yōu)劃分已經(jīng)被證明是一個(gè)NP-Hard問(wèn)題，進(jìn)化計(jì)算被認(rèn)為是解決這類問(wèn)題的有效方案.早期基于進(jìn)化計(jì)算的社區(qū)發(fā)現(xiàn)方法Ga-net[2]、Meme-Net[3]都基于遺傳算法，優(yōu)化目標(biāo)單一.2009年，Pizzuti提出的MOGA-Net[4]首次將多目標(biāo)用于社區(qū)發(fā)現(xiàn)，隨后多目標(biāo)優(yōu)化算法相繼出現(xiàn)，2018年，Zhang等[5]提出RMOEA算法，將一致性較高的同社區(qū)節(jié)點(diǎn)規(guī)約成超級(jí)節(jié)點(diǎn).2020年，Liu等[6]提出NE-PSO算法，采用多目標(biāo)粒子群優(yōu)化在嵌入空間搜索社區(qū)結(jié)構(gòu)取得了不錯(cuò)的效果.但這些算法僅考慮了網(wǎng)絡(luò)的結(jié)構(gòu)，忽略了節(jié)點(diǎn)的屬性信息.

在屬性網(wǎng)絡(luò)上，Li 等[7]同時(shí)優(yōu)化屬性余弦相似度與模塊度，采用鄰域修復(fù)策略提高社區(qū)劃分的準(zhǔn)確度.Pizzuti等[8]探討了余弦相似度、模塊度、社區(qū)分?jǐn)?shù)等屬性與結(jié)構(gòu)指標(biāo)的優(yōu)化效果，給出 NSGA-II[9]在屬性網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)上較為優(yōu)越的結(jié)論.Teng等[10]將社區(qū)標(biāo)簽視為節(jié)點(diǎn)基因，基于NSGA-II框架優(yōu)化社區(qū)結(jié)構(gòu).Sun等[11]將進(jìn)化計(jì)算與神經(jīng)網(wǎng)絡(luò)結(jié)合，采用神經(jīng)網(wǎng)絡(luò)解碼出社區(qū)的鄰位編碼形式，并轉(zhuǎn)換為社區(qū)劃分.以上算法在社區(qū)評(píng)價(jià)階段考慮屬性，但現(xiàn)有工作都直接或間接基于鄰位編碼，導(dǎo)致進(jìn)化過(guò)程中無(wú)法有效利用屬性信息.

隨機(jī)游走因具有較好地處理稀疏網(wǎng)絡(luò)、提取高低階結(jié)構(gòu)信息的優(yōu)點(diǎn)，在網(wǎng)絡(luò)表示學(xué)習(xí)(network representation learning，NRL)中被廣泛應(yīng)用于獲得節(jié)點(diǎn)的多階近鄰繼而得到節(jié)點(diǎn)的嵌入向量.Perozzi 等[12]提出Deep Walk算法，通過(guò)與聚類算法結(jié)合進(jìn)行社區(qū)發(fā)現(xiàn).Node2vec算法[13]在DeepWalk的基礎(chǔ)上對(duì)節(jié)點(diǎn)進(jìn)行傾向性采樣.Zhang等[14]提出ANRL模型，利用深層神經(jīng)網(wǎng)絡(luò)來(lái)獲取結(jié)構(gòu)信息和屬性信息之間的復(fù)雜關(guān)系.Hou等[15]提出RoSANE模型采用概率轉(zhuǎn)移矩陣進(jìn)行隨機(jī)游走.其中DeepWalk、Node2vec算法僅考慮拓?fù)浣Y(jié)構(gòu)，ANRL、RoSANE算法考慮了節(jié)點(diǎn)屬性，但缺少對(duì)社區(qū)邊緣度較小的節(jié)點(diǎn)的游走，造成社區(qū)邊界識(shí)別較低，社區(qū)發(fā)現(xiàn)的精度不高.

針對(duì)上述問(wèn)題，提出一種基于隨機(jī)游走的進(jìn)化計(jì)算社區(qū)發(fā)現(xiàn)算法(random-walk-based evolutionary community detection,RWECD).RWECD算法設(shè)計(jì)考慮了拓?fù)浜蛯傩噪S機(jī)游走的社區(qū)初始化策略，策略中重新定義游走概率，獲取一組有偏隨機(jī)游走序列；設(shè)計(jì)考慮拓?fù)浜蛯傩缘墓?jié)點(diǎn)嵌入向量更新策略，使得種群在每一代更新過(guò)程中充分利用結(jié)構(gòu)和屬性信息來(lái)進(jìn)行啟發(fā)式更新.并通過(guò)在真實(shí)和人工數(shù)據(jù)集上實(shí)驗(yàn)，驗(yàn)證了RWECD算法能夠有效提高社區(qū)發(fā)現(xiàn)的精度.

1 RWECD算法

1.1 基本概念

定義1網(wǎng)絡(luò)嵌入.復(fù)雜網(wǎng)絡(luò)可以被建模為圖G=(V,E,A)，其中V={v1，v2，…，vn}表示n個(gè)節(jié)點(diǎn)的集合，E表示網(wǎng)絡(luò)中邊的集合,E={(vi,vj)|vi∈V,vj∈V,且i≠j}.A=[a1,a2,…，an]T∈R|v|×m為節(jié)點(diǎn)的屬性信息矩陣,用來(lái)描述節(jié)點(diǎn)的屬性信息.

定義2屬性相似度矩陣.SA用于記錄兩個(gè)節(jié)點(diǎn)間屬性相似度.對(duì)于單屬性網(wǎng)絡(luò)，如果節(jié)點(diǎn)vi和節(jié)點(diǎn)vj具有相同的屬性，則SA中第i行和第j列的元素(i,j)設(shè)置為1，否則為0.對(duì)于多屬性網(wǎng)絡(luò)，SA中的元素(i,j)定義為節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的屬性向量的余弦相似度.

(1)

(2)

定義3嵌入空間的屬性相似度.嵌入空間中的屬性相似度矩陣SNE定義如下:

(3)

定義4社區(qū)屬性相似度Sim.在嵌入空間，通過(guò)最大化如下函數(shù)保留二階相似性.采用社區(qū)屬性相似度作為社區(qū)的第一個(gè)目標(biāo)函數(shù)，其值越大社區(qū)劃分越好.定義如下：

(4)

定義5模塊度函數(shù)Q.采用模塊度作為社區(qū)的第二個(gè)目標(biāo)函數(shù)，模塊度定義如下：

(5)

其中：m為網(wǎng)絡(luò)邊數(shù)，A為鄰接矩陣，節(jié)點(diǎn)i和j存在連接，Aij值為1；否則為 0.ki和kj表示節(jié)點(diǎn)i和j的度；函數(shù)δ(Ci,Cj)中，節(jié)點(diǎn)i和j同屬一個(gè)社區(qū)，其值為 1，否則為 0.Q值越接近1，社區(qū)結(jié)構(gòu)越顯著.

1.2 RWECD算法框架

RWECD算法的框架如圖1所示，整體可以分為編碼表示及初始化、向量更新、輸出社區(qū)劃分3個(gè)階段.在階段1中，設(shè)計(jì)一種結(jié)合屬性相似度的隨機(jī)游走策略，基于該策略生成一組游走序列，采用鄰位編碼方式對(duì)游走序列進(jìn)行編碼，為每個(gè)節(jié)點(diǎn)選擇一個(gè)合適的基因值，接著把其解碼為基于社區(qū)標(biāo)簽的嵌入表示，執(zhí)行隨機(jī)初始化.在階段2中，設(shè)計(jì)綜合考慮拓?fù)浜蛯傩缘墓?jié)點(diǎn)嵌入向量更新策略，經(jīng)過(guò)多次更新后，對(duì)更新的社區(qū)采用目標(biāo)函數(shù)進(jìn)行評(píng)價(jià).在階段3中，獲取融合屬性結(jié)構(gòu)與屬性的社區(qū)劃分.

圖1 RWECD算法框架Fig.1 RWECD algorithm framework

1.3 編碼表示與初始化

在RWECD算法中，每個(gè)個(gè)體均由兩部分構(gòu)成，嵌入向量表示I={I1，I2，…，In∈Rn×d}和節(jié)點(diǎn)的社區(qū)標(biāo)簽L={C1，C2，…,Cn}，其中d為嵌入維數(shù)，Ci表示節(jié)點(diǎn)Vi的社區(qū)標(biāo)簽.在進(jìn)化計(jì)算的社區(qū)發(fā)現(xiàn)中，通常有鄰位編碼和標(biāo)簽編碼兩種方式.鄰位編碼根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)節(jié)點(diǎn)編碼，節(jié)點(diǎn)的基因值必然是其結(jié)構(gòu)鄰居中的某個(gè)節(jié)點(diǎn).假設(shè)網(wǎng)絡(luò)中有三個(gè)節(jié)點(diǎn)1、2、3，節(jié)點(diǎn)1的基因值為2(1與2必須在結(jié)構(gòu)上存在連接)，那么節(jié)點(diǎn)1和節(jié)點(diǎn)2一定屬于同一個(gè)社區(qū).標(biāo)簽編碼直接將社區(qū)標(biāo)簽作為節(jié)點(diǎn)的編碼，如節(jié)點(diǎn)1、2的基因值為1，節(jié)點(diǎn)6、7的基因值為2，將基因值看作他們的社區(qū)標(biāo)簽，那么解碼后節(jié)點(diǎn)1、2被分配到一個(gè)社區(qū)，節(jié)點(diǎn)6、7被分配到另一個(gè)社區(qū).圖2表示鄰位編碼和標(biāo)簽編碼過(guò)程，其中圖2(a)為鄰位編碼，圖2(b)為標(biāo)簽編碼.RWECD采用鄰位編碼與標(biāo)簽編碼相結(jié)合的編碼方式.

圖2 鄰位編碼與標(biāo)簽編碼表示法Fig.2 Adjacency coding and label coded representation

在RWECD中，為了得到相對(duì)較好的初始種群，在初始化過(guò)程中設(shè)計(jì)了一種結(jié)合屬性相似度的隨機(jī)游走方案，首先采用公式(6)獲取游走概率生成游走序列Dwalki，接著根據(jù)游走序列Dwalki產(chǎn)生節(jié)點(diǎn)的鄰位編碼，最后對(duì)鄰位編碼進(jìn)行編碼轉(zhuǎn)換得到每個(gè)節(jié)點(diǎn)的社區(qū)標(biāo)簽.在獲取社區(qū)標(biāo)簽后，執(zhí)行隨機(jī)初始化，使得具有相同社區(qū)標(biāo)簽的節(jié)點(diǎn)在嵌入空間中距離更近.游走概率公式如下:

(6)

圖3給出了一個(gè)基于上述隨機(jī)游走方案生成游走序列的示例.

圖3 初始化過(guò)程示例Fig.3 Example of the initialization process

圖3(a)表示相似度矩陣，圖3(b)表示利用隨機(jī)游走生成的個(gè)體編碼及編碼轉(zhuǎn)換，圖3(c)和圖3(d)表示初始化節(jié)點(diǎn)的嵌入表示.以節(jié)點(diǎn)2為例，此處游走步長(zhǎng)為3.從得到的屬性相似度矩陣可以看出，對(duì)于至少一維屬性值相同的節(jié)點(diǎn)共有5個(gè)，即節(jié)點(diǎn)1、3、4、5和8.通過(guò)公式(6)得到的游走概率，這5個(gè)節(jié)點(diǎn)被選擇的概率分別為0.097 5、0.235、0.215、0.078、0.08，最終確定節(jié)點(diǎn)2的下一個(gè)游走節(jié)點(diǎn)為節(jié)點(diǎn)3，依次計(jì)算最終游走序列為2→3→4→1，再取節(jié)點(diǎn)5，按照游走概率最后確定的游走序列為5→8→7→6.獲取游走序列后根據(jù)基于節(jié)點(diǎn)的鄰位編碼確定每個(gè)節(jié)點(diǎn)的等位基因值.接著對(duì)個(gè)體進(jìn)行編碼轉(zhuǎn)換，得到節(jié)點(diǎn)的社區(qū)標(biāo)簽.執(zhí)行隨機(jī)初始化，使得I的值在0到1之間隨機(jī)初始化，從而使相同社區(qū)標(biāo)簽的節(jié)點(diǎn)在嵌入空間中距離更近，隨后計(jì)算每個(gè)社區(qū)內(nèi)所有節(jié)點(diǎn)表示向量的平均值，接著計(jì)算兩兩社區(qū)表示向量平均值的余弦相似度，對(duì)比預(yù)先設(shè)置的閾值，若余弦相似度大于這個(gè)閾值，則對(duì)這兩社區(qū)進(jìn)行合并.這種方式有效地利用了節(jié)點(diǎn)的屬性信息，生成的初始化種群的質(zhì)量相對(duì)較高.

1.4 向量更新

① 交叉及變異.在設(shè)計(jì)算法中應(yīng)用了經(jīng)典的模擬二進(jìn)制交叉SBX算子[16].SBX特別適用于存在多個(gè)最優(yōu)解的問(wèn)題.對(duì)于變異算子，傳統(tǒng)的算子如隨機(jī)變異、高斯變異和多項(xiàng)式變異算子都適用于多目標(biāo)進(jìn)化計(jì)算.在本研究中，選擇隨機(jī)變異算子.

② 向量更新.若相應(yīng)適應(yīng)度函數(shù)值增加，合格節(jié)點(diǎn)將相繼加入對(duì)應(yīng)社區(qū).因而，嵌入空間中每個(gè)合格節(jié)點(diǎn)的位置需要稍微向其所屬的新社區(qū)偏移.從屬性和拓?fù)鋬刹糠志C合考慮更新向量，設(shè)計(jì)思想源于一個(gè)節(jié)點(diǎn)傾向于移動(dòng)到距社區(qū)中心點(diǎn)近的社區(qū)，一個(gè)節(jié)點(diǎn)也更傾向于移動(dòng)到新社區(qū)中度大的節(jié)點(diǎn)處，如社交網(wǎng)絡(luò)中，一些度大的節(jié)點(diǎn)可以認(rèn)為是較成功的人，其具有的影響力也較高.嵌入向量的更新如下式所示：

(7)

式中：Icenter是新社區(qū)中心節(jié)點(diǎn)的表示;Imax是社區(qū)中度最大的節(jié)點(diǎn)表示;β是控制移動(dòng)范圍的正參數(shù).在本研究中設(shè)定β為0.3，嵌入向量更新可以看做節(jié)點(diǎn)在搜索空間做了一次位移.對(duì)生成社區(qū)劃分使用公式(4)、(5)評(píng)價(jià)，Q值越接近1，社區(qū)屬性相似度越大，搜索到的社區(qū)結(jié)構(gòu)在拓?fù)浣Y(jié)構(gòu)和屬性上越顯著.

1.5 輸出社區(qū)劃分

節(jié)點(diǎn)社區(qū)劃分經(jīng)過(guò)編碼表示及初始化、向量更新、社區(qū)劃分3個(gè)階段，社區(qū)劃分如圖4所示，圖4(a)為網(wǎng)絡(luò)空間嵌入表示，4(b)為社區(qū)標(biāo)簽.

圖4 社區(qū)劃分Fig.4 The community divided

1.6 算法偽代碼

RWECD算法是在NSGA-II框架下實(shí)現(xiàn)的，其偽代碼如下所示.

RWECD算法偽代碼輸入:G=(V,E,A);//屬性網(wǎng)絡(luò),d:嵌入空間的維度,Genmax:最大迭代次數(shù),Popsize:種群規(guī)模Pc:交叉概率,Pm:變異概率輸出:社區(qū)劃分L,網(wǎng)絡(luò)表示I,//階段1:基于隨機(jī)游走的社區(qū)初始化(1)SA←Getsimilarity(G)//Getsimilarity()函數(shù)用于獲取屬性相似度矩陣SA(2)P←Initialpopu(SA,Popsize,d)//Initialpopu()函數(shù)用于創(chuàng)建初始種群//階段2:向量更新(3)while(t

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

為了檢驗(yàn)RWECD的性能，在人工和真實(shí)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)選取6個(gè)對(duì)比算法，DeepWalk、Node2vec是基于隨機(jī)游走算法，BAGC[17]、SCI[18]、vGraph[19]是基于模型的算法，RMOEA是基于進(jìn)化計(jì)算的算法.

2.1 實(shí)驗(yàn)數(shù)據(jù)集2.1.1 人工數(shù)據(jù)集

采用LFR基準(zhǔn)網(wǎng)絡(luò)生成人工數(shù)據(jù)集，基于LFR 生成1組參數(shù)不同的網(wǎng)絡(luò)D1來(lái)驗(yàn)證所提算法的性能.人工網(wǎng)絡(luò)參數(shù)具體含義為：n、k、μ分別代表節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)平均度、混合參數(shù)，kmax、Cmin、Cmax分別代表節(jié)點(diǎn)最大度、最小社區(qū)內(nèi)節(jié)點(diǎn)數(shù)、最大社區(qū)內(nèi)節(jié)點(diǎn)數(shù)，其余未說(shuō)明參數(shù)設(shè)置為L(zhǎng)FR工具默認(rèn)值.D1網(wǎng)絡(luò)參數(shù)為：n=1 000～5 000、k=20、μ=0.2和0.5、kmax=50、Cmin=10、Cmax=100.

2.1.2 真實(shí)數(shù)據(jù)集

表1 真實(shí)網(wǎng)絡(luò)Tab.1 Real-world networks

實(shí)驗(yàn)選取6個(gè)真實(shí)數(shù)據(jù)集驗(yàn)證所提算法性能，具體包括：WebKB[20]中4個(gè)美國(guó)大學(xué)的計(jì)算機(jī)系交流網(wǎng)絡(luò)Cornell、Texas、Washington、Wisconsin,以及兩個(gè)不同領(lǐng)域的科學(xué)引文網(wǎng)絡(luò)Cora[21]、Citeseer[22].表1給出了這些屬性網(wǎng)絡(luò)的具體信息：

2.2 評(píng)價(jià)指標(biāo)

采用標(biāo)準(zhǔn)互信息NMI和平均F1指標(biāo)評(píng)價(jià)RWECD算法的性能.NMI定義如下所示：

(8)

其中：CA、CB分別表示真實(shí)社區(qū)劃分與算法檢測(cè)社區(qū)劃分;Nij表示同時(shí)被分配到CA中第i個(gè)社區(qū)與CB中第j個(gè)社區(qū)的節(jié)點(diǎn)數(shù)量;真實(shí)社區(qū)劃分和檢測(cè)的社區(qū)劃分越相似，NMI的值越接近1，否則就越低.

F1定義如下式所示：

(9)

圖5 向量更新參數(shù)β實(shí)驗(yàn)Fig.5 Vector update parameter β experiment

2.3 參數(shù)實(shí)驗(yàn)

RWECD算法中有一個(gè)重要的向量更新參數(shù)β，其對(duì)算法精度的影響結(jié)果如圖5所示，實(shí)驗(yàn)采用 D1網(wǎng)絡(luò)進(jìn)行.結(jié)果表明，在不同網(wǎng)絡(luò)規(guī)模上，RWECD精度相對(duì)穩(wěn)定，當(dāng)β=0.3時(shí)，在不同的網(wǎng)絡(luò)上都取得最好的效果，隨著β繼續(xù)增大，精度開(kāi)始下降.因此，后面實(shí)驗(yàn)中將參數(shù)β值設(shè)置為0.3.

2.4 精度實(shí)驗(yàn)2.4.1 人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖6～7顯示了RWECD與對(duì)比算法在D1網(wǎng)絡(luò)上的精度實(shí)驗(yàn)，其中圖6為NMI精度實(shí)驗(yàn)，圖7為F1精度實(shí)驗(yàn).結(jié)果表明，在多數(shù)網(wǎng)絡(luò)上RWECD算法精度優(yōu)于對(duì)比算法，這是因?yàn)镽WECD通過(guò)嵌入向量的更新策略，使得節(jié)點(diǎn)屬性信息在進(jìn)化過(guò)程中被有效利用，進(jìn)而得到準(zhǔn)確的社區(qū)劃分.DeepWalk、Node2vec算法的精度也較高，這是因?yàn)殡m然DeepWalk、Node2vec算法都是利用隨機(jī)游走序列來(lái)捕捉網(wǎng)絡(luò)中的結(jié)構(gòu)，但其都有考慮高階拓?fù)湫畔?，所以在不同?guī)模的網(wǎng)絡(luò)上精度都較高.SCI算法采用社區(qū)成員矩陣和社區(qū)屬性矩陣進(jìn)行非負(fù)矩陣分解，因此其精度隨網(wǎng)絡(luò)規(guī)模的增大變化不大.RMOEA 采用節(jié)點(diǎn)規(guī)約策略將同社區(qū)的節(jié)點(diǎn)合并成超級(jí)節(jié)點(diǎn)以提高收斂速度，然而，在μ值較大的網(wǎng)絡(luò)上，由于社區(qū)邊界較模糊，這種策略可能會(huì)錯(cuò)誤地合并不同社區(qū)的節(jié)點(diǎn)，從而導(dǎo)致算法精度較低.

圖6 人工數(shù)據(jù)集上的NMI實(shí)驗(yàn)Fig.6 NMI experiments on artificial datasets

圖7 人工數(shù)據(jù)集上的F1實(shí)驗(yàn)Fig.7 F1 experiments on artificial datasets

2.4.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖8～9顯示了RWECD算法與對(duì)比算法在各個(gè)真實(shí)網(wǎng)絡(luò)上的精度實(shí)驗(yàn)，其中圖8為NMI精度實(shí)驗(yàn)，圖9為F1精度實(shí)驗(yàn).

圖8 真實(shí)數(shù)據(jù)集上的NMI實(shí)驗(yàn)Fig.8 NMI experiments on real datasets

圖9 真實(shí)數(shù)據(jù)集上的F1實(shí)驗(yàn)Fig.9 F1 experiments on real data sets

結(jié)果表明，RWECD算法在多數(shù)網(wǎng)絡(luò)中的精度效果明顯，這是因?yàn)镽WECD通過(guò)基于隨機(jī)游走的初始化策略，獲取初始種群的質(zhì)量較高，因此能夠更好地識(shí)別社區(qū)邊界，提高社區(qū)發(fā)現(xiàn)的精度.從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，雖然DeepWalk、Node2vec、RMOEA算法僅考慮拓?fù)浣Y(jié)構(gòu)，但在Cora、Citeseer網(wǎng)絡(luò)上，RWECD算法精度低于DeepWalk、Node2vec、RMOEA算法，這是因?yàn)閷?duì)于網(wǎng)絡(luò)Cora、Citeseer，其拓?fù)浣Y(jié)構(gòu)對(duì)社區(qū)分辨的影響要強(qiáng)于屬性，且屬性相似度與拓?fù)湎嗨贫却嬖谝欢ǔ潭鹊谋畴x.

2.5 迭代進(jìn)化實(shí)驗(yàn)

在網(wǎng)絡(luò)Cora、Texas及D1上進(jìn)行RWECD迭代實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果為一組非支配解.實(shí)驗(yàn)過(guò)程如圖10所示.圖 10(a)、(b)、(c)、(d)分別表示在網(wǎng)絡(luò)Cora、Texas、D1(μ=0.2與μ=0.5)上的迭代進(jìn)化結(jié)果.圖中不同顏色點(diǎn)代表不同子代的帕累托解集.由圖10可以看出，每隔10代,在網(wǎng)絡(luò)Cora、Texas上迭代至40代之前，優(yōu)化指標(biāo)Q和Sim都有明顯提高，同時(shí)，帕累托前沿分散均勻，表明RWECD算法優(yōu)化效果較明顯.但在40～50代的迭代過(guò)程中，RWECD算法優(yōu)化效果不太明顯.這是因?yàn)楫?dāng)種群迭代至40代時(shí)，帕累托解集開(kāi)始逐漸收斂并接近最優(yōu)值.在模塊度Q上，Cora結(jié)果優(yōu)于Texas，表明Cora網(wǎng)絡(luò)的拓?fù)湫畔⑤^為明顯，而在屬性Sim上，Texas網(wǎng)絡(luò)上的結(jié)果優(yōu)于Cora，則表明Texas網(wǎng)絡(luò)的屬性信息較為明顯.在D1網(wǎng)絡(luò)上結(jié)果與網(wǎng)絡(luò)Cora和Texas結(jié)果類似.不同之處在于，當(dāng)μ=0.2時(shí)，RWECD在模塊度Q上的結(jié)果優(yōu)于μ=0.5.原因在于μ控制網(wǎng)絡(luò)的復(fù)雜程度，值越小拓?fù)浣Y(jié)構(gòu)越簡(jiǎn)單，優(yōu)化模塊度Q值較高.在屬性上，D1網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果沒(méi)有明顯區(qū)別.

圖10 迭代進(jìn)化實(shí)驗(yàn)結(jié)果

3 結(jié)論

針對(duì)屬性網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題，提出一種基于隨機(jī)游走的進(jìn)化計(jì)算社區(qū)發(fā)現(xiàn)算法.為了更好地識(shí)別社區(qū)邊界，設(shè)計(jì)一種基于拓?fù)浣Y(jié)構(gòu)及屬性信息隨機(jī)游走的社區(qū)初始化策略，使游走方向偏向度小且屬性相似度高的節(jié)點(diǎn)，可以獲得相對(duì)較好的初始種群，能夠準(zhǔn)確地識(shí)別社區(qū)邊界，從而提高社區(qū)發(fā)現(xiàn)的精度.為了在進(jìn)化過(guò)程中有效利用屬性信息，設(shè)計(jì)了考慮拓?fù)浜蛯傩缘墓?jié)點(diǎn)嵌入向量的更新策略，使得節(jié)點(diǎn)的屬性信息能夠在進(jìn)化過(guò)程中被有效利用，節(jié)點(diǎn)在嵌入空間更新可理解為節(jié)點(diǎn)在搜索空間進(jìn)行位移，在一定程度上擴(kuò)大搜索的范圍，提高社區(qū)發(fā)現(xiàn)的質(zhì)量.通過(guò)在真實(shí)和人工數(shù)據(jù)集上實(shí)驗(yàn)，驗(yàn)證了提出的RWECD算法能夠提高社區(qū)發(fā)現(xiàn)的精度.未來(lái)，將在現(xiàn)有工作的基礎(chǔ)上設(shè)計(jì)一種新的解碼策略來(lái)有效地表示重疊社區(qū)和相應(yīng)的嵌入表示，嘗試在沒(méi)有任何先驗(yàn)知識(shí)的情況下自動(dòng)確定社區(qū)的數(shù)量.