基于改進(jìn)對稱二值非負(fù)矩陣分解的重疊社區(qū)發(fā)現(xiàn)方法

成其偉，陳啟買，賀超波，劉 海

（1.華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州 510631；2.仲愷農(nóng)業(yè)工程學(xué)院信息科學(xué)與技術(shù)學(xué)院，廣州 510225）

（?通信作者電子郵箱hechaobo@foxmail.com）

0 引言

復(fù)雜網(wǎng)絡(luò)常用于表示各類復(fù)雜系統(tǒng)組成部分的交互關(guān)系，它在現(xiàn)實(shí)世界中的各個領(lǐng)域都廣泛存在，例如科技文獻(xiàn)領(lǐng)域的合著關(guān)系網(wǎng)絡(luò)、信息服務(wù)領(lǐng)域的在線社交網(wǎng)絡(luò)以及生物信息領(lǐng)域的蛋白質(zhì)交互網(wǎng)絡(luò)等。由于各類復(fù)雜網(wǎng)絡(luò)常常蘊(yùn)藏著豐富且有價(jià)值的信息，對復(fù)雜網(wǎng)絡(luò)進(jìn)行分析與挖掘已吸引了大量研究人員的關(guān)注，而社區(qū)發(fā)現(xiàn)是其中重要研究課題。社區(qū)發(fā)現(xiàn)目的在于發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)聚簇，要求同一個聚簇內(nèi)的節(jié)點(diǎn)間鏈接稠密，而不同聚簇的節(jié)點(diǎn)間鏈接稀疏［1］。有效的社區(qū)發(fā)現(xiàn)不僅能夠揭示復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特征和預(yù)測其發(fā)展趨勢，而且還具有很好的應(yīng)用價(jià)值，例如，通過對在線社交網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)，可以找出具有相似興趣且關(guān)系密切的用戶群體并進(jìn)行產(chǎn)品推薦，從而實(shí)現(xiàn)精準(zhǔn)的社會化營銷并提高推薦的轉(zhuǎn)化率［2］。

復(fù)雜網(wǎng)絡(luò)的社區(qū)不僅具有成員節(jié)點(diǎn)連接緊密的特點(diǎn)，而且通常還具有重疊性，即一個節(jié)點(diǎn)能隸屬多個社區(qū)。例如興趣廣泛的在線社交網(wǎng)絡(luò)用戶可以參與多個興趣社區(qū)，具有多個研究方向的科研人員可以隸屬于多個研究團(tuán)隊(duì)［3］。近年來，已有許多重疊社區(qū)發(fā)現(xiàn)方法被提出，其中包括基于派系過濾的方法［4］、基于模塊度的方法［5］、基于局部擴(kuò)張的方法［6］以及基于隨機(jī)塊模型的方法［7］等。值得指出的是，目前基于非負(fù)矩陣分解（Nonnegative Matrix Factorization，NMF）的重疊社區(qū)發(fā)現(xiàn)方法已受到廣泛關(guān)注，例如：Cao 等［8］提出的基于非負(fù)矩陣分解的社區(qū)發(fā)現(xiàn)算法（Community Detection with Nonnegative Matrix Factorization，CDNMF）方法首先通過計(jì)算節(jié)點(diǎn)在網(wǎng)絡(luò)中的中心度來構(gòu)建節(jié)點(diǎn)特征矩陣，然后應(yīng)用NMF獲得重疊社區(qū)結(jié)構(gòu)；Zhang等［9］提出了對稱二值非負(fù)矩陣分解方 法（Symmetric Binary Nonnegative Matrix Factorization，SBNMF），其分解得到的二值矩陣不僅可以顯式地指示節(jié)點(diǎn)的社區(qū)隸屬關(guān)系，而且還可以區(qū)分離群節(jié)點(diǎn)和重疊節(jié)點(diǎn)；胡麗瑩等［10］提出了一種帶參數(shù)的對稱非負(fù)矩陣分解算法來獲得社區(qū)重疊劃分結(jié)果、重疊節(jié)點(diǎn)、中心節(jié)點(diǎn)以及離群節(jié)點(diǎn)；Shi等［11］通過NMF 與貝葉斯概率模型結(jié)合來自動獲得一個節(jié)點(diǎn)分配給特定社區(qū)的最佳概率閾值從而得到重疊社區(qū)劃分；Jin等［12］則將圖正則化理論引入到NMF 中進(jìn)行重疊社區(qū)發(fā)現(xiàn)；此外，Ye 等［13］提出了一種離散化的-非負(fù)矩陣分解方法（Discrete Nonnegative Matrix Factorization，DNMF），通過結(jié)合NMF 和偽監(jiān)督約束項(xiàng)，可以獲得到二值社區(qū)成員隸屬關(guān)系矩陣。以上這些基于NMF 的重疊社區(qū)發(fā)現(xiàn)方法的研究表明，NMF 不僅能夠更高效挖掘復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)，而且挖掘結(jié)果比其他類型的方法具有更好的可解釋性，是一種理想的重疊社區(qū)發(fā)現(xiàn)模型。

在現(xiàn)有基于NMF 的重疊社區(qū)發(fā)現(xiàn)方法中，基于對稱二值NMF 的方法SBNMF 最具有代表性，原因在于它不僅具備了NMF 強(qiáng)大的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)聚類能力，而且首次提出了離散化節(jié)點(diǎn)社區(qū)隸屬關(guān)系表示的思想，即通過只包含0和1的二值社區(qū)成員隸屬關(guān)系矩陣能夠顯式地指明節(jié)點(diǎn)屬于哪個社區(qū)，無需跟其他基于NMF 的重疊社區(qū)發(fā)現(xiàn)方法一樣還需要手動設(shè)置閾值進(jìn)行節(jié)點(diǎn)社區(qū)歸屬強(qiáng)度的判斷，從而提高了社區(qū)發(fā)現(xiàn)的效率。然而，實(shí)際研究及應(yīng)用發(fā)現(xiàn)SBNMF 在面對社區(qū)內(nèi)的鏈接十分稠密的復(fù)雜網(wǎng)絡(luò)時(shí)具有很好的社區(qū)發(fā)現(xiàn)性能，但在面對社區(qū)內(nèi)的鏈接相對稀疏的網(wǎng)絡(luò)時(shí)性能將會顯著下降。該缺點(diǎn)顯然降低了SBNMF 的可適用性，畢竟大部分現(xiàn)實(shí)世界復(fù)雜網(wǎng)絡(luò)中的社區(qū)內(nèi)的鏈接并不會非常稠密，例如在線社交網(wǎng)絡(luò)的社區(qū)并不是大部分用戶都具有好友關(guān)系。

針對SBNMF 存在的問題，本文提出一種改進(jìn)的基于對稱二值非負(fù)矩陣分解（Improved SBNMF，ISBNMF）的重疊社區(qū)發(fā)現(xiàn)方法，主要工作包括：1）解決SBNMF 面對社區(qū)內(nèi)鏈接稀疏的網(wǎng)絡(luò)時(shí)重疊社區(qū)發(fā)現(xiàn)性能低下的問題；2）針對設(shè)計(jì)的ISBNMF重疊社區(qū)發(fā)現(xiàn)模型提出了兩種優(yōu)化求解方案；3）在人工合成網(wǎng)絡(luò)數(shù)據(jù)集和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了大量的對比實(shí)驗(yàn)，驗(yàn)證ISBNMF 在重疊社區(qū)發(fā)現(xiàn)的性能上要優(yōu)于SBNMF 和其他現(xiàn)有代表性方法。

1 相關(guān)工作

1.1 對稱非負(fù)矩陣分解

非負(fù)矩陣分解NMF 可在原空間中尋找一個低維的特征空間和原數(shù)據(jù)在該低維空間上的投影。形式上，給定一個表示原空間的非負(fù)矩陣X，大小為n × m，NMF 可以將其分解為兩個非負(fù)的低秩矩陣因子W 和H，大小分別為n × k 和m × k，其中k ?m，n。得到的因子矩陣W 和H 可以重構(gòu)出近似等于X 的矩陣，即X ≈WHT。NMF 的優(yōu)化求解模型通?？梢员磉_(dá)為：

其中F 為Frobenius 范數(shù)。若X 是一個對稱的非負(fù)矩陣，那么可以通過令W=H，得到X ≈HHT，這種分解方式被稱為對稱NMF（Symmetric NMF，SNMF）［14］。SNMF 與NMF 相比，具有更強(qiáng)的聚類能力，同時(shí)具有良好的可解釋性［15］。Wang等［16］首次將SNMF 應(yīng)用到了針對無向網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)中，提出了基于SNMF 的社區(qū)發(fā)現(xiàn)方法，其具體表述為：給定一個復(fù)雜網(wǎng)絡(luò)G=(V，E)，其中V 代表節(jié)點(diǎn)的集合，E 代表連接節(jié)點(diǎn)的邊集合。矩陣A 是一個表示網(wǎng)絡(luò)G 的鄰接矩陣，它是一個大小為n × n 的對稱矩陣，其中Aij=1 表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間有邊相連，Aij=0則表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間無邊相連?；赟NMF的社區(qū)發(fā)現(xiàn)模型表示為：

可以通過式（3）的乘性迭代更新規(guī)則對模型進(jìn)行優(yōu)化求解。

目標(biāo)函數(shù)（2）收斂后，可得到矩陣因子H。對于矩陣H 的每一個行向量Hi，對Hi進(jìn)行規(guī)范化，使Hi的所有元素的累加之和為1，即規(guī)范化后H 中的元素Hij表示節(jié)點(diǎn)i 隸屬于社區(qū)j的強(qiáng)度。

1.2 基于SBNMF的重疊社區(qū)發(fā)現(xiàn)方法

復(fù)雜網(wǎng)絡(luò)的社區(qū)具有重疊性，因此社區(qū)發(fā)現(xiàn)方法都應(yīng)該具備重疊社區(qū)的檢測能力?；赟NMF 的社區(qū)發(fā)現(xiàn)方法只提供了一種模糊的重疊社區(qū)檢測方法，即雖然可以通過Hij的值來得到節(jié)點(diǎn)i與社區(qū)j間的隸屬強(qiáng)度，但是決定節(jié)點(diǎn)i是否屬于社區(qū)j需要手動設(shè)置一個閾值進(jìn)行判斷，這往往難于獲得準(zhǔn)確的重疊社區(qū)發(fā)現(xiàn)結(jié)果。針對該問題，Zhang等［9］提出了基于對稱二值NMF的重疊社區(qū)發(fā)現(xiàn)方法SBNMF，該方法可以直接學(xué)習(xí)得到只有0和1表示的二值節(jié)點(diǎn)社區(qū)隸屬關(guān)系矩陣，從而可以直接提取節(jié)點(diǎn)的社區(qū)標(biāo)簽。具體地，假設(shè)給定一個大小為n × n的復(fù)雜網(wǎng)絡(luò)鄰接矩陣A，SBNMF會求解出一個n × r的二值矩陣U，使得A ≈UUT，Uij∈{0，1}。Uij=1 表示節(jié)點(diǎn)i 直接隸屬于社區(qū)j，Uij=0則表示節(jié)點(diǎn)i不屬于社區(qū)j。SBNMF 的算法過程是先使用SNMF求出H，再使用H作為如下模型U的初始值并進(jìn)行優(yōu)化求解。

SBNMF 提供了一種可自動學(xué)習(xí)最佳u 值的方法，從而提高了社區(qū)發(fā)現(xiàn)效率，最終的二值節(jié)點(diǎn)社區(qū)隸屬關(guān)系U 通過U=Θ(U -u)獲得。

2 基于改進(jìn)SBNMF的重疊社區(qū)發(fā)現(xiàn)方法

2.1 SBNMF存在的問題分析

假設(shè)有一個完全正確地標(biāo)記了節(jié)點(diǎn)真實(shí)社區(qū)的二值矩陣U，使用UUT來重構(gòu)出矩陣M，即M=UUT，其中矩陣元素Mij=Ui?Uj=∑kUikUjk，Ui表示U的第i個行向量，Uj表示U的第j個行向量。同時(shí)由于Uij取值只為0 和1 的特殊性，Mij有著一個重要的表示意義，即其可以表示為節(jié)點(diǎn)i 與節(jié)點(diǎn)j 的共同社區(qū)個數(shù)。假設(shè)將M 看作一個鄰接矩陣，Mij＞0 看作節(jié)點(diǎn)i與節(jié)點(diǎn)j相互連接，Mij=0看作節(jié)點(diǎn)i與節(jié)點(diǎn)j沒有連接。通過M表示的網(wǎng)絡(luò)，可以直觀地發(fā)現(xiàn)：

1）對于處于同一個社區(qū)內(nèi)的節(jié)點(diǎn)，它們兩兩間是相互連接的。

2）對于處于不同社區(qū)的節(jié)點(diǎn)，它們是沒有連接的。

然而現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)社區(qū)具有稀疏性，同一個社區(qū)內(nèi)的節(jié)點(diǎn)間都相互連接的可能性非常小。此外，不同社區(qū)之間的節(jié)點(diǎn)也有可能建立連接。由此可知使用UUT來重構(gòu)出的矩陣M 與真實(shí)網(wǎng)絡(luò)的鄰接矩陣A 將有著較大的誤差，這將會降低SBNMF 的重疊社區(qū)檢測效果，其原因還可以進(jìn)一步分析如下：假若一個網(wǎng)絡(luò)有k 個社區(qū)C1，C2，…，Ck，大小分別為P1，P2，…，Pk，將屬于相同社區(qū)的節(jié)點(diǎn)編號調(diào)整為連續(xù)的，那么其鄰接矩陣A可以表示為：

其中：Si可以看作是第i 個社區(qū)表示的子網(wǎng)絡(luò)鄰接矩陣，大小為Pi× Pi。在A 中，除去子矩陣S1到Sk，其余元素大多為0。在真實(shí)網(wǎng)絡(luò)中，相同社區(qū)節(jié)點(diǎn)之間的連接通常并不太稠密，即Si中元素值為1的比重較小，值為0的比重較大。這樣SBNMF為了讓UUT更為近似于A，會傾向使式（4）求解出的u 的值較高，這樣才能使得UUT重構(gòu)的鄰接矩陣?yán)锉硎就粋€社區(qū)的鄰接矩陣Si有較多的0。由于重疊節(jié)點(diǎn)屬于多個社區(qū)，所以其屬于每一個社區(qū)的隸屬強(qiáng)度也會降低，再由于求出的u 較高，那么SBNMF 將會傾向?qū)⒅丿B節(jié)點(diǎn)檢測為離群節(jié)點(diǎn)或求得的節(jié)點(diǎn)所屬社區(qū)數(shù)目比節(jié)點(diǎn)真實(shí)所屬社區(qū)數(shù)目少，從而降低了重疊社區(qū)檢測的效果。例如針對如圖1 所示的網(wǎng)絡(luò)示例，節(jié)點(diǎn)6、7顯然為重疊節(jié)點(diǎn)，但由于社區(qū)內(nèi)部稀疏，SBNMF將重疊節(jié)點(diǎn)6、7檢測為了離群節(jié)點(diǎn)，這顯然是錯誤。

圖1 SBNMF對社區(qū)內(nèi)部鏈接稀疏的網(wǎng)絡(luò)進(jìn)行重疊社區(qū)發(fā)現(xiàn)Fig.1 SBNMF performs overlapping community detection on networks with sparse links within communities

2.2 ISBNMF重疊社區(qū)發(fā)現(xiàn)方法

針對SBNMF 存在的問題，本文提出了一種改進(jìn)的SBNMF 方法ISBNMF，其主要執(zhí)行過程是：1）與SBNMF 第一步相同，先使用SNMF 算法求出H，該矩陣指示了每個節(jié)點(diǎn)隸屬于每個社區(qū)的強(qiáng)度；2）通過H提供的信息，再結(jié)合表示原網(wǎng)絡(luò)的鄰接矩陣A，構(gòu)建一個社區(qū)內(nèi)部鏈接稠密的新網(wǎng)絡(luò)；3）基于SBNMF 構(gòu)建社區(qū)發(fā)現(xiàn)模型，其中目標(biāo)分解矩陣為新網(wǎng)絡(luò)的鄰接矩陣A′。步驟2 和步驟3 是ISBNMF 的核心組成部分，下面分別介紹這2部分的具體操作過程。

1）構(gòu)建社區(qū)內(nèi)部鏈接稠密的網(wǎng)絡(luò)。

由于SBNMF 的問題根源在于大多數(shù)網(wǎng)絡(luò)的社區(qū)內(nèi)部節(jié)點(diǎn)鏈接稀疏，這會使得SBNMF 傾向?qū)⒅丿B節(jié)點(diǎn)識別為離群節(jié)點(diǎn)。基于該問題的發(fā)現(xiàn)，本文試圖在原網(wǎng)絡(luò)的基礎(chǔ)上構(gòu)造一個新的網(wǎng)絡(luò)，該網(wǎng)絡(luò)中屬于同一個社區(qū)的節(jié)點(diǎn)間鏈接盡可能稠密，并接近同一個社區(qū)內(nèi)的節(jié)點(diǎn)兩兩相連的條件。為了構(gòu)造這樣的新網(wǎng)絡(luò)，將選擇在不刪除原有網(wǎng)絡(luò)節(jié)點(diǎn)連接前提下，添加新的節(jié)點(diǎn)連接。為此需要解決如下兩個問題：1）每個節(jié)點(diǎn)需要連接的節(jié)點(diǎn)個數(shù)；2）每個節(jié)點(diǎn)該如何選擇要連接的節(jié)點(diǎn)。為了解決這些問題，本文采用的策略如下：

為了解決問題2，本文首先利用H 包含的每個節(jié)點(diǎn)的低維表示向量使用式（8）計(jì)算出兩兩節(jié)點(diǎn)間的相似度，節(jié)點(diǎn)間的相似度越高，則表明它們同屬一個社區(qū)的概率就越大。因此對于節(jié)點(diǎn)i，可以選擇前h 個相似度最高的節(jié)點(diǎn)進(jìn)行連接，其中h=Connect(i)。

2）構(gòu)建ISBNMF社區(qū)發(fā)現(xiàn)模型。

令A(yù)′表示新網(wǎng)絡(luò)的鄰接矩陣，ISBNMF 社區(qū)發(fā)現(xiàn)模型使用表示具有社區(qū)節(jié)點(diǎn)連接稠密特征的鄰接矩陣A′，而非使用表示原網(wǎng)絡(luò)的鄰接矩陣A進(jìn)行二值矩陣分解。具體的社區(qū)發(fā)現(xiàn)模型如式（9）所示：

由于式（9）是有約束非線性規(guī)劃問題，并且也是一個離散優(yōu)化問題，很難直接求解該問題［17］，但可以使用式（10）所示的等價(jià)無約束非線性規(guī)劃模型來代替。

2.3 模型求解

對于式（10）模型的求解，可以先使用SNMF 求解的H 來初始化U，然后選擇如下兩種方法之一進(jìn)行求解：

1）網(wǎng)格搜索法（Grid Search Method，GSM）：先確定u 的定義域?yàn)樵O(shè)置步長間隔h 將u 的定義域離散化成一系列網(wǎng)格點(diǎn)，然后在每個網(wǎng)格點(diǎn)上搜索使得目標(biāo)函數(shù)式（10）最小的u 值。為了平衡運(yùn)行效率與精確度，本文設(shè)置h=0.01。后面將使用網(wǎng)格搜索法求解模型的ISBNMF 方法簡稱為ISBNMF-GSM。

2）梯度下降法（Gradient Decent Method，GDM）：由于Θ是非光滑的階躍函數(shù)，可以選擇使用一個光滑可導(dǎo)的函數(shù)Φ 來近似替代Θ。本文選擇式（11）的函數(shù)來近似替代Θ，這樣模型式（10）可以表示為式（12）：

其中：λ 是一個較大的常數(shù)，其值越大，Φ 就越近似于Θ，本文設(shè)置λ=100。對于目標(biāo)函數(shù)L(u)的梯度方向gk的推導(dǎo)如下所示：

其中：dk=-gk；δ 和σ 為常數(shù)，取值滿足0 ＜δ ＜σ ＜1。后面將使用梯度下降法求解模型的ISBNMF 方法簡稱為ISBNMFGDM。

最后求解模型得到u 后，通過U=Θ(U -u)即可求得最終的二值節(jié)點(diǎn)社區(qū)隸屬關(guān)系矩陣U。

2.4 ISBNMF重疊社區(qū)發(fā)現(xiàn)算法

根據(jù)上述分析，設(shè)計(jì)如下ISBNMF重疊社區(qū)發(fā)現(xiàn)算法。

算法1 ISBNMF重疊社區(qū)發(fā)現(xiàn)。

圖2 給出了ISBNMF 對圖1 相同的復(fù)雜網(wǎng)絡(luò)示例進(jìn)行重疊社區(qū)發(fā)現(xiàn)的具體流程，可以清楚地看出ISBNMF 很準(zhǔn)確地獲得了重疊社區(qū)結(jié)構(gòu)。對于ISBNMF 重疊社區(qū)發(fā)現(xiàn)算法的時(shí)間復(fù)雜度計(jì)算可以分為三部分來進(jìn)行。第一部分是應(yīng)用SNMF，其時(shí)間復(fù)雜度為O(t1n2)，其中t1為迭代次數(shù)，n 為網(wǎng)絡(luò)的節(jié)點(diǎn)個數(shù)。第二部分是構(gòu)建新網(wǎng)絡(luò)，其時(shí)間復(fù)雜度為O(kn2)，其中k 為社區(qū)的個數(shù)。第三部分是ISBNMF 模型求解，使用網(wǎng)格搜索法求解模型的時(shí)間復(fù)雜度為O((max(U)/h)*(kn2))，其中h為離散化定義域的步長；使用梯度下降法來求解模型的時(shí)間復(fù)雜度為O(t2kn2)，t2為迭代次數(shù)。綜合計(jì)算，ISBNMF算法的時(shí)間復(fù)雜度為O(t1n2+kn2+max((max(U)/h)*(kn2)，t2kn2))，又因?yàn)閗 ?n 且h、t1、t2為與網(wǎng)絡(luò)規(guī)模無關(guān)的常數(shù)，所以時(shí)間復(fù)雜度近似為O(n2)，該時(shí)間復(fù)雜度與SBNMF相同。

圖2 ISBNMF進(jìn)行重疊社區(qū)發(fā)現(xiàn)的流程Fig.2 Process of ISBNMF performing overlapping community detection

3 實(shí)驗(yàn)結(jié)果及分析

本文選擇具有代表性的基于NMF 的重疊社區(qū)發(fā)現(xiàn)方法SBNMF［9］、CDNMF［8］和DNMF［13］作為基準(zhǔn)，然后在人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行性能比較。實(shí)驗(yàn)硬件平臺為Intel Core i5-4210M CPU，主頻2.60 GHz，內(nèi)存12 GB，操作系統(tǒng)為Windows 10。除DNMF 使用Matlab R2015b 實(shí)現(xiàn)，其余方法均使用Python3.5實(shí)現(xiàn)。

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

為了驗(yàn)證ISBNMF 方法的重疊社區(qū)發(fā)現(xiàn)性能，本文使用人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)作為數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

1）人工合成網(wǎng)絡(luò)：使用廣泛使用的LFR 基準(zhǔn)合成網(wǎng)絡(luò)工具包［18］來生成帶有真實(shí)社區(qū)劃分結(jié)果的合成網(wǎng)絡(luò)，LFR 包括節(jié)點(diǎn)數(shù)n、重疊節(jié)點(diǎn)數(shù)on、重疊節(jié)點(diǎn)隸屬關(guān)系數(shù)om 以及混合參數(shù)mu。實(shí)驗(yàn)通過改變其中一個參數(shù)的值，并固定其余參數(shù)來生成4 組合成網(wǎng)絡(luò)集，每組合成網(wǎng)絡(luò)集包含5 個合成網(wǎng)絡(luò)，共計(jì)20個LFR合成網(wǎng)絡(luò)。具體參數(shù)的設(shè)置情況如表1所示。

表1 LFR基準(zhǔn)合成網(wǎng)絡(luò)的參數(shù)Tab.1 Parameters of LFR benchmark synthetic networks

2）真實(shí)網(wǎng)絡(luò)：使用8 個具有代表性的真實(shí)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，分別為空手道俱樂部關(guān)系網(wǎng)絡(luò)Karate［18］、海豚網(wǎng)絡(luò)Dolphins［18］、美國大學(xué)生足球聯(lián)賽網(wǎng)絡(luò)Football［18］、美國政治書籍銷售網(wǎng)絡(luò)Polbooks［18］、政治博客網(wǎng)絡(luò)Polblogs［18］、社交媒體網(wǎng)絡(luò)Facebook［19］、美國電網(wǎng)網(wǎng)絡(luò)Powergrid［13］以及論文關(guān)系網(wǎng)絡(luò)Pubmed［13］。各網(wǎng)絡(luò)的具體統(tǒng)計(jì)特征如表2所示。

表2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集Tab.2 Real network datasets

3.2 評價(jià)指標(biāo)

對于已知真實(shí)社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)數(shù)據(jù)集，本文使用重疊標(biāo)準(zhǔn)化互信息（Overlapping Normalized Mutual Information，ONMI）［20］和F1-measure［21］作為重疊社區(qū)發(fā)現(xiàn)性能的評價(jià)指標(biāo)。對于未知真實(shí)社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)數(shù)據(jù)集，則使用擴(kuò)展模塊度（Extended Q-modularity，EQ）［22］作為評價(jià)指標(biāo)，它們的具體定義如下：

1）ONMI。ONMI 可以評估真實(shí)社區(qū)成員C*與方法檢測到的社區(qū)成員C之間的相似性，其定義如下：

其中：H(Ci)表示第i 個社區(qū)Ci的熵表示Ci相對于C*的熵，而H(Ci|C*)的定義如下：

2）F1-measure。F1-measure 可以用于評價(jià)方法對重疊節(jié)點(diǎn)（所屬社區(qū)個數(shù)大于1的節(jié)點(diǎn)）的檢測效果，其定義如下：

其中：N表示方法檢測到的重疊節(jié)點(diǎn)集合，N*表示真實(shí)的重疊節(jié)點(diǎn)集合，P(N，N*)和R(N，N*)分別定義如下：

3）擴(kuò)展模塊度EQ。擴(kuò)展模塊度EQ 是一種將社區(qū)發(fā)現(xiàn)性能評價(jià)廣泛使用的模塊度Q的適用場景推廣到重疊社區(qū)發(fā)現(xiàn)問題的一種評價(jià)指標(biāo)，其定義如下所示：

其中：m表示網(wǎng)絡(luò)邊的總數(shù)，Ou表示節(jié)點(diǎn)u所屬的社區(qū)個數(shù)，ku表示節(jié)點(diǎn)u的度。

對于上述3 個評價(jià)指標(biāo)，均是取值越高，則表明相應(yīng)方法的重疊社區(qū)檢測性能越好。

3.3 實(shí)驗(yàn)對比分析

3.3.1 人工合成網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)與分析

對于每一組合成網(wǎng)絡(luò)，由于已知其真實(shí)的社區(qū)結(jié)構(gòu)，實(shí)驗(yàn)使用ONMI和F1-score 作為評價(jià)指標(biāo)，對每個方法重復(fù)進(jìn)行10次實(shí)驗(yàn)并將實(shí)驗(yàn)結(jié)果的平均值作為最終結(jié)果。

通過改變表示節(jié)點(diǎn)個數(shù)的參數(shù)n，固定其余參數(shù)，令n 從1 000 增加到5 000，每次增加的幅度為1 000，生成第一組的5個合成網(wǎng)絡(luò)，具體可參考表1。圖3（a）和圖4（a）是第一組合成網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果。從圖3（a）中可以看出隨著n 的增加，各算法在性能指標(biāo)ONMI 上都出現(xiàn)了小幅度的下降，表明了網(wǎng)絡(luò)的節(jié)點(diǎn)個數(shù)變化對于重疊社區(qū)發(fā)現(xiàn)的影響較小。本文提出的ISBNMF-GSM 和ISBNMF-GDM 得到的ONMI 最佳，表明算法檢測出的社區(qū)結(jié)構(gòu)接近真實(shí)社區(qū)結(jié)構(gòu)。從圖4（a）中可以看出各算法在檢測重疊節(jié)點(diǎn)上的表現(xiàn)差異較大，本文提出的ISBNMF-GSM 的F1-score 能達(dá)到0.873，說明能非常準(zhǔn)確地檢測出重疊節(jié)點(diǎn)；而DNMF 在ONMI 上表現(xiàn)的性能尚可，可是極低的F1-score說明其只能檢測出極少的重疊節(jié)點(diǎn)，進(jìn)一步表明了其檢測出的社區(qū)結(jié)構(gòu)在非重疊部分有著一定的準(zhǔn)確性，而對于重疊部分的檢測能力十分薄弱。SBNMF 由于社區(qū)內(nèi)部鏈接稀疏的原因，導(dǎo)致其部分重疊節(jié)點(diǎn)被檢測為了離群節(jié)點(diǎn)，所以相應(yīng)的F1-score也非常低。

通過改變表示重疊節(jié)點(diǎn)個數(shù)的參數(shù)on，固定其余參數(shù)，令on 從100 增加到500，每次增加的幅度為100，生成第二組的5個合成網(wǎng)絡(luò)。通過改變混合參數(shù)mu，固定其余參數(shù)，令mu從0.1 增加到0.5，每次增加的幅度為0.1，生成第三組的5 個合成網(wǎng)絡(luò)。圖3（b）和圖4（b）是第二組合成網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果，圖3（c）和圖4（c）是第三組合成網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果。從上述的圖中可以看出，隨著參數(shù)on、mu的增加，社區(qū)結(jié)構(gòu)開始逐漸變得模糊，各個算法得到的ONMI 和F1-score 都呈現(xiàn)出下降趨勢，而本文提出的ISBNMF-GSM 和ISBNMF-GDM 相對于其余的比較方法依然得到了最佳的ONMI 和F1-score，說明該算法能很好地應(yīng)對重疊節(jié)點(diǎn)個數(shù)多和社區(qū)結(jié)構(gòu)混亂的網(wǎng)絡(luò)，具有更強(qiáng)的魯棒性。

通過改變節(jié)點(diǎn)隸屬社區(qū)個數(shù)參數(shù)om，固定其余參數(shù)，令om從2增加到6，每次增加的幅度為1，生成第四組的5個合成網(wǎng)絡(luò)。圖3（d）和圖4（d）是第四組合成網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果，從圖中可以看出ISBNMF-GSM 隨著om的增大，ONMI和F1-score有明顯的下降趨勢，說明ISBNMF-GSM 對于om 較為敏感。但綜合的平均性能依然高于其余的比較方法，表明該方法重疊社區(qū)發(fā)現(xiàn)的效果良好。

圖3 人工合成網(wǎng)絡(luò)的ONMI性能比較Fig.3 ONMI performance comparison on synthesis networks

圖4 人工合成網(wǎng)絡(luò)的F1-score 性能比較Fig.4 F1-score performance comparison on synthesis networks

對于ISBNMF 方法的兩種實(shí)現(xiàn)形式ISBNMF-GDM 和ISBNMF-GSM，ISBNMF-GDM 是基于梯度下降的算法，由于u的隨機(jī)初始化通常會使其求得目標(biāo)函數(shù)的局部最優(yōu)解。而ISBNMF-GSM由于近似地遍歷了u的所有取值，所以會求得近似的全局最優(yōu)解。因此對于經(jīng)過多次實(shí)驗(yàn)的平均結(jié)果，ISBNMF-GDM總會略微低于ISBNMF-GSM?？傮w上，兩者在上述的實(shí)驗(yàn)中在ONMI和F1-score指標(biāo)上都高于其余對比方法。

為了說明本文提出的ISBNMF 構(gòu)造新網(wǎng)絡(luò)階段的改進(jìn)效果，選取第一組的5個LFR 基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)，對原網(wǎng)絡(luò)與新網(wǎng)絡(luò)進(jìn)行社區(qū)稀疏度分析以及誤差分析。首先進(jìn)行社區(qū)稀疏度分析，對于一個社區(qū)，其社區(qū)稀疏度定義為社區(qū)表示的鄰接矩陣中包含值為0 的元素的百分比。對于一個網(wǎng)絡(luò)，其社區(qū)稀疏度定義為該網(wǎng)絡(luò)所包含的所有社區(qū)的社區(qū)稀疏度取平均。原網(wǎng)絡(luò)與新網(wǎng)絡(luò)的社區(qū)稀疏度如表3 所示。從表中可以看出，新網(wǎng)絡(luò)比原網(wǎng)絡(luò)的社區(qū)稀疏程度大幅度降低，即新網(wǎng)絡(luò)社區(qū)內(nèi)部鏈接十分稠密，解決了原網(wǎng)絡(luò)社區(qū)內(nèi)部鏈接稀疏導(dǎo)致SBNMF重疊社區(qū)發(fā)現(xiàn)性能降低的問題。

其次，為了更精確地闡述使用新網(wǎng)絡(luò)帶來的改進(jìn)效果，進(jìn)一步地對第一組的5 個LFR 基準(zhǔn)網(wǎng)絡(luò)進(jìn)行誤差分析，對于一個網(wǎng)絡(luò)與其真實(shí)社區(qū)關(guān)系隸屬矩陣重構(gòu)網(wǎng)絡(luò)的誤差定義如式（21）所示：

其中：U為真實(shí)社區(qū)關(guān)系隸屬矩陣，A為代表網(wǎng)絡(luò)的鄰接矩陣。其誤差結(jié)果如圖5所示。從圖5中可以看出，新網(wǎng)絡(luò)相較于原網(wǎng)絡(luò)大幅度降低了與真實(shí)社區(qū)關(guān)系隸屬矩陣重構(gòu)網(wǎng)絡(luò)的誤差，因此能提升重疊社區(qū)發(fā)現(xiàn)的性能。

圖5 網(wǎng)絡(luò)處理前后的誤差比較Fig.5 Error comparison between original network and processed network

綜上所述，ISBNMF 方法很好地改善了SBNMF 面對社區(qū)內(nèi)部鏈接稀疏的網(wǎng)絡(luò)時(shí)重疊社區(qū)發(fā)現(xiàn)能力弱的缺點(diǎn)，但同時(shí)也付出了一定的時(shí)間性能為代價(jià)，具體的時(shí)間性能測試如表4 所示，ISBNMF 主要因?yàn)樵黾恿藰?gòu)造新網(wǎng)絡(luò)的步驟，導(dǎo)致運(yùn)行時(shí)間要比SBNMF要高。

表3 不同網(wǎng)絡(luò)的社區(qū)稀疏度對比 單位：%Tab.3 Community sparsity comparison of different networks unit：%

表4 不同網(wǎng)絡(luò)上的時(shí)間性能對比 單位：sTab.4 Time performance comparison of different networks unit：s

3.3.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)與分析

由于所有采用的真實(shí)網(wǎng)絡(luò)都沒有給出真實(shí)的重疊社區(qū)劃分結(jié)果，因此實(shí)驗(yàn)將擴(kuò)展模塊化EQ用作評價(jià)指標(biāo)。對于每一個真實(shí)網(wǎng)絡(luò)，實(shí)驗(yàn)對每個方法重復(fù)進(jìn)行10 次實(shí)驗(yàn)并將實(shí)驗(yàn)結(jié)果EQ的平均值作為最終結(jié)果。

為了說明β 對本文算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的影響，選取具有代表性的四個數(shù)據(jù)集進(jìn)行參數(shù)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6 所示。從圖6 中可以看出Football 數(shù)據(jù)集當(dāng)β=0.1 時(shí)，ISBNMFGSM算法得到的EQ取得最高值，而其余3個數(shù)據(jù)集則是當(dāng)β=0時(shí)，EQ 取得最高值。當(dāng)β取值過大時(shí)，可能會導(dǎo)致社區(qū)相互間的連接增多，降低準(zhǔn)確性，導(dǎo)致性能下降。因此，對于真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，β 的取值為0 至0.1 時(shí)，能取得良好的重疊社區(qū)發(fā)現(xiàn)效果。

圖6 ISBNMF-GSM在不同β下的EQ平均值Fig.6 Average EQ of ISBNMF-GSM under different β

最終所有數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果如表5 所示，EQ 的最高值已加粗標(biāo)出。

表5 基于擴(kuò)展模塊度EQ的性能比較Tab.5 Performance comparison by using extended modularity EQ

從表5 可以看出，本文提出的ISBNMF-GSM 方法在Karate、Dolphins、Football、Polblogs、Powergrid、Pubmed 這6 個數(shù)據(jù)集上都取得了最高的EQ 值，僅在Polbooks、Facebook 數(shù)據(jù)集中稍微低于DNMF。特別地，相較于SBNMF 方法，ISBNMF-GSM 分別在8 個數(shù)據(jù)集中約提升了4.2%、5.3%、8%、5.4%、8.1%、11.3%、7.7%、6.8%，表明ISBNMF 明顯地改進(jìn)了SBNMF 方法，并且能夠更好地應(yīng)用于真實(shí)的網(wǎng)絡(luò)當(dāng)中。以上結(jié)果表明本文提出的ISBNMF-GSM 方法在真實(shí)的網(wǎng)絡(luò)中也能夠檢測出清晰準(zhǔn)確的社區(qū)結(jié)構(gòu)，具有良好的重疊社區(qū)發(fā)現(xiàn)能力。

4 結(jié)語

為了解決重疊社區(qū)發(fā)現(xiàn)方法SBNMF 在面對社區(qū)內(nèi)部鏈接稀疏的網(wǎng)絡(luò)時(shí)性能變差的問題，本文提出了一種改進(jìn)的基于對稱二值非負(fù)矩陣分解的重疊社區(qū)發(fā)現(xiàn)方法ISBNMF。在人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上進(jìn)行了性能對比實(shí)驗(yàn)。結(jié)果表明ISBNMF 不僅解決了SBNMF 存在的問題，并且相比其他代表性重疊社區(qū)發(fā)現(xiàn)方法（如DNMF 和CDNMF）也有著更好的性能。由于ISBNMF 的時(shí)間復(fù)雜度近似為O(n2)，這限制了其應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)的能力。在后續(xù)的工作中，將重點(diǎn)研究如何進(jìn)一步提升ISBNMF 的運(yùn)行效率，設(shè)計(jì)更有效的社區(qū)發(fā)現(xiàn)模型迭代優(yōu)化求解算法以及基于內(nèi)存計(jì)算框架Spark 對ISBNMF進(jìn)行并行化實(shí)現(xiàn)。