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

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

0 概述

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

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

多層網(wǎng)絡(luò)具有維度高、結(jié)構(gòu)復(fù)雜、層間差異大的特點，許多算法無法有效地檢測其社團(tuán)結(jié)構(gòu)。隨著稀疏學(xué)習(xí)研究的不斷深入，各種子空間表示方法不斷涌現(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 框架中，提出一種非負(fù)低秩表示方法，其在一個優(yōu)化步驟中同時完成了相似度矩陣構(gòu)建和子空間聚類。同年，WANG 等［15］提出一種局部與結(jié)構(gòu)正則化的低秩表示方法（LSLRR），同時考慮了數(shù)據(jù)的局部幾何結(jié)構(gòu)和全局塊對角線結(jié)構(gòu)，改進(jìn)了經(jīng)典LRR 方法。2020 年，陶洋等［16］提出將對稱約束和結(jié)構(gòu)約束融合到高維數(shù)據(jù)表示的低秩屬性中，同時捕獲高維數(shù)據(jù)的全局對稱結(jié)構(gòu)和子空間的加權(quán)局部線性結(jié)構(gòu)，以提高聚類性能。

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

1 基于稀疏子空間聚類的社團(tuán)檢測模型

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

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

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

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

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

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

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

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

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

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

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

在式（5）中：δ和ω是平衡參數(shù)；1 表示單位矢量；G??n×n為期望的親和度矩陣，即要學(xué)習(xí)的協(xié)同親和圖；Gij為第i和第j節(jié)點來自同一社團(tuán)的概率，通過計算跨層聯(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）所示模型，本文設(shè)計了如下的優(yōu)化求解算法。雖然式（6）具有較多變量，整體上非凸的，但是固定其他變量時，其每個變量的子問題都是凸的，并且具有閉合解。因此，本文使用交替方向乘子算法（ADMM）［17］將模型函數(shù)分離成具有閉合解的獨立子問題。引入輔助變量Qm??n×n和Pm??n×n，使得式（6）是可分離的，得到式（7）所示形式：

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

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

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

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

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

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

2）推特數(shù)據(jù)集，包括Football、Olympics、Politics數(shù)據(jù)集。Football 數(shù)據(jù)由推特上活躍的248 個足球運動員數(shù)據(jù)組成，根據(jù)所屬俱樂部劃為20 個類，這些球員的社交網(wǎng)絡(luò)被分為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）手機(jī)數(shù)據(jù)集MPD，由3 層組成，代表麻省理工學(xué)院中87 個用戶之間不同的聯(lián)系，包括物理位置、藍(lán)牙掃描和電話。

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

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

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

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

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

3.2 參數(shù)設(shè)置

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

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

3.3 比較方法

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

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

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

3.4 評估指標(biāo)

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

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

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

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

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

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

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

3.5 計算復(fù)雜度和收斂性分析

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

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

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

3.6 參數(shù)分析

本文方 法的參數(shù)σs、λ、δ、ω對實驗結(jié)果的影響如圖4 所示，為保持參數(shù)選取標(biāo)準(zhǔn)的一致性，選擇NMI 作為主要評估指標(biāo)?？梢钥闯觯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 社團(tuán)檢測實驗結(jié)果

本文方法和其他8 種方法在Purity、NMI、ACC 3 種指標(biāo)下的實驗結(jié)果如表3～表5 所示，最優(yōu)結(jié)果用黑體表示?？梢钥闯?，本文方法在大部分?jǐn)?shù)據(jù)集中都能達(dá)到最優(yōu)。值得注意的是，在推特數(shù)據(jù)集的3 個網(wǎng)絡(luò)中（Football、Olympics、Politics），所有方法的結(jié)果都很理想，這是因為該數(shù)據(jù)集中網(wǎng)絡(luò)層的社團(tuán)內(nèi)部連接較為緊密，社團(tuán)結(jié)構(gòu)較為清晰，有利于進(jìn)行社團(tuán)檢測。本文方法無規(guī)律地略低于某些方法，這源于優(yōu)化過程中的參數(shù)設(shè)置與迭代次數(shù)導(dǎo)致的精度誤差。但是，在網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)較差的Citeseer 和CoRA 中，本文方法明顯優(yōu)于其他所有比較方法，說明本文方法可以挖掘不同層的互補(bǔ)信息，得到更為準(zhǔn)確的一致性聯(lián)合稀疏表示。此外，從與單層的子空間分割算法（LRR、SSC、SSCF）的比較可以看出，本文方法中加入的距離正則項和自適應(yīng)權(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)絡(luò)中的社團(tuán)檢測問題，本文提出一種基于子空間分割的多層網(wǎng)絡(luò)聯(lián)合稀疏表示方法。不同于傳統(tǒng)的單層網(wǎng)絡(luò)分割與平均疊加的思路，本文將距離正則項和非負(fù)約束條件共同集成到SSC 框架中，同時利用數(shù)據(jù)的全局和局部信息進(jìn)行圖學(xué)習(xí)，并且在模型中引入l2，1范數(shù)，促使學(xué)習(xí)到的協(xié)同親和圖具有更清晰的聚類結(jié)構(gòu)。此外，整合互補(bǔ)層的信息并考慮不同層的重要性，設(shè)計基于ADMM 的迭代算法來優(yōu)化模型。下一步將通過優(yōu)化算法參數(shù)，擴(kuò)大本文方法的適用性。