基于限制性隨機(jī)游走局部譜近似社區(qū)發(fā)現(xiàn)算法

吳衛(wèi)江，桑睿彤+，鄭藝峰,3,4

(1.中國(guó)石油大學(xué)(北京) 石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 102249；2.中國(guó)石油大學(xué)(北京) 信息科學(xué)與信息工程學(xué)院，北京 102249；3.閩南師范大學(xué)數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，福建 漳州 363000；4.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州 363000)

0 引 言

社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究的熱點(diǎn)問(wèn)題之一，大多數(shù)傳統(tǒng)方法主要針對(duì)整個(gè)網(wǎng)絡(luò)[1-3]，進(jìn)行全局遍歷，從而找出網(wǎng)絡(luò)內(nèi)部?jī)?nèi)聚性高且網(wǎng)絡(luò)剩余部分相對(duì)分離的節(jié)點(diǎn)簇。其不足之處在于，算法的時(shí)間復(fù)雜度較高?，F(xiàn)有方法包括模塊度最大化算法[4-6]、譜聚類算法[7,8]和標(biāo)簽傳播算法[9,10]等等。需要注意的是，從大規(guī)模的網(wǎng)絡(luò)中獲取全局信息較為困難，因此，全局算法不適用于大型網(wǎng)絡(luò)。為了解決上述問(wèn)題，研究人員轉(zhuǎn)向大型網(wǎng)絡(luò)的局部結(jié)構(gòu)(即局部社區(qū)發(fā)現(xiàn)算法)，從目標(biāo)社區(qū)中已知的少數(shù)成員開(kāi)始，恢復(fù)社區(qū)中的剩余成員。研究表明，基于種子集擴(kuò)展的方法[11]可有效發(fā)現(xiàn)局部社區(qū)，具體包括局部譜方法[12]、個(gè)性化PageRank方法[13]和熱核擴(kuò)散方法[14]等等。上述方法能有效降低大型網(wǎng)絡(luò)的時(shí)間復(fù)雜度，但對(duì)于目標(biāo)社區(qū)恢復(fù)的準(zhǔn)確度還有待提高。為此，本文提出局部社區(qū)發(fā)現(xiàn)方法(LRW-LSA)，采用限制性隨機(jī)游走作為大型圖探索的預(yù)處理步驟，從而得到較小范圍的子圖以降低計(jì)算復(fù)雜度。同時(shí)，結(jié)合快速聚類融合方法，進(jìn)一步提高子圖對(duì)要恢復(fù)社區(qū)的覆蓋率。最后，使用Lanczos方法進(jìn)行快速迭代恢復(fù)得到局部社區(qū)。

1 相關(guān)研究

基于PageRank的局部社區(qū)發(fā)現(xiàn)是一種經(jīng)典的局部社區(qū)發(fā)現(xiàn)算法。Hollocou A等發(fā)現(xiàn)實(shí)際網(wǎng)絡(luò)中PageRank有效迭代次數(shù)不超過(guò)3步，提出簡(jiǎn)單而有效的無(wú)參數(shù)LexRank方法，主要根據(jù)嵌入空間的字典序排列節(jié)點(diǎn)以解決實(shí)際網(wǎng)絡(luò)中PageRank迭代次數(shù)問(wèn)題[15]。Isabel等通過(guò)研究應(yīng)用于隨機(jī)區(qū)塊模型的種子集擴(kuò)展，開(kāi)發(fā)了一種用于評(píng)估排名方法的原則框架，解決了個(gè)性化PageRank方法缺乏與種子集目標(biāo)的先驗(yàn)關(guān)系問(wèn)題[16]。

基于熱核(heat kernel)擴(kuò)散的方法涉及過(guò)渡矩陣指數(shù)的泰勒級(jí)數(shù)展開(kāi)。Chung等在此基礎(chǔ)上提出了一種高效的局部社區(qū)發(fā)現(xiàn)算法[17]，利用熱核PageRank近似算法作為子程序，對(duì)熱核PageRank向量進(jìn)行掃描，從而找到切分點(diǎn)，并根據(jù)一定規(guī)則進(jìn)行社區(qū)截?cái)?。Yang等提出兩種基于熱核PageRank的新的局部圖聚類算法TEA和TEA+[18]，以解決熱核PageRank方法的局限性問(wèn)題。上述方法有助于提高時(shí)間效率，但其準(zhǔn)確率有待進(jìn)一步提高。

基于局部譜的方法則是目前應(yīng)用最廣泛的數(shù)據(jù)分析技術(shù)之一，主要采用圖拉普拉斯矩陣的特征值向量用以提取不相交的群落。Pan等采用heat kernel方法采集局部子圖，再對(duì)采樣子空間進(jìn)行譜近似以恢復(fù)目標(biāo)社區(qū)，從而降低算法的計(jì)算復(fù)雜度[19]。不足之處在于其采樣子空間會(huì)存在過(guò)多冗余，從而影響其精確度。

與上述方法相比，本文所提出的LRW-LSA主要優(yōu)勢(shì)在于：①通過(guò)使用限制性隨機(jī)游走以及聚類融合對(duì)采樣方法進(jìn)行優(yōu)化，提升了對(duì)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的處理能力，并精確了采樣空間減少了噪聲點(diǎn)，降低了后續(xù)對(duì)采樣空間的計(jì)算復(fù)雜度；②使用Lanczos迭代的方法代替?zhèn)鹘y(tǒng)冪次迭代的方式以恢復(fù)目標(biāo)社區(qū)，有效地提高局部社區(qū)準(zhǔn)確率。

2 基于限制性隨機(jī)游走局部譜近似社區(qū)發(fā)現(xiàn)算法

采樣作為社區(qū)發(fā)現(xiàn)的預(yù)處理過(guò)程，能有效地降低計(jì)算復(fù)雜度，從而提高算法精度。本文方法主要包括：①采用限制性隨機(jī)游走方法(limited random walk，LRW)對(duì)給定目標(biāo)節(jié)點(diǎn)進(jìn)行隨機(jī)游走得到粗略的子社區(qū)空間，并通過(guò)快速聚類融合對(duì)隨機(jī)游走的向量進(jìn)行融合，從而獲得最終的采樣子空間；②通過(guò)Lanczos迭代對(duì)采樣子空間進(jìn)行進(jìn)一步的精確，以恢復(fù)出目標(biāo)節(jié)點(diǎn)所在的全部社區(qū)成員。算法的流程如圖1所示。

圖1 算法流程

2.1 限制性隨機(jī)游走

為了有效降低算法時(shí)間復(fù)雜度，采用限制性隨機(jī)游走方法[20]對(duì)社區(qū)網(wǎng)絡(luò)進(jìn)行預(yù)處理。隨機(jī)游走可等價(jià)為一個(gè)離散的平穩(wěn)馬爾科夫鏈過(guò)程，其馬爾科夫轉(zhuǎn)移矩陣P可表示為

P=(I+A)(I+D)-1

(1)

其中，A表示社區(qū)網(wǎng)絡(luò)的鄰接矩陣，I為單位矩陣。

通過(guò)給定的馬爾科夫轉(zhuǎn)移矩陣P可以計(jì)算隨機(jī)游走每步擴(kuò)散概率向量x

xt+1=Pxt

(2)

限制性隨機(jī)游來(lái)源于Markov聚類算法思想，對(duì)游走擴(kuò)散點(diǎn)轉(zhuǎn)移后的每一步進(jìn)行膨脹和歸一化操作，從而提高目標(biāo)節(jié)點(diǎn)擴(kuò)散的速度和社區(qū)恢復(fù)的準(zhǔn)確程度。膨脹操作可通過(guò)式(3)冪函數(shù)實(shí)現(xiàn)，其增長(zhǎng)速度快于線性函數(shù)

(3)

需要注意是，在膨脹操作之后，必須對(duì)x進(jìn)行歸一化處理，具體定義如下

(4)

(5)

其中，1=[1,1,…,1]T。

綜上所述，膨脹和歸一化操作能有效增強(qiáng)向量x中的大值，降低小值。

2.2 快速聚類融合過(guò)程

對(duì)于社區(qū)中每個(gè)頂點(diǎn)vi，通過(guò)限制性隨機(jī)游走，可獲得其對(duì)應(yīng)的特征向量x(*,i)。如果x(*,i)中的概率值足夠大，則vi被分配到局部的社區(qū)中，不需進(jìn)一步計(jì)算。

如果頂點(diǎn)的概率值大于η·max(x(*,i))(η與x(*,i)中的最大值相關(guān)聯(lián)，η∈[0.3,0.5])，則稱為有效頂點(diǎn)，可直接分配到局部社區(qū)。反之，頂點(diǎn)可能為社區(qū)成員或社區(qū)外的噪聲點(diǎn)。因此，需對(duì)低概率點(diǎn)使用聚類融合算法進(jìn)行二次處理。

當(dāng)vi為種子頂點(diǎn)時(shí)，其特征向量x(*,i)中每個(gè)元素xj(*,i)可表示為隨機(jī)游走擴(kuò)散點(diǎn)到達(dá)頂點(diǎn)vi的平穩(wěn)狀態(tài)的概率值。值得注意的是，x(*,i)主要取決于初始頂點(diǎn)vi所屬的社區(qū)的結(jié)構(gòu)，可見(jiàn)，相同社區(qū)中的頂點(diǎn)具有相似的特征向量。

對(duì)于兩個(gè)頂點(diǎn)集，如果其有效頂點(diǎn)重疊足夠大，則應(yīng)將其分組到相同的集群中。這意味著，獲取集群中重要的頂點(diǎn)，如果其重要頂點(diǎn)重疊超過(guò)一半，則合并集群。通過(guò)上述方法，可精確得到采樣子圖，相較于其它傳統(tǒng)的采樣方法，該子空間中幾乎包含所有的社區(qū)成員且噪聲點(diǎn)較少。

2.3 局部Lanczos譜近似

(1)局部Lanczos譜近似過(guò)程

本文使用局部Lanczos譜近似方法[21]來(lái)獲得局部特征向量，特征向量表示種子周?chē)W(wǎng)絡(luò)的隱式拓?fù)浣Y(jié)構(gòu)，通過(guò)特征向量最終恢復(fù)目標(biāo)社區(qū)。

根據(jù)Lanczos理論，存在正交矩陣Q和三對(duì)角矩陣T使得

(6)

其中，As表示采樣Gs子圖的鄰接矩陣，Ds表示采樣Gs子圖的對(duì)角度矩陣。

指示向量y第x個(gè)元素的值表示節(jié)點(diǎn)vx屬于目標(biāo)社區(qū)的可能性，具體如下所示

(7)

其中，v和u分別代表過(guò)渡矩陣Nrw和3對(duì)角矩陣T的特征向量。

(2)局部社區(qū)邊界截?cái)噙^(guò)程

將向量y中的概率降序排列，y第k個(gè)元素的值表示節(jié)點(diǎn)vk屬于目標(biāo)社區(qū)的可能性，降序排列后找到第一個(gè)索引為k*的節(jié)點(diǎn)vk*，并使降序排列的第0個(gè)節(jié)點(diǎn)v0到k*個(gè)節(jié)點(diǎn)vk*的集合Sk*作為最終的恢復(fù)出的目標(biāo)社區(qū)，其中第k*個(gè)節(jié)點(diǎn)是第一個(gè)最小的導(dǎo)率[22](表示為conductance)，conductanceφ(Sk*)是第一個(gè)局部最小值，Sk*即為得到的最終恢復(fù)出的目標(biāo)社區(qū)。值得注意的是，導(dǎo)率越小則表明節(jié)點(diǎn)之間內(nèi)部關(guān)系越緊密外部關(guān)系越稀疏，反之亦然。

2.4 算法實(shí)現(xiàn)

算法：基于限制性隨機(jī)游走局部譜近似算法LRW-LSA

輸入：圖G(V,E)的鄰接矩陣A，種子點(diǎn)集合Vs，膨脹函數(shù)(3)的指數(shù)r，最大迭代次數(shù)Tmax，限制性訪問(wèn)頂點(diǎn)的數(shù)量的值ε和一個(gè)終止條件的值ξ

輸出：最終目標(biāo)社區(qū)Sk*

(1)通過(guò)式(1)對(duì)轉(zhuǎn)移矩陣P進(jìn)行初始化

(2)foreach種子集Vs中的任意頂點(diǎn)vi

(4)forift

(5)種子集Vs中的任意頂點(diǎn)vi通過(guò)式(3)、式(4)進(jìn)行膨脹操作和歸一化操作

(7)根據(jù)2.2節(jié)的快速聚類融合策略得到采樣子圖Gs=(Vs,Es)

(8)通過(guò)2.3節(jié)的局部Lanczos譜近似過(guò)程得到指示向量y

(9)對(duì)y向量對(duì)應(yīng)的節(jié)點(diǎn)通過(guò)比較y中元素的值進(jìn)行降序排列

(10)找到包含所有種子節(jié)點(diǎn)的集合Sk0對(duì)應(yīng)的節(jié)點(diǎn)索引k0

(11)Fork=k0∶ns,conductanceφ(Sk)∶φk=φ(Sk={vi|i≤k且在降序排列中})

(12)找到第一個(gè)局部最小值φ(Sk*)時(shí)的k*，并輸出最終目標(biāo)社區(qū)Sk*

3 實(shí) 驗(yàn)

為了驗(yàn)證算法的有效性，將本文算法與現(xiàn)有的局部社區(qū)發(fā)現(xiàn)算法在多個(gè)真實(shí)社區(qū)網(wǎng)絡(luò)數(shù)據(jù)上進(jìn)行比較。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文6個(gè)數(shù)據(jù)集均來(lái)源于SNAP collection，主要涉及生產(chǎn)、協(xié)作、社交等多個(gè)應(yīng)用領(lǐng)域，具體見(jiàn)表1。表中主要包含每個(gè)數(shù)據(jù)集的計(jì)算其節(jié)點(diǎn)和邊的數(shù)量，計(jì)算社區(qū)的平均大小和標(biāo)準(zhǔn)偏差以及平均導(dǎo)率。在實(shí)驗(yàn)過(guò)程中，在每個(gè)數(shù)據(jù)集上隨機(jī)選取500個(gè)真實(shí)社區(qū)，并從每個(gè)目標(biāo)社區(qū)中隨機(jī)選取3個(gè)種子節(jié)點(diǎn)作為初始的種子集。為了保證比較的公平性，本文采用相同的隨機(jī)生成的種子集運(yùn)行所有的基線算法。以Matlab作為開(kāi)發(fā)語(yǔ)言。硬件環(huán)境為CPU：Intel Xeon processors at 2.30 GHz；內(nèi)存：256 GB memory。

表1 數(shù)據(jù)集信息

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

本文采用F1-Score和Jaccard系數(shù)作為評(píng)價(jià)指標(biāo)來(lái)檢測(cè)局部社區(qū)發(fā)現(xiàn)算法，其中，C1表示待檢測(cè)社區(qū)，C2表示目標(biāo)社區(qū)。F1-Score越大則代表兩社區(qū)相似度越高，即恢復(fù)越準(zhǔn)確。Jaccard越大，也代表著兩社區(qū)間區(qū)別越小，即恢復(fù)越準(zhǔn)確。F1-Score和Jaccard系數(shù)分別定義如下

(8)

(9)

3.3 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證本文算法的有效性，將LRW-LSA與以下4種算法進(jìn)行比較：

rwPISA[21]：基于隨機(jī)游走的冪次迭代局部社區(qū)發(fā)現(xiàn)算法；

rwLISA[21]：基于隨機(jī)游走的Lanczos迭代局部社區(qū)發(fā)現(xiàn)算法；

LOSP[23]：目前性能較好的基于局部譜子空間的方法；

LEMON[24]：另外一種基于局部譜空間的方法。

在實(shí)驗(yàn)過(guò)程中，對(duì)于限制性隨機(jī)游走和快速聚類融合部分，將膨脹指數(shù)r設(shè)置為2，最大迭代次數(shù)Tmax=5，限制訪問(wèn)頂點(diǎn)的數(shù)量的小值ε=10-5和閾值η=0.3。

實(shí)驗(yàn)表明r=2適用于大多數(shù)社區(qū)，且計(jì)算優(yōu)勢(shì)較大。Tmax=5能保證在不影響計(jì)算精度的同時(shí)最大降低采樣耗時(shí)。ε用于去除概率向量中的較小的值從而降低計(jì)算復(fù)雜度，只要ε取值足夠小，就不會(huì)影響最終的聚類結(jié)果。對(duì)于Lanczos迭代部分，為了保證精度且降低計(jì)算復(fù)雜度，本文將最大迭代值k設(shè)置為3，以表示種子周?chē)木植可鐓^(qū)結(jié)構(gòu)的局部特征向量。

3.4 采樣方法對(duì)比

常見(jiàn)的大型圖采樣方法主要包括：隨機(jī)游走、個(gè)性化PageRank和heat keneral方法。本文將LRW-LSA所采用的限制性隨機(jī)游走加聚類融合采樣方法(LRW)與上述方法進(jìn)行比較，具體見(jiàn)表2至表5，其中覆蓋率代表采樣后的子圖包含目標(biāo)社區(qū)成員于目標(biāo)社區(qū)全部成員的比例(覆蓋率越高代表子圖包含目標(biāo)社區(qū)成員越多)，ns代表采樣后子圖所包含的節(jié)點(diǎn)總數(shù)，n為數(shù)據(jù)集中的所有節(jié)點(diǎn)總數(shù)，ns/n為采樣后子圖中的節(jié)點(diǎn)數(shù)量與總節(jié)點(diǎn)數(shù)量的比例，比例越小表示采樣子圖中噪聲點(diǎn)數(shù)量越少。

表2 不同采樣方法在不同數(shù)據(jù)集上覆蓋率對(duì)比

表3 不同采樣方法在不同數(shù)據(jù)集上ns對(duì)比

表4 不同采樣方法在不同數(shù)據(jù)上ns/n對(duì)比

表5 不同采樣方法在不同數(shù)據(jù)上時(shí)間復(fù)雜度對(duì)比

從表中可以看出，隨機(jī)游走、個(gè)性化PageRank和heat keneral采樣方法僅在部分實(shí)驗(yàn)數(shù)據(jù)集覆蓋效果較好，但在對(duì)于Orkut實(shí)驗(yàn)數(shù)據(jù)集時(shí)，這3種方法的效果普遍欠佳，而本文的采樣方法能取得較好的實(shí)驗(yàn)效果。從實(shí)驗(yàn)數(shù)據(jù)中不難發(fā)現(xiàn)，本文的采樣方法不僅能取得較好覆蓋率，且采樣后子圖包含的節(jié)點(diǎn)也明顯更少(噪聲點(diǎn)個(gè)數(shù)更少)，更有利于后續(xù)的精確恢復(fù)目標(biāo)社區(qū)。在采樣過(guò)程的時(shí)間復(fù)雜度上，LRW方法則略遜于所比對(duì)算法，但仍在可接受的范圍，但在進(jìn)行Lanczos迭代時(shí)，能有效降低計(jì)算復(fù)雜度。

3.5 與其它方法對(duì)比

除上述采樣方法對(duì)比之外，本文采用兩種不同的對(duì)陣矩陣計(jì)算特征值方法(即Lanczos方法和冪次迭代方法)，對(duì)采樣后的子空間進(jìn)行求解，使用F1-Score、Jaccard系數(shù)作為評(píng)測(cè)標(biāo)準(zhǔn)。實(shí)驗(yàn)結(jié)果表明，相較于冪次迭代方法，Lanczos方法更容易收斂，效果更好。具體實(shí)驗(yàn)結(jié)果見(jiàn)表6至表8。

表6 F1-Score實(shí)驗(yàn)結(jié)果對(duì)比

表7 Jaccard 系數(shù)實(shí)驗(yàn)結(jié)果對(duì)比

表8 不同算法時(shí)間復(fù)雜度對(duì)比

由上述實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn)，本文所提出的LRW-LSA方法在F1-Score和Jaccard系數(shù)上均優(yōu)于對(duì)比方法。尤其在Orkut數(shù)據(jù)集上，相較于其它方法，LRW-LSA方法在復(fù)雜結(jié)構(gòu)網(wǎng)絡(luò)也能獲得較好的預(yù)測(cè)能力。由此可見(jiàn)，LRW-LSA方法對(duì)于復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)有著更強(qiáng)的處理能力。

4 結(jié)束語(yǔ)

本文提出一種基于采樣和局部譜近似的局部社區(qū)發(fā)現(xiàn)方法，通過(guò)限制性隨機(jī)游走、快速聚類融合以及Lanczos迭代對(duì)目標(biāo)社區(qū)進(jìn)行高精確度的恢復(fù)。實(shí)驗(yàn)結(jié)果表明，本文方法能有效提高恢復(fù)目標(biāo)社區(qū)的精度，且對(duì)于復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)有著更強(qiáng)的處理能力?？梢?jiàn)，本文所提出的LRW-LSA方法有助于提高局部社區(qū)發(fā)現(xiàn)的精確度，然而，如何降低LRW-LSA時(shí)間復(fù)雜度仍存在不足，值得進(jìn)一步優(yōu)化，以實(shí)現(xiàn)更高效的局部社區(qū)發(fā)現(xiàn)算法。