基于隨機游走的進化計算社區(qū)發(fā)現(xiàn)

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

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

0 引言

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

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

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

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

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

1 RWECD算法

1.1 基本概念

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

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

(1)

(2)

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

(3)

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

(4)

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

(5)

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

1.2 RWECD算法框架

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

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

1.3 編碼表示與初始化

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

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

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

(6)

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

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

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

1.4 向量更新

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

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

(7)

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

1.5 輸出社區(qū)劃分

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

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

1.6 算法偽代碼

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

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

2 實驗結果與分析

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

2.1 實驗數(shù)據(jù)集2.1.1 人工數(shù)據(jù)集

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

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

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

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

2.2 評價指標

采用標準互信息NMI和平均F1指標評價RWECD算法的性能.NMI定義如下所示：

(8)

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

F1定義如下式所示：

(9)

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

2.3 參數(shù)實驗

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

2.4 精度實驗2.4.1 人工數(shù)據(jù)集實驗結果

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

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

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

2.4.2 真實數(shù)據(jù)集實驗結果

圖8～9顯示了RWECD算法與對比算法在各個真實網(wǎng)絡上的精度實驗，其中圖8為NMI精度實驗，圖9為F1精度實驗.

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

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

結果表明，RWECD算法在多數(shù)網(wǎng)絡中的精度效果明顯，這是因為RWECD通過基于隨機游走的初始化策略，獲取初始種群的質量較高，因此能夠更好地識別社區(qū)邊界，提高社區(qū)發(fā)現(xiàn)的精度.從實驗結果發(fā)現(xiàn)，雖然DeepWalk、Node2vec、RMOEA算法僅考慮拓撲結構，但在Cora、Citeseer網(wǎng)絡上，RWECD算法精度低于DeepWalk、Node2vec、RMOEA算法，這是因為對于網(wǎng)絡Cora、Citeseer，其拓撲結構對社區(qū)分辨的影響要強于屬性，且屬性相似度與拓撲相似度存在一定程度的背離.

2.5 迭代進化實驗

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

圖10 迭代進化實驗結果

3 結論

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