孫登第，凌 媛，丁轉(zhuǎn)蓮，羅 斌

（1.安徽大學 計算機科學與技術(shù)學院，合肥 230601；2.安徽大學 互聯(lián)網(wǎng)學院，合肥 230039）

0 概述

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

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

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

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

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

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

圖1 多層網(wǎng)絡示意圖Fig.1 Schematic diagram of multi-layer network

1.1 節(jié)點相似性度量

與現(xiàn)有方法不同，本文提出的子空間聚類方法不直接作用在鄰接矩陣上，而是通過計算每個節(jié)點相對于網(wǎng)絡中所有其他節(jié)點的測地距離矢量來表示該節(jié)點。對于未加權(quán)的網(wǎng)絡，測地距離是沿最短路徑的2 個節(jié)點之間的鏈路數(shù)；對于加權(quán)圖，測地距離是沿最短路徑的鏈路的權(quán)重的總和。這樣就可以將每個節(jié)點都嵌入到高維幾何空間中。由于社團定義為具有更多組內(nèi)鏈接和更少組間鏈接的節(jié)點組，因此同一社團中2 個節(jié)點之間的測地距離的期望值將小于2 個不同社團中2 個節(jié)點的測地距離的期望值。所以，在映射的幾何空間中，每個社團將分布于一個獨立的子空間中。盡管節(jié)點的嵌入維度與網(wǎng)絡中的節(jié)點數(shù)相同，但由于數(shù)據(jù)聚類的低秩特性，實際維度卻要小得多，具體取決于節(jié)點所在社團的大小。例如對于一個包含2 個社團的未加權(quán)無向網(wǎng)絡，節(jié)點標記為｛1，2，3｝和｛4，5，6｝，每個社團內(nèi)部的3 個節(jié)點兩兩相連。在此網(wǎng)絡中，每個節(jié)點由測地距離矩陣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)，即網(wǎng)絡沒有任何自環(huán)。進一步地，使用高斯核函數(shù)將測地距離向量pi轉(zhuǎn)換為相似性向量，如式（2）所示：

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

1.2 多層網(wǎng)絡的聯(lián)合稀疏表示

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

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

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

1.3 正則化的聯(lián)合稀疏表示學習

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

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

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

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

2 模型優(yōu)化與求解

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

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

3 實驗與結(jié)果分析

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

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

在10 個現(xiàn)實世界的網(wǎng)絡上測試本文方法，以證明其在廣泛領域中的適用性。這些數(shù)據(jù)集的相關信息如下：

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

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

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

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

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

6）世界貿(mào)易網(wǎng)絡WTN，包含214 個國家之間的貿(mào)易關系，分別使用地理區(qū)域和經(jīng)濟貿(mào)易類別作為標簽，因此產(chǎn)生WTN（reg）和WTN（cat）2 種網(wǎng)絡。

實驗中使用的數(shù)據(jù)集的節(jié)點數(shù)目、層數(shù)目和真實類數(shù)目如表1 所示。

表1 多層網(wǎng)絡數(shù)據(jù)集Table 1 Multi-layer network datasets

3.2 參數(shù)設置

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

表2 各數(shù)據(jù)集中的參數(shù)設置Table 2 Parameter settings in each dataset

3.3 比較方法

選取單層網(wǎng)絡和多層網(wǎng)絡2 類方法進行比較。

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

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

3.4 評估指標

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

正確分類的節(jié)點數(shù)的百分比如式（9）所示：

其中：n是節(jié)點總數(shù)；|φk∩cj|表示φk與cj的交集的節(jié)點數(shù)。

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

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

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

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

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

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

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

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

3.6 參數(shù)分析

本文方 法的參數(shù)σs、λ、δ、ω對實驗結(jié)果的影響如圖4 所示，為保持參數(shù)選取標準的一致性，選擇NMI 作為主要評估指標?？梢钥闯觯Y(jié)果與上文分析保持一致。此外還可以看出，對不同的數(shù)據(jù)庫，參數(shù)曲線在每個參數(shù)最優(yōu)值兩側(cè)較長的一段中均保持平穩(wěn)，表明本文方法對參數(shù)具有一定的魯棒性。

圖4 不同參數(shù)對實驗結(jié)果的影響Fig.4 Influence of different parameters on experimental results

3.7 社團檢測實驗結(jié)果

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

表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 結(jié)束語

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