基于超圖和K-means改進的異質網絡社區發現算法

趙宇紅 張曉楠(內蒙古科技大學信息工程學院 內蒙古 包頭 014010)

0 引 言

信息網絡是對復雜關聯系統的抽象概括，表達了系統中的實體及實體間的關系。信息網絡的實例包括社交網絡、交通網絡和生物網絡等。挖掘信息網絡的結構特性、演化規則和實體特征對于理解和應用信息網絡有著重要意義。

信息網絡的社區發現研究[1-2]就是挖掘和發現關聯緊密的實體群組，準確的社區發現既可以幫助人類了解網絡結構的演化規則，也可以發現個體特征在群組形成中的作用，社區發現可以支持網絡分析、用戶管理、面向群組的網絡應用。例如，廣告投放、商品推薦和輿情監測都是社區發現的典型應用。大多數社區發現算法的研究，都是在同質網絡中展開的，即將網絡中所有節點和節點間的連接都定義為同一種類型。基于同質網絡的社區發現研究可挖掘潛在的群組結構，也實現了眾多有重要影響的應用。然而，實際生活中大多數網絡都是異質的，近些年，異質網絡[3]這一概念受到很多關注。異質網絡與實際網絡相符合，節點及節點間的關系是多種類型的，這種多類型的節點和連接關系使網絡變得異常復雜，如何能夠準確且全面地度量多類型節點以及節點之間錯綜復雜的多種關聯，異質網絡的提出給社區發現研究帶來了巨大挑戰。本文提出一種適用于異質網絡，邏輯清晰、復雜度低且具有高準確度的社區發現算法。

算法首先使用超圖[4]數據模型對異質信息網絡進行建模，利用網絡表示學習方法DeepWalk算法[5]對異質信息網絡中的節點進行訓練學習，得到節點的低維向量化表示。另外，針對K-means[6]聚類中心隨機選取容易造成社區劃分結果不穩定，即聚類中心的敏感性問題，提出一種新的聚類中心選取方法，基于DeepWalk所獲得的節點向量信息重新定義了節點間距離度量，結合改進的K-means算法實現了異質網絡的社區發現，本文提出的基于超圖和DeepWalk改進的K-means算法，簡稱為HD-K-means算法，算法在仿真實驗中效果良好。

1 社區發現方法

Girvan等[7]提出了GN算法，利用邊界數對社區進行劃分。GN算法是一個有效的社區發現算法，但算法的復雜度較高。接著Gregory[8]提出了一種基于GN的改進算法CONGA，降低了算法的復雜度。之后，許多學者又相繼提出了K-means、HLCD[9]和基于邊緣加權[10]等社區發現算法，但這些算法都是基于同質信息網絡結構的。

近年來，一些基于異質信息網絡的社區發現算法相繼被提出。其中主成分分析(Principal Component Analysis，PCA)[11]是一種具有代表性的異質信息網絡社區發現方法。PCA通過降維把各維度數據進行線性無關的表示，繼而對主要的數據特征進行提取，實現社區劃分。PCA具有無監督性，在計算過程中無法使用類別先驗知識。之后，一種有監督性的社區發現方法線性判別分析(Linear Discriminant Analysis，LDA)[12]被提出，在該算法中，LDA將數據在低維向量進行投影，利用投影后的數據更容易被區分這一特點來達到社區劃分的目的。然而，通過PCA和LDA劃分出來的數據有正有負，在現實世界里，負數值的存在沒有實際的意義。針對這一問題，非負矩陣分解算法(Non-negative Matrix Factorization，NMF)[13]被提出，算法將一個非負的原始矩陣分解成兩個非負矩陣相乘的形式來達到社區劃分的目的。

然而，大多數基于異質信息網絡的社區發現方法往往存在過程復雜、不易理解、復雜度高等問題。一些基于同質信息網絡的社區發現方法，如K-means算法，具有邏輯簡單、便于理解且易實現的特點。但是傳統的K-means算法本身存在聚類中心選取隨機性的問題，且是基于同質網絡結構設計的。本文提出一種基于超圖和DeepWalk改進的K-means異質網絡社區發現算法HD-K-means，該算法繼承了傳統K-means算法簡單高效的特點，改進了K-means的聚類中心隨機選取問題，同時也考慮了異質網絡的多類型節點及關系。

2 算法設計

2.1 傳統的K-means算法

聚類是社區發現算法中一種重要且常用的方法。作為一種經典的聚類算法，K-means原理簡單，易于實現，且復雜度低。K-means算法通過對網絡中的節點進行聚類來挖掘節點之間潛在的關系。其主要的思想如下：

(1) 隨機選取K個初始聚類中心，生成對應的K個簇。

(2) 遍歷所有節點，依據“距離”實現相似度度量，將每個節點劃分到“最近的”聚類中心所在的簇。

(3) 更新聚類中心為每簇的均值。

(4) 重復步驟(2)-步驟(3)，直到K個簇的中心點不再變化，或者達到預設的迭代次數為止。

在傳統的K-means算法中，聚類中心是隨機選取的，這造成了極大敏感性，極易使得聚類結果陷入局部最優解。此外，K值的選取也是一個非常重要的問題。

2.2 HD-K-means算法的基本思想

傳統的K-means算法是一種基于同質網絡的社區發現算法，網絡中的節點都是由二維向量來表示的。通過歐氏距離來計算節點間的距離，衡量節點間的相似度，進而實現聚類。基于同質網絡的節點向量表示忽略節點的類型和節點之間可能存在的復雜關系這一實際情況，針對這一問題，本文提出一種基于超圖建模的方法，利用超圖表示不同類型節點間的復雜關系，之后通過DeepWalk算法實現對異質網絡中的節點向量表示學習，得到更加準確的節點向量低維表示，使節點間的距離度量(即相似度)更加準確。

在K-means算法中聚類中心的選取對于整個聚類結果的好壞起著至關重要的作用，即聚類中心敏感性問題?？赡苡捎谶x取的聚類中心不同，最后得到的社區劃分的結果也不同，本文針對K-means算法的這一不足，提出一種新的聚類中心選取方法。一種基于密度基尼系數的選取方法。HD-K-means算法流程如圖1所示。算法首先利用超圖建模，通過DeepWalk算法在異質信息網絡下得到節點的向量表示，基于密度基尼系數選取聚類中心，利用Skip-gram模型訓練學習所獲得的節點向量計算節點距離(即相似度)完成聚類，最終得到社區發現結果。

2.2.1基于超圖和DeepWalk的異質網絡表示學習

網絡表示學習(Network Representation Learning,NRL)[14]也被稱為圖嵌入法(Graph Embedding Method,GEM)，旨在將網絡中的節點表示成低維、稠密的向量形式，該形式可以在向量空間中具有表示以及推理能力，進而可將得到的向量表示運用到社區發現、鏈路預測、可視化分類，以及節點分類等任務中。Word2vec[15]在自然語言處理中，將關聯的上下文詞信息經訓練學習表示為低維詞向量形式，詞向量應用于情感分析、翻譯及語言學中，且取得了顯著的效果?；谶@個思想，在網絡空間模型中，DeepWalk 算法被提出，該算法把網絡中的節點表示為自然語言中的單詞。把節點生成的序列看作是自然語言模型中的句子，在深度學習的基礎上將異質信息網絡中的節點表示成低維的向量形式。

本文使用網絡表示學習中的DeepWalk算法實現對節點的低維向量表示。DeepWalk算法首先通過隨機游走生成一個游走序列，再基于Skip-gram模型進行節點序列訓練，輸出節點的低維向量表示。

但是DeepWalk算法是基于同質網絡結構的，為了能夠使該算法全面學習異質網絡中的節點與節點的關聯信息，引入超圖實現對異質信息網絡的建模，在超圖中嵌入DeepWalk算法完成對異質信息網絡的表示學習。

(1) 基于超圖的深度隨機游走。超圖，可以把不同類型的節點、不同語義的邊表達在一個網絡中，從而來表示異質信息網絡中的多類型節點及復雜關系。超圖由超邊集和節點集構成，一條超邊包含多個節點，超圖的超邊異質性和節點的多樣性，可以更全面地呈現網絡中的復雜關系，有助于支持更豐富的網絡結構信息的挖掘。

超圖的結構如圖2所示。

圖2 超圖的結構

首先，利用超圖對異質信息網絡進行建模。在異質信息網絡中，通過異質網絡中復雜的節點關系進行隨機游走，在給定當前根節點v的情況下，首先隨機選取一個與v相關的超邊e，然后隨機地選取下一個節點vx∈e，最終得到步長為l的節點序列ωv。傳統DeepWalk算法中，網絡中的節點是基于等概率隨機游走得到游走序列，但實際網絡中關系越緊密的兩個節點之間應該有更高的轉移概率，通過轉移概率得到下一個可能游走到的節點。模型的轉移概率可以通過式(1)進行計算。

(1)

最終，節點v在進行γ次游走之后，得到γ個深度隨機游走序列。將隨機游走序列、滑動窗口大小c作為Skip-gram模型的輸入進行節點訓練，得到節點的向量表示φ。

(2) Skip-gram模型。Skip-gram模型包括輸入層、映射層和輸出層。它通過一個改進的神經網絡模型進行節點向量的訓練。該模型結構如圖3所示。

圖3 Skip-gram模型結構

Skip-gram模型是一種語言模型，它可以在已知中心詞的情況下，預測其所在句子的上下文。引入Skip-gram模型可以通過某個節點和其所在的節點序列來預測該節點的鄰居節點。圖3中，ω(t)表示當前輸入節點，與傳統的神經網絡模型相比所不同的是，輸入節點不是標量值，而是一個向量，即不只表示大小，還表示方向，使用one-hot的形式表示。在映射層中，Skip-gram將所有輸入的節點的累計作為一個向量，投影到輸出層。輸出層為中間節點上下鄰居節點向量。

經過Skip-gram模型學習輸出的低維節點向量，是以超圖深度游走的游走序列的輸入訓練所獲取的，游走序列中獲取節點的順序表達了節點間的關聯程度，在深度學習下，更精確地表示了異質網絡節點的信息，從而也提高了本文提出的HD-K-means算法中節點間距離度量(即相似度)結果的準確性。

2.2.2聚類中心的選取

通常作為聚類中心的點應具有如下特征：(1) 密度往往比與其相鄰的其他節點的密度大；(2) 各個聚類中心之間相距往往較遠?；诰垲愔行牡倪@兩個特點，本文提出一種基于密度基尼系數的聚類中心的選取方法。

輸入：節點集X={x1,x2,…,xn}(n是節點的數量)，社區個數為K。

輸出：劃分好的K個社區。

(1) 首先計算節點集X中的任意節點xi的局部密度ρxi。以xi點為圓心，dc為半徑，ρxi的計算式表示為：

(2)

(3)

式中：χ(x)是密度基尼系數估計的函數；dij表示節點xi到節點xj的距離，xi和xj是節點集X中的任意兩個節點。ρxi的值越大，說明節點xi的密度越大，通過計算得到密度最大的節點xi作為第一個聚類中心。

(2) 通過計算其他剩余節點到第一個聚類中心的距離，距離最大的節點即為第二個聚類中心，再重新計算剩余節點到第一個聚類中心和第二個聚類中心的距離，距離最大節點為第三個聚類中心。依次計算，直到選出K個初始聚類中心。

(3) 將網絡中的節點根據距離(即相似度)進行聚類，最終得到K個社區劃分結果。

基于超圖利用DeepWalk算法獲得異質信息網絡中節點的向量表示，假定φ(xi)=[xi1xi2…xid]表示節點集X中任意節點xi的向量，d表示輸出維度。本文使用歐氏距離來度量節點間的距離,計算式表示為：

(4)

本文提出的聚類中心選取方法，根據定義的節點密度，對網絡中的節點進行密度排序，依據節點密度值的大小選取初始聚類中心，解決了聚類中心的選取敏感性，消除局部最優解問題，從而使得社區劃分更為穩定、準確。

2.3 參數的取值

DeepWalk算法參數的取值：窗口大小c=5；以每個節點開始的路徑數量γ=10；每條路徑的長度l=40；輸出維度d=64。

半徑dc的取值:基尼系數[16]是關于系統不確定性的度量，基尼系數越大，說明系統的不確定性越大；反之，說明系統的不確定性越小?；嵯禂涤嬎闶奖硎緸椋?/p>

(5)

式中：n指節點的總數量；Pi指第i類節點的數量占總數量節點的比例。半徑dc的設置定義了局部結構范圍，也影響了節點的密度。如果dc的值過大，會導致關聯不緊密的節點也聚類在一個簇中，如果dc的值過小，則會導致一個簇的分裂，這種隨機性決定了半徑dc也是一個不確定性的度量，因此，引入基尼系數解決半徑dc的合理設置問題。給定n個節點的局部密度估計ρ1,ρ2,…,ρn。如果節點的局部密度值越小，則說明節點分布的不確定性越大，具有最大基尼系數。由此可以引入密度基尼系數衡量節點局部密度估計聚類中心選取的合理性，密度基尼系數用H表示。H和Q的計算式分別表示為：

(6)

(7)

式中：參數Q指的是n個節點的總密度。通過式(6)分析參數半徑dc不斷增大密度基尼系數H的變化，當H最大時所對應的dc即為最佳的局部密度計算所設定的半徑值。

社區數K的取值：傳統的K-means算法中K值的計算是一個非常經典的問題，有不少學者就此問題給出了很多解決方案[17-18]。本文采用Elbow method即肘方法[18]。對于n個節點的數據集，迭代計算K的值從1取到n。在每次社區劃分結束之后，計算其他節點到簇心的距離的平方和，當K值不斷增加，距離的平方和就逐漸減少，節點的聚類會更加準確，每個簇的內部聚合程度會逐漸提高，距離的平方和自然會逐漸減小。當K值小于最佳聚類數時，隨著K的增大會大幅度增加每個簇的聚合程度，所以距離的平方和下降的速度比較快；當K達到最佳的聚類數時，再增加K值聚合程度會迅速變小，距離的平方和下降幅度會驟減，然后隨著K值的繼續增大趨于平緩。所以我們根據距離平方和和K值得到一個手肘形狀的關系圖，而這個“肘”點對應的K值即為最佳的聚類數。

3 實驗與結果分析

實驗環境以及平臺是Intel(R) Core(TM)i7-8700處理器、32 GB內存。運行環境為Python3.7。

3.1 相關數據集的介紹

該實驗在兩個真實的異質信息網絡數據集下面進行有效驗證，數據集的詳細介紹如下。

DBLP數據集：一個作者合作網絡,網絡中包含作者、論文、類型和會議四種類型的節點，不同類型節點之間包含不同的連接關系。

Aminer數據集:一個作者合作網絡數據集，網絡中包含四種類型的節點。與DBLP不同的是，這四種類型的節點分別是作者、論文、會議和參考。節點之間通過潛在的關系進行連接。數據集的統計情況如表1所示，其中：n代表數據集中的節點數；e代表節點之間的連邊數；K代表社區數。

表1 數據集參數

3.2 評價標準

使用準確率precision和標準化互信息NMI作為評價指標。準確率precision可以作如下定義：在給定的數據集中，劃分正確的節點數據與總節點數據的比值。計算式表示為：

(8)

式中：對于函數ζ(x,y)，如果x=y，函數值為1，否則，其值為0；對于任意的節點i，lpi為通過社區劃分算法得到的結果，lti為節點i實際所歸屬的社區；n表示總的節點個數。準確率的值越大，說明社區劃分的結果越準確。

標準化互信息(Normalized Mutual Information,NMI)用于衡量社區劃分結果的準確度，取值在0到1之間，NMI計算式表示為：

(9)

3.3 實驗驗證

3.3.1基于密度基尼系數半徑dc的設置驗證

半徑dc的設置直接影響到初始聚類中心的選擇。為克服dc的不確定性，提出一種基于密度基尼系數的算法。仿真實驗中，對參數半徑dc的敏感性及選擇算法的有效性進行分析與驗證。實驗結果如圖4所示，其中橫軸為半徑dc的取值(0.1～0.8)，以0.1為步長不斷增加，縱坐標是相應半徑下對應的密度基尼系數值。

隨著半徑dc的不斷增加，密度基尼系數H也會不斷增加，系統的不確定性不斷減小，在某個半徑dc值下密度基尼系數H達到最大，系統的不確定性達到最小，此時的半徑dc值為0.36。隨著半徑dc的值不斷增大，密度基尼系數H開始不斷減小，系統的不確定性開始增加。那么，當系統的不確定性最小，即半徑dc等于0.36為最佳dc值。

通過評價指標NMI和準確率實驗對本文算法進行驗證，結果如圖5和圖6所示。

圖5 不同的dc值在DBLP和Aminer數據集下的NMI值

圖6 不同的dc值在DBLP和Aminer數據集下的precision值

將NMI作為評價指標，通過數據集DBLP和Aminer驗證半徑dc的取值是否準確。如圖5所示，半徑dc的值從0.1開始到0.8不斷增大，當半徑dc的值為0.36時，分別得到DBLP數據集和Aminer數據集下對應的最大NMI值。可以得出，本文提出的參數dc值的設定是可行的，并且取得了較好的效果。

在圖6中，將precision作為評價指標，通過數據集DBLP和Aminer驗證半徑dc的取值是否準確。通過驗證，最終得到的半徑dc的值，是一個最優的參數值，可以得到準確的社區劃分結果。

3.3.2社區發現準確性的驗證

實驗中，首先利用肘方法和節點密度估計合理性來確定聚類個數K和參數dc的值。其次，為了保證準確性，讓每次實驗都在給定的網絡數據集中重復20次，度量指標取實驗的平均值。接著將本文提出的HD-K-means與傳統的K-means、基于特征提取進行社區劃分的主成分分析(PCA)、具有拓撲結構發現的非負矩陣分解(NMF)三種社區發現算法在異質信息網絡數據集下作對比，驗證HD-K-means算法社區劃分的效果。實驗結果如表2所示。

通過NMI和precision值來觀察社區劃分結果。將本文提出的HD-K-means算法與傳統的K-means算法作比較，該算法使用超圖建模，更全面地表示網絡中不同類型節點的復雜連接關系，并利用DeepWalk算法得到節點的低維向量表示，以獲得節點間更準確的距離度量。仿真實驗表明，在異質信息網絡中HD-K-means算法能夠得到更好的社區劃分結果，且改善了傳統K-means算法的聚類中心選擇敏感性問題。另外，HD-K-means算法與其他三種異質網絡社區劃分方法的對比結果表明，本文提出的HD-K-means算法在評價指標NMI和precision上均有所提升。仿真實驗驗證了該方法適用于異質信息網絡，且可以得到更準確的社區劃分結果。

4 結 語

本文研究并提出一種應用于異質信息網絡的社區發現算法HD-K-means，算法在網絡表示學習的支持下獲得節點向量表示，并將得到的節點向量根據歐氏距離計算節點距離(即相似度)，使用密度基尼系數選取聚類中心，結合節點距離進行聚類并最終得到社區劃分結果。該方法在異質信息網絡中繼承了傳統K-means算法邏輯簡單、易于實現的特點，與此同時，基于密度基尼系數聚類中心的選取方法與傳統K-means算法相比，無須迭代計算即可得到聚類中心，降低了算法的復雜度。最終，通過實驗驗證了HD-K-means算法可行性和有效性。