基于限制性隨機游走局部譜近似社區發現算法

吳衛江，桑睿彤+，鄭藝峰,3,4

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

0 引 言

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

1 相關研究

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

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

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

與上述方法相比，本文所提出的LRW-LSA主要優勢在于：①通過使用限制性隨機游走以及聚類融合對采樣方法進行優化，提升了對復雜網絡結構的處理能力，并精確了采樣空間減少了噪聲點，降低了后續對采樣空間的計算復雜度；②使用Lanczos迭代的方法代替傳統冪次迭代的方式以恢復目標社區，有效地提高局部社區準確率。

2 基于限制性隨機游走局部譜近似社區發現算法

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

圖1 算法流程

2.1 限制性隨機游走

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

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

(1)

其中，A表示社區網絡的鄰接矩陣，I為單位矩陣。

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

xt+1=Pxt

(2)

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

(3)

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

(4)

(5)

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

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

2.2 快速聚類融合過程

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

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

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

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

2.3 局部Lanczos譜近似

(1)局部Lanczos譜近似過程

本文使用局部Lanczos譜近似方法[21]來獲得局部特征向量，特征向量表示種子周圍網絡的隱式拓撲結構，通過特征向量最終恢復目標社區。

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

(6)

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

指示向量y第x個元素的值表示節點vx屬于目標社區的可能性，具體如下所示

(7)

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

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

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

2.4 算法實現

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

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

輸出：最終目標社區Sk*

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

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

(4)forift

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

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

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

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

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

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

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

3 實 驗

為了驗證算法的有效性，將本文算法與現有的局部社區發現算法在多個真實社區網絡數據上進行比較。

3.1 實驗數據集

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

表1 數據集信息

3.2 評價指標

本文采用F1-Score和Jaccard系數作為評價指標來檢測局部社區發現算法，其中，C1表示待檢測社區，C2表示目標社區。F1-Score越大則代表兩社區相似度越高，即恢復越準確。Jaccard越大，也代表著兩社區間區別越小，即恢復越準確。F1-Score和Jaccard系數分別定義如下

(8)

(9)

3.3 實驗設置

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

rwPISA[21]：基于隨機游走的冪次迭代局部社區發現算法；

rwLISA[21]：基于隨機游走的Lanczos迭代局部社區發現算法；

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

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

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

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

3.4 采樣方法對比

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

表2 不同采樣方法在不同數據集上覆蓋率對比

表3 不同采樣方法在不同數據集上ns對比

表4 不同采樣方法在不同數據上ns/n對比

表5 不同采樣方法在不同數據上時間復雜度對比

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

3.5 與其它方法對比

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

表6 F1-Score實驗結果對比

表7 Jaccard 系數實驗結果對比

表8 不同算法時間復雜度對比

由上述實驗數據可以發現，本文所提出的LRW-LSA方法在F1-Score和Jaccard系數上均優于對比方法。尤其在Orkut數據集上，相較于其它方法，LRW-LSA方法在復雜結構網絡也能獲得較好的預測能力。由此可見，LRW-LSA方法對于復雜的網絡結構有著更強的處理能力。

4 結束語

本文提出一種基于采樣和局部譜近似的局部社區發現方法，通過限制性隨機游走、快速聚類融合以及Lanczos迭代對目標社區進行高精確度的恢復。實驗結果表明，本文方法能有效提高恢復目標社區的精度，且對于復雜的網絡結構有著更強的處理能力?？梢姡疚乃岢龅腖RW-LSA方法有助于提高局部社區發現的精確度，然而，如何降低LRW-LSA時間復雜度仍存在不足，值得進一步優化，以實現更高效的局部社區發現算法。