基于改進對稱二值非負矩陣分解的重疊社區發現方法

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

（1.華南師范大學計算機學院，廣州 510631；2.仲愷農業工程學院信息科學與技術學院，廣州 510225）

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

0 引言

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

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

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

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

1 相關工作

1.1 對稱非負矩陣分解

非負矩陣分解NMF 可在原空間中尋找一個低維的特征空間和原數據在該低維空間上的投影。形式上，給定一個表示原空間的非負矩陣X，大小為n × m，NMF 可以將其分解為兩個非負的低秩矩陣因子W 和H，大小分別為n × k 和m × k，其中k ?m，n。得到的因子矩陣W 和H 可以重構出近似等于X 的矩陣，即X ≈WHT。NMF 的優化求解模型通常可以表達為：

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

可以通過式（3）的乘性迭代更新規則對模型進行優化求解。

目標函數（2）收斂后，可得到矩陣因子H。對于矩陣H 的每一個行向量Hi，對Hi進行規范化，使Hi的所有元素的累加之和為1，即規范化后H 中的元素Hij表示節點i 隸屬于社區j的強度。

1.2 基于SBNMF的重疊社區發現方法

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

SBNMF 提供了一種可自動學習最佳u 值的方法，從而提高了社區發現效率，最終的二值節點社區隸屬關系U 通過U=Θ(U -u)獲得。

2 基于改進SBNMF的重疊社區發現方法

2.1 SBNMF存在的問題分析

假設有一個完全正確地標記了節點真實社區的二值矩陣U，使用UUT來重構出矩陣M，即M=UUT，其中矩陣元素Mij=Ui?Uj=∑kUikUjk，Ui表示U的第i個行向量，Uj表示U的第j個行向量。同時由于Uij取值只為0 和1 的特殊性，Mij有著一個重要的表示意義，即其可以表示為節點i 與節點j 的共同社區個數。假設將M 看作一個鄰接矩陣，Mij＞0 看作節點i與節點j相互連接，Mij=0看作節點i與節點j沒有連接。通過M表示的網絡，可以直觀地發現：

1）對于處于同一個社區內的節點，它們兩兩間是相互連接的。

2）對于處于不同社區的節點，它們是沒有連接的。

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

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

圖1 SBNMF對社區內部鏈接稀疏的網絡進行重疊社區發現Fig.1 SBNMF performs overlapping community detection on networks with sparse links within communities

2.2 ISBNMF重疊社區發現方法

針對SBNMF 存在的問題，本文提出了一種改進的SBNMF 方法ISBNMF，其主要執行過程是：1）與SBNMF 第一步相同，先使用SNMF 算法求出H，該矩陣指示了每個節點隸屬于每個社區的強度；2）通過H提供的信息，再結合表示原網絡的鄰接矩陣A，構建一個社區內部鏈接稠密的新網絡；3）基于SBNMF 構建社區發現模型，其中目標分解矩陣為新網絡的鄰接矩陣A′。步驟2 和步驟3 是ISBNMF 的核心組成部分，下面分別介紹這2部分的具體操作過程。

1）構建社區內部鏈接稠密的網絡。

由于SBNMF 的問題根源在于大多數網絡的社區內部節點鏈接稀疏，這會使得SBNMF 傾向將重疊節點識別為離群節點。基于該問題的發現，本文試圖在原網絡的基礎上構造一個新的網絡，該網絡中屬于同一個社區的節點間鏈接盡可能稠密，并接近同一個社區內的節點兩兩相連的條件。為了構造這樣的新網絡，將選擇在不刪除原有網絡節點連接前提下，添加新的節點連接。為此需要解決如下兩個問題：1）每個節點需要連接的節點個數；2）每個節點該如何選擇要連接的節點。為了解決這些問題，本文采用的策略如下：

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

2）構建ISBNMF社區發現模型。

令A′表示新網絡的鄰接矩陣，ISBNMF 社區發現模型使用表示具有社區節點連接稠密特征的鄰接矩陣A′，而非使用表示原網絡的鄰接矩陣A進行二值矩陣分解。具體的社區發現模型如式（9）所示：

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

2.3 模型求解

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

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

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

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

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

最后求解模型得到u 后，通過U=Θ(U -u)即可求得最終的二值節點社區隸屬關系矩陣U。

2.4 ISBNMF重疊社區發現算法

根據上述分析，設計如下ISBNMF重疊社區發現算法。

算法1 ISBNMF重疊社區發現。

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

圖2 ISBNMF進行重疊社區發現的流程Fig.2 Process of ISBNMF performing overlapping community detection

3 實驗結果及分析

本文選擇具有代表性的基于NMF 的重疊社區發現方法SBNMF［9］、CDNMF［8］和DNMF［13］作為基準，然后在人工合成網絡和真實網絡數據集上進行性能比較。實驗硬件平臺為Intel Core i5-4210M CPU，主頻2.60 GHz，內存12 GB，操作系統為Windows 10。除DNMF 使用Matlab R2015b 實現，其余方法均使用Python3.5實現。

3.1 數據集

為了驗證ISBNMF 方法的重疊社區發現性能，本文使用人工合成網絡和真實網絡作為數據集進行實驗。

1）人工合成網絡：使用廣泛使用的LFR 基準合成網絡工具包［18］來生成帶有真實社區劃分結果的合成網絡，LFR 包括節點數n、重疊節點數on、重疊節點隸屬關系數om 以及混合參數mu。實驗通過改變其中一個參數的值，并固定其余參數來生成4 組合成網絡集，每組合成網絡集包含5 個合成網絡，共計20個LFR合成網絡。具體參數的設置情況如表1所示。

表1 LFR基準合成網絡的參數Tab.1 Parameters of LFR benchmark synthetic networks

2）真實網絡：使用8 個具有代表性的真實網絡進行實驗，分別為空手道俱樂部關系網絡Karate［18］、海豚網絡Dolphins［18］、美國大學生足球聯賽網絡Football［18］、美國政治書籍銷售網絡Polbooks［18］、政治博客網絡Polblogs［18］、社交媒體網絡Facebook［19］、美國電網網絡Powergrid［13］以及論文關系網絡Pubmed［13］。各網絡的具體統計特征如表2所示。

表2 真實網絡數據集Tab.2 Real network datasets

3.2 評價指標

對于已知真實社區結構的網絡數據集，本文使用重疊標準化互信息（Overlapping Normalized Mutual Information，ONMI）［20］和F1-measure［21］作為重疊社區發現性能的評價指標。對于未知真實社區結構的網絡數據集，則使用擴展模塊度（Extended Q-modularity，EQ）［22］作為評價指標，它們的具體定義如下：

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

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

2）F1-measure。F1-measure 可以用于評價方法對重疊節點（所屬社區個數大于1的節點）的檢測效果，其定義如下：

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

3）擴展模塊度EQ。擴展模塊度EQ 是一種將社區發現性能評價廣泛使用的模塊度Q的適用場景推廣到重疊社區發現問題的一種評價指標，其定義如下所示：

其中：m表示網絡邊的總數，Ou表示節點u所屬的社區個數，ku表示節點u的度。

對于上述3 個評價指標，均是取值越高，則表明相應方法的重疊社區檢測性能越好。

3.3 實驗對比分析

3.3.1 人工合成網絡數據集的實驗與分析

對于每一組合成網絡，由于已知其真實的社區結構，實驗使用ONMI和F1-score 作為評價指標，對每個方法重復進行10次實驗并將實驗結果的平均值作為最終結果。

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

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

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

圖3 人工合成網絡的ONMI性能比較Fig.3 ONMI performance comparison on synthesis networks

圖4 人工合成網絡的F1-score 性能比較Fig.4 F1-score performance comparison on synthesis networks

對于ISBNMF 方法的兩種實現形式ISBNMF-GDM 和ISBNMF-GSM，ISBNMF-GDM 是基于梯度下降的算法，由于u的隨機初始化通常會使其求得目標函數的局部最優解。而ISBNMF-GSM由于近似地遍歷了u的所有取值，所以會求得近似的全局最優解。因此對于經過多次實驗的平均結果，ISBNMF-GDM總會略微低于ISBNMF-GSM。總體上，兩者在上述的實驗中在ONMI和F1-score指標上都高于其余對比方法。

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

其次，為了更精確地闡述使用新網絡帶來的改進效果，進一步地對第一組的5 個LFR 基準網絡進行誤差分析，對于一個網絡與其真實社區關系隸屬矩陣重構網絡的誤差定義如式（21）所示：

其中：U為真實社區關系隸屬矩陣，A為代表網絡的鄰接矩陣。其誤差結果如圖5所示。從圖5中可以看出，新網絡相較于原網絡大幅度降低了與真實社區關系隸屬矩陣重構網絡的誤差，因此能提升重疊社區發現的性能。

圖5 網絡處理前后的誤差比較Fig.5 Error comparison between original network and processed network

綜上所述，ISBNMF 方法很好地改善了SBNMF 面對社區內部鏈接稀疏的網絡時重疊社區發現能力弱的缺點，但同時也付出了一定的時間性能為代價，具體的時間性能測試如表4 所示，ISBNMF 主要因為增加了構造新網絡的步驟，導致運行時間要比SBNMF要高。

表3 不同網絡的社區稀疏度對比 單位：%Tab.3 Community sparsity comparison of different networks unit：%

表4 不同網絡上的時間性能對比 單位：sTab.4 Time performance comparison of different networks unit：s

3.3.2 真實網絡數據集的實驗與分析

由于所有采用的真實網絡都沒有給出真實的重疊社區劃分結果，因此實驗將擴展模塊化EQ用作評價指標。對于每一個真實網絡，實驗對每個方法重復進行10 次實驗并將實驗結果EQ的平均值作為最終結果。

為了說明β 對本文算法在真實網絡數據集的影響，選取具有代表性的四個數據集進行參數實驗，實驗結果如圖6 所示。從圖6 中可以看出Football 數據集當β=0.1 時，ISBNMFGSM算法得到的EQ取得最高值，而其余3個數據集則是當β=0時，EQ 取得最高值。當β取值過大時，可能會導致社區相互間的連接增多，降低準確性，導致性能下降。因此，對于真實網絡數據集，β 的取值為0 至0.1 時，能取得良好的重疊社區發現效果。

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

最終所有數據集的實驗結果如表5 所示，EQ 的最高值已加粗標出。

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

從表5 可以看出，本文提出的ISBNMF-GSM 方法在Karate、Dolphins、Football、Polblogs、Powergrid、Pubmed 這6 個數據集上都取得了最高的EQ 值，僅在Polbooks、Facebook 數據集中稍微低于DNMF。特別地，相較于SBNMF 方法，ISBNMF-GSM 分別在8 個數據集中約提升了4.2%、5.3%、8%、5.4%、8.1%、11.3%、7.7%、6.8%，表明ISBNMF 明顯地改進了SBNMF 方法，并且能夠更好地應用于真實的網絡當中。以上結果表明本文提出的ISBNMF-GSM 方法在真實的網絡中也能夠檢測出清晰準確的社區結構，具有良好的重疊社區發現能力。

4 結語

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