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

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

0 引 言

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

1 相關(guān)研究

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

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

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

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

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

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

圖1 算法流程

2.1 限制性隨機游走

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

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

(1)

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

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

xt+1=Pxt

(2)

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

(3)

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

(4)

(5)

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

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

2.2 快速聚類融合過程

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

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

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

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

2.3 局部Lanczos譜近似

(1)局部Lanczos譜近似過程

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

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

(6)

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

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

(7)

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

(2)局部社區(qū)邊界截斷過程

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

2.4 算法實現(xiàn)

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

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

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

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

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

(4)forift

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

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

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

(9)對y向量對應(yīng)的節(jié)點通過比較y中元素的值進行降序排列

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

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

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

3 實 驗

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

3.1 實驗數(shù)據(jù)集

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

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

3.2 評價指標(biāo)

本文采用F1-Score和Jaccard系數(shù)作為評價指標(biāo)來檢測局部社區(qū)發(fā)現(xiàn)算法，其中，C1表示待檢測社區(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è)置

為了驗證本文算法的有效性，將LRW-LSA與以下4種算法進行比較：

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

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

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

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

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

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

3.4 采樣方法對比

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

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

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

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

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

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

3.5 與其它方法對比

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

表6 F1-Score實驗結(jié)果對比

表7 Jaccard 系數(shù)實驗結(jié)果對比

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

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

4 結(jié)束語

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