基于稀疏子空間聚類的多層網絡社團檢測

孫登第，凌 媛，丁轉蓮，羅 斌

（1.安徽大學 計算機科學與技術學院，合肥 230601；2.安徽大學 互聯網學院，合肥 230039）

0 概述

社團檢測的目的是對復雜網絡中的節點進行劃分，使同類節點屬于相同的社團。通過社團檢測可以更好地理解復雜網絡的拓撲結構和功能特性，因此其對網絡分析與數據挖掘至關重要，目前被廣泛應用于機器學習［1］、計算機視覺［2］、圖像處理［3-4］等領域中。

近年來，已出現較多針對社團檢測問題的研究，如文獻［5］提出一種基于網絡拓撲與節點元數據的社團檢測算法，文獻［6］進行了局部優先的動態網絡重疊社團及其演變模式檢測，文獻［7］基于網絡社團檢測實現了電信客戶細分，文獻［8］提出了帶偏置信號傳播隨機游走的社團檢測算法，但這些工作主要集中于單層網絡，即網絡節點之間只存在一種關系的情況。然而在現實環境中，網絡可能同時具備多種連接類型，例如：在通信網絡中，存在用戶之間不同的通信方式，如電話、微信、微博等；在貿易網絡中，國家之間會有不同商品的貿易往來，如食品、衣服等。如果不考慮連接的多種形式而將這些網絡簡化為單一類型的交互，將無法捕獲系統、豐富而全面的內部結構。為了涵蓋這些關系的多類型特性，利用相同的節點集合分層描述不同連接，以形成多層網絡（也稱為多重網絡或復合網絡），并對其進行社團檢測顯然具有更強的科學意義。因此，此項技術引起了廣泛關注［9-11］。

多層網絡具有維度高、結構復雜、層間差異大的特點，許多算法無法有效地檢測其社團結構。隨著稀疏學習研究的不斷深入，各種子空間表示方法不斷涌現。2009 年，ELHAMIFAR 等［12］提出了稀疏子空間聚類模型，該模型的解具有塊對角結構，同一個塊的數據屬于同一子空間。然而，該方法單獨考慮每個數據的稀疏表示，缺乏對數據集全局結構的描述。2010年，LIU等［13］提出了基于低秩表示的子空間聚類方法（LRR），以捕獲數據集的全局結構。2018 年，FANG 等［14］通過將高斯場與調和函數合并到LRR 框架中，提出一種非負低秩表示方法，其在一個優化步驟中同時完成了相似度矩陣構建和子空間聚類。同年，WANG 等［15］提出一種局部與結構正則化的低秩表示方法（LSLRR），同時考慮了數據的局部幾何結構和全局塊對角線結構，改進了經典LRR 方法。2020 年，陶洋等［16］提出將對稱約束和結構約束融合到高維數據表示的低秩屬性中，同時捕獲高維數據的全局對稱結構和子空間的加權局部線性結構，以提高聚類性能。

子空間表示方法能夠準確描述數據分布，并通過子空間聚類自適應地將數據劃分到不同的子空間中，在網絡嵌入與聚類中體現出重要的應用價值。但現有的子空間聚類模型大多只適用于單層網絡，亟需將其推廣到多層網絡，深入挖掘層間的互補信息，實現多層融合與協同聚類。本文針對多層網絡的社團檢測問題，提出一種多層網絡稀疏子空間聚類方法。引入結構化的稀疏約束l2，1范數，并在迭代過程中更新不同層的權重，以描述各層網絡對社團檢測的重要程度。在此基礎上，設計交替方向乘子方法ADMM［17］，聯合優化層權重、節點稀疏表示和圖結構的魯棒性。

1 基于稀疏子空間聚類的社團檢測模型

如圖1 所示，本文研究的多層網絡是M個單層網絡的集合，表示為Gi(V，Ei)，i=1，2，…，M。每層網絡中的節點數相同(n=|V|)，但是連通模式和鏈路分布不同(mi=|Ei|)。該多層網絡可以用一組鄰接矩陣來進行表示，即A={A1，A2，…，AM}，其中，Ai??n×n表示第i層的鄰接矩陣。多層網絡中社團檢測的目的是推斷出最適合所有給定層共享的潛在社團分配。考慮每層包含的信息具有互補性，通過整合來自所有層的信息查找共享社團的過程也稱為網絡集成（融合）［18］。

圖1 多層網絡示意圖Fig.1 Schematic diagram of multi-layer network

1.1 節點相似性度量

與現有方法不同，本文提出的子空間聚類方法不直接作用在鄰接矩陣上，而是通過計算每個節點相對于網絡中所有其他節點的測地距離矢量來表示該節點。對于未加權的網絡，測地距離是沿最短路徑的2 個節點之間的鏈路數；對于加權圖，測地距離是沿最短路徑的鏈路的權重的總和。這樣就可以將每個節點都嵌入到高維幾何空間中。由于社團定義為具有更多組內鏈接和更少組間鏈接的節點組，因此同一社團中2 個節點之間的測地距離的期望值將小于2 個不同社團中2 個節點的測地距離的期望值。所以，在映射的幾何空間中，每個社團將分布于一個獨立的子空間中。盡管節點的嵌入維度與網絡中的節點數相同，但由于數據聚類的低秩特性，實際維度卻要小得多，具體取決于節點所在社團的大小。例如對于一個包含2 個社團的未加權無向網絡，節點標記為｛1，2，3｝和｛4，5，6｝，每個社團內部的3 個節點兩兩相連。在此網絡中，每個節點由測地距離矩陣P的1 列表示，如式（1）所示：

令pi為vi與所有vj?G的測地距離的集合，所有這些向量的集合為矩陣P??n×n，P=[p1，p2，…，p n]。P(i，j)是vi與vj之間的距離，并且P的所有對角線項均為零(P(i，i)=0)，即網絡沒有任何自環。進一步地，使用高斯核函數將測地距離向量pi轉換為相似性向量，如式（2）所示：

其中：σs控制衰減率；?表示點乘運算符。如果無法從節點vj到達節點vi，則P(i，j)=∞，S(i，j)=0。

1.2 多層網絡的聯合稀疏表示

基于上述表示形式，本文提出如下的聯合稀疏表示模型。受到稀疏聚類算法［12，19］的啟發，相同社團的節點在相同的稀疏子空間中，因此，每個節點都可以由剩余節點的線性組合稀疏地表示，即Sm=Sm Zm，Zm是稀疏表示系數矩陣。由于網絡中的數據會受到不同程度噪聲的干擾，因此為提高模型的魯棒性，本文引入噪聲矩陣，融合所有層的聯合稀疏表示如式（3）所示：

在現實世界中，通常不同層具有不同的信息量，因此，為每層分配一個自適應權重，從而使得本文方法能夠自適應地整合不同層的節點數據。將這些層權加到式（3）中，自適應權重的多層網絡聯合稀疏表示模型如式（4）所示：

其中：r=[r1，r2，…，rΜ]Τ是層權向量，rm表示第m層的權重；Γ表示rm的正則化，當允許它們單獨指定時，它可以避免rm的退化解，Γ是一個自適應參數，在第1 次迭代之后確定。

1.3 正則化的聯合稀疏表示學習

現有多數方法使用表示系數矩陣來定義圖的親和性：W=(|Z|+|ZΤ|)/2。雖然這種親和力在某種程度上是有效的，但它表示的含義已經不同于圖原始的定義［20］。該方法獲得的親和性圖矩陣會不可避免地存在一些元素是負數的情況，而矩陣中的元素對應圖中邊的權重，即節點間的關聯，所以，當出現邊權是負數時不能做出有意義的解釋。本文通過式（5）所示約束，直接學習出一個統一的、更能描述多層網絡中節點子空間一致性分布的協同親和圖G。

在式（5）中：δ和ω是平衡參數；1 表示單位矢量；G??n×n為期望的親和度矩陣，即要學習的協同親和圖；Gij為第i和第j節點來自同一社團的概率，通過計算跨層聯合表示Zi和Zj之間的距離來衡量；約束GΤ1=1 和G≥0 用于保證Gi概率性質；用于避免過擬合。

結合式（4）和式（5）可得到本文最終的模型，如式（6）所示。該模型框架如圖2 所示。

圖2 本文模型框架Fig.2 Framework of the proposed model

2 模型優化與求解

針對式（6）所示模型，本文設計了如下的優化求解算法。雖然式（6）具有較多變量，整體上非凸的，但是固定其他變量時，其每個變量的子問題都是凸的，并且具有閉合解。因此，本文使用交替方向乘子算法（ADMM）［17］將模型函數分離成具有閉合解的獨立子問題。引入輔助變量Qm??n×n和Pm??n×n，使得式（6）是可分離的，得到式（7）所示形式：

其 中：P=[P1，P2，…，PM]；Q=[Q1，Q2，…，QM]。將式（7）中的約束條件進一步轉化為式（8）所示的增廣拉格朗日函數：

3 實驗與結果分析

為驗證本文方法的有效性，采用多種數據集設計實驗。

3.1 數據集

在10 個現實世界的網絡上測試本文方法，以證明其在廣泛領域中的適用性。這些數據集的相關信息如下：

1）引文數據集，包括Citeseer、CoRA 數據集，分別有6 類3 312 份論文和7 類2 708 份論文。這2 個數據集都使用同樣的方法構建為兩層網絡，其中引文層表示論文之間的引用關系，相似層表示論文之間的文本相似性。

2）推特數據集，包括Football、Olympics、Politics數據集。Football 數據由推特上活躍的248 個足球運動員數據組成，根據所屬俱樂部劃為20 個類，這些球員的社交網絡被分為3 層，分別代表推特用戶之間的3 種交互方式；Olympics數據涵蓋了參與2012 年倫敦夏季奧運會的464 位運動員和組織數據，按28 個大項分類，本文使用與Football 數據集相同的方法來構造3 層；Politics 數據集為419 位來自英國的國會議員數據，依據政黨劃分為5 類，同樣構建3 層。

3）手機數據集MPD，由3 層組成，代表麻省理工學院中87 個用戶之間不同的聯系，包括物理位置、藍牙掃描和電話。

4）社交網絡數據集SND，由律師事務所的71 個員工數據組成，3 層網絡表示他們之間的3 種交互方式。

5）腦蟲網絡WBN，由代表神經元的279 個節點組成，通過5 種不同類型的鏈接相連，代表5 種不同類型的突觸，本文使用神經元類型作為真實標簽。

6）世界貿易網絡WTN，包含214 個國家之間的貿易關系，分別使用地理區域和經濟貿易類別作為標簽，因此產生WTN（reg）和WTN（cat）2 種網絡。

實驗中使用的數據集的節點數目、層數目和真實類數目如表1 所示。

表1 多層網絡數據集Table 1 Multi-layer network datasets

3.2 參數設置

由于式（8）中的參數較多，并且對于不同的數據集各參數都會相應變化，因此在實驗中反復調整力求結果較優，不同數據集中的參數設置如表2 所示。為了便于調參，在實驗中將λ和γ設置為相同的值，并且在所有的數據集中設置ξ=3。此外，通過實驗驗證參數的選取。

表2 各數據集中的參數設置Table 2 Parameter settings in each dataset

3.3 比較方法

選取單層網絡和多層網絡2 類方法進行比較。

1）單層網絡方法。為了與已有的子空間聚類方法進行比較，選擇最具有代表性的SSC［12］、LRR［13］、和SSCF［22］方法，但是子空間聚類方法目前僅應用于單層網絡中，為了將它們應用于多層網絡，首先將所有網絡層合并為一個由以下鄰接矩陣描述的單層網絡：A=。此外，還與Ncut［23］方法進行比較，以驗證本文方法的有效性。

2）多層網絡方法。將本文方法與當前具有代表性的多層網絡社團檢測方法進行比較，分別是基于矩陣分解的CSNMF 方法［24］和LMF 方法［25］、基于信息融合的SNF 方法［26］、基于譜聚類的SC-ML 方法［27］，為了展現公平性，所有的實驗以最佳結果進行對比。

3.4 評估指標

采用以下3種廣泛使用的評估指標：純度（Purity）［28］，規一化互信息（NMI）［29］，準確性（ACC）［30］。這3 個指標都提供了一種定量方法來比較計算的社團聚類Ω={φ1，φ2，…，φκ}和真實標簽C={c1，c2，…，cκ}。

正確分類的節點數的百分比如式（9）所示：

其中：n是節點總數；|φk∩cj|表示φk與cj的交集的節點數。

為了平衡社團聚類的質量與數量，使用NMI 指標，其定義如式（10）所示：

其中：I表示節點簇Ω與真實類C之間的互信息；H(Ω)和H(C)分別表示簇和類的熵。

給定一個包含n個頂點的數據集，對于每個樣本網絡，令ψi為通過應用不同方法獲得的聚類標簽，而ζi為該數據集提供的真實標簽，被正確分配的節點的百分比如式（11）所示：

其 中：δ(x，y) 是delta 函數，即當x和y相等時，δ(x，y)=1，否則等于0；map(ψi)是將每個社團標簽ψi映射到數據集中等效標簽的映射函數。

3.5 計算復雜度和收斂性分析

利用O標記簡要分析本文模型的計算復雜度。在算法1 中，當不考慮基本的矩陣運算，如矩陣相加、矩陣相乘時，最大的計算成本是矩陣的逆運算，對于大小為n×n的矩陣，逆運算的計算復雜度為O（n3），由于在Z 和P的更新過程中存在逆運算，因此算法1 的總計算復雜度約為Ο(2τn3)，其中，τ是迭代次數。

此外，本文采用ADMM 算法求解所提出的多層網絡聯合稀疏表示模型。由于目標函數較為復雜，因此基于梯度的方法不能保證找到最佳解。為驗證所得優化路徑，在多層網絡上進行收斂性實驗。對于每一個網絡，在每次迭代后保存目標函數l的值，并將其繪制為波形圖。SND、Football、Olympics 和WTN 網絡上的實驗結果如圖3 所示，從波形圖中可以發現，目標函數l快速收斂并趨于穩定。因此，實驗結果驗證了本文方法的收斂性。在其他網絡中也具有類似的結果。

圖3 收斂性對比Fig.3 Comparison of convergence

3.6 參數分析

本文方 法的參數σs、λ、δ、ω對實驗結果的影響如圖4 所示，為保持參數選取標準的一致性，選擇NMI 作為主要評估指標。可以看出，結果與上文分析保持一致。此外還可以看出，對不同的數據庫，參數曲線在每個參數最優值兩側較長的一段中均保持平穩，表明本文方法對參數具有一定的魯棒性。

圖4 不同參數對實驗結果的影響Fig.4 Influence of different parameters on experimental results

3.7 社團檢測實驗結果

本文方法和其他8 種方法在Purity、NMI、ACC 3 種指標下的實驗結果如表3～表5 所示，最優結果用黑體表示。可以看出，本文方法在大部分數據集中都能達到最優。值得注意的是，在推特數據集的3 個網絡中（Football、Olympics、Politics），所有方法的結果都很理想，這是因為該數據集中網絡層的社團內部連接較為緊密，社團結構較為清晰，有利于進行社團檢測。本文方法無規律地略低于某些方法，這源于優化過程中的參數設置與迭代次數導致的精度誤差。但是，在網絡社團結構較差的Citeseer 和CoRA 中，本文方法明顯優于其他所有比較方法，說明本文方法可以挖掘不同層的互補信息，得到更為準確的一致性聯合稀疏表示。此外，從與單層的子空間分割算法（LRR、SSC、SSCF）的比較可以看出，本文方法中加入的距離正則項和自適應權重對子空間分割產生了積極的作用，大幅提高了聚類性能。

表3 不同方法檢測精度比較（Purity）Table 3 Accuracy comparison of different methods（Purity）

表4 不同方法檢測精度比較（NMI）Table 4 Accuracy comparison of different methods（NMI）

表5 不同方法檢測精度比較（ACC）Table 5 Accuracy comparison of different methods（ACC）

4 結束語

為解決多層網絡中的社團檢測問題，本文提出一種基于子空間分割的多層網絡聯合稀疏表示方法。不同于傳統的單層網絡分割與平均疊加的思路，本文將距離正則項和非負約束條件共同集成到SSC 框架中，同時利用數據的全局和局部信息進行圖學習，并且在模型中引入l2，1范數，促使學習到的協同親和圖具有更清晰的聚類結構。此外，整合互補層的信息并考慮不同層的重要性，設計基于ADMM 的迭代算法來優化模型。下一步將通過優化算法參數，擴大本文方法的適用性。