應用非負矩陣分解模型的社區發現方法綜述*

李亞芳，賈彩燕＋，于　劍1.北京交通大學計算機與信息技術學院，北京1000442.交通數據分析與挖掘北京市重點實驗室，北京100044

?

應用非負矩陣分解模型的社區發現方法綜述*

李亞芳1，2，賈彩燕1，2＋，于劍1，2
1.北京交通大學計算機與信息技術學院，北京100044
2.交通數據分析與挖掘北京市重點實驗室，北京100044

* The National Natural Science Foundation of China under Grant Nos. 61473030，61370129（國家自然科學基金）; the Fundamental Research Funds for the Central Universities of China under Grant Nos. K15JB00070，2014JBM031（中央高校基本科研業務費專項資金）; the Opening Project of State Key Laboratory of Digital Publishing Technology（數字出版國家重點實驗室專項課題）.

Received 2015-05，Accepted 2015-08.

CNKI網絡優先出版：2015-08-12，http://www.cnki.net/kcms/detail/11.5602.TP.20150812.1638.008.html

李亞芳，賈彩燕，于劍.應用非負矩陣分解模型的社區發現方法綜述[J].計算機科學與探索，2016，10（1）：1-13.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10（01）-0001-13

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel:＋86-10-89056056

摘要：非負矩陣分解（nonnegative matrix factorization，NMF）在提取高維數據中隱含模式和結構方面具有良好性能，已成為數據挖掘領域的熱點研究之一。NMF作為無監督學習的有效工具，在模式識別、文本處理、多媒體數據分析以及生物信息學等研究領域得到了廣泛應用。目前，已有工作將NMF模型應用于網絡數據挖掘，發現網絡中隱含的社區結構。對基于NMF的社區發現方法進行了總結，包括無監督的社區發現方法和半監督的社區發現方法，通過在實際網絡和人工網絡進行實驗，比較分析了不同算法的性能，進一步研究了當前基于NMF發現社區結構所面臨的挑戰，并對下一步研究方向進行了展望。

關鍵詞：數據挖掘；非負矩陣分解；社區發現

1　引言

復雜網絡是描述自然界和社會系統的有力工具，現實世界中諸多復雜系統（如社會系統、科技系統、生物系統等）都可以用網絡的形式表示。復雜網絡是重要的多學科交叉研究領域，吸引了越來越多研究者的關注。研究發現，很多實際網絡中的節點具有聚集化特性——“模塊性”[1-2]，即網絡存在明顯的“社區結構”，主要表現為社區內部節點之間連接稠密，社區之間的節點連接稀疏。在實際網絡中，社區結構通常具有特殊意義，發現社區結構對于理解網絡的拓撲結構和功能特性具有重要的研究意義[3]。比如，在科研合作網中，一個社區通常表示某個科研領域，社區內的成員可能具有相似的研究方向，從而有利于提供精準的論文推薦以及選擇合適的論文評審專家；蛋白質交互網中，一個社區代表一個組織的功能模塊，因此有利于預測未知蛋白的功能。

目前，網絡中社區發現的研究已經取得很多研究成果，可以大體將社區發現方法分為圖切割方法[4-6]、目標函數優化方法[7-10]、聚類方法[11-13]和啟發式方法[14-15]等。本質上，社區發現問題屬于無監督學習范疇，因此研究者逐漸將目光投向無監督學習領域中取得成功應用的非負矩陣分解（nonnegative matrix factorization，NMF）模型處理網絡中社區結構探測的問題。

NMF是一種新的矩陣分解思想，最早由Paatero 和Tapper[16]提出，稱為正矩陣分解。1999年，Lee和Seung將NMF應用于圖像處理并取得突出成果[17]。NMF相比于傳統分解算法，具有實現簡便，分解形式和分解結果有可解釋性等優點，迅速得到各個領域研究者的高度重視。目前，NMF在理論研究和算法實現方向取得了突破性進展，研究發現，NMF與無監督學習的K-means方法和PLSI（probabilistic latent semantic indexing）等方法具有密切關系，且得到的結果有更好的解釋性[18-20]。由于NMF在提取高維數據中隱含模式和結構方面具有良好能力，成為維數約簡、無監督學習和預測等問題的有效工具，在模式識別[21]、文本處理[22-23]、多媒體數據分析[24]以及生物信息學[25]等研究領域得到了廣泛應用。目前，也涌現出許多工作將NMF模型應用到網絡社區發現中[26-37]，以發現網絡中隱含的模塊結構，并得到成功的應用。例如，He等人提出的NMFIB（nonnegative matrix factorization with iterative bipartition）模型[27]能夠在蛋白質交互網絡中得到更多統計顯著的GO（gene ontology）項；Rsorakis等人提出的BNMF（Bayesian nonnegative matrix factorization）模型[30]，通過與傳統層次聚類方法和譜聚類方法的對比，能夠得到更加準確的社區結構。

本文對基于NMF的社區發現方法進行了總結，分析了當前研究面臨的挑戰，并對下一步研究方向進行了展望。本文組織結構為：第2章介紹非負矩陣分解基本模型以及應用于社區發現的解釋；第3章介紹構建NMF模型中數據矩陣的方法；第4章對基于NMF的無監督社區發現方法進行總結；第5章介紹基于NMF的半監督社區發現方法；第6章進行實驗比較和分析；最后指出基于NMF發現網絡中社區結構遇到的挑戰，并對未來的研究工作進行展望。

2　NMF基本概念和定義

非負矩陣分解的思想是尋找一個新的特征空間，將原數據在該空間進行投影，利用投影結果和空間信息重構原數據。給定一個非負的特征矩陣Xm×n，將其分解為兩個低秩的非負矩陣W＝[Wic]∈和H＝[Hjc]∈（k?n，m）的乘積，盡可能地逼近原來的數據矩陣X，即X≈WHT。形式化地，NMF模型可表示為如下優化問題：

min D（X，WHT）

s.t. W≥0，H≥0

其中，D（x，y）是衡量x與y差異性的損失函數，平方誤差函數和廣義KL散度函數是兩種常用的損失函數。平方誤差函數用兩個矩陣差的Frobenius范數的平方表示，即DLSE（X，WHT）＝||X?WHT|，稱該方法為NMFLSE。兩個矩陣的廣義KL散度（又稱I-divergence）定義為：

稱該方法為NMFKL。損失函數的選擇，通常依據不同的應用而定。為了優化該目標函數，常用的優化方法有多步迭乘法、梯度下降法、投影梯度法和交替最小二乘法等。

給定網絡G＝（V，E），V＝{v1，v2，…，vn}表示節點集合，E＝{e1，e2，…，em}是邊集合。通常用鄰接矩陣A＝[Aij]n×n表示節點間的鏈接關系，矩陣對應元素的值表示邊的強度，如果vi和vj之間不存在邊，則Aij＝0。鄰接矩陣是最常用的一種相似度表示，當然，也可以通過相似度計算得到新的相似度矩陣表示節點間的關系。本文用數據矩陣X表示通過相似度計算得到的網絡中節點間的關系。

將標準的NMF模型應用于社區發現通常有兩種理論解釋。一種是基于NMF的基本思想，從節點的表示進行解釋。數據矩陣X可以看作節點的特征表示矩陣，以鄰接矩陣為例，每個節點通過與其他節點的鏈接情況來表示，即每一列是節點在n維空間的表示。W中的k個列向量看作新的特征空間下的一組基，H的每一行是在這組基下的新表示。因此，每個節點的表示向量x可以用W的列向量的線性組合進行逼近：x≈WhT，其中，h表示在各基向量的組合權重，代表節點到各個社區的隸屬度。另一種是從網絡中邊的生成角度進行解釋，用Wic和Hic分別表示從節點vi生成社區c中“出邊”和“入邊”的概率。因此，在k個社區中，生成連接節點vi和vj的邊的概率為WikHjk，通過參數學習，用生成的邊擬合實際網絡中觀測到的邊，從而得到節點屬于各社區的隸屬度，學習到的W（H）的行表示每個節點屬于各社區的程度。

通過以上兩種方法得到的隸屬度矩陣通常是節點的軟化分矩陣，對應元素是取值為0到1的實數，表示每個節點屬于各社區的程度。如果將節點指派到較大的隸屬度對應的社區，則得到網絡的重疊社區劃分結果；如果將節點唯一指派到最大隸屬度對應的社區，就得到非重疊劃分的社區結構。

3　構建基于NMF社區發現方法的數據矩陣

NMF模型中的待分解數據矩陣X（又稱特征矩陣），通常用鄰接矩陣A表示，表示節點與網絡中其他節點的鏈接關系和強度。然而，這種表示形式只能簡單地呈現有直接連邊的節點對之間的關系，無法用其他非直接連邊的節點進行表示，得到的數據矩陣包含的信息有限。因此，根據網絡的拓撲結構，通過相似度計算方法，得到新的數據矩陣成為基于NMF的社區發現方法中的重要內容。

根據數據矩陣的構造方法進行劃分，大體可以分為以下幾類：

（1）基于鄰接矩陣的方法。如最簡單的鄰接矩陣A，以及通過矩陣A構建任意節點之間相似度的SH方法和SA方法[38]、Regular方法[39]等。

（2）基于物理過程的方法。該類方法將網絡中任一節點看作源節點，通過一定時間下某個物理傳播過程，得到該節點對網絡中其他節點的影響程度積累，代表該節點與網絡中節點的相似程度。代表方法有基于核擴散的SK方法[40]、信號傳播方法（Signal）[41]、熱量擴散方法[42]（Heat）、基于隨機游走的LRW（local random walk）[43]和NRW（neighborhood random walk）方法[44]等。

（3）基于節點共有鄰居的方法。如果兩個節點之間共有鄰居越多，其相似度越高，如Jaccard相似度方法[45]、SC方法[46]等。

（4）基于最短路徑的方法。計算網絡中節點的最短路徑，如果兩個節點距離越近，則相似度越高，代表方法有SP方法[47]等。

目前，根據網絡中節點的鏈接關系，計算相似度矩陣構建數據矩陣的方法很多，更多相似度計算方法來構造數據矩陣X，可參見文獻[48]。Wang等人曾初步比較了幾種相似度方法[40]。本文對以上列舉的12種數據矩陣構建方法進行了實驗比較與分析，見6.1節。

根據數據矩陣分解的因子個數對算法進行劃分，可以將基于NMF的社區發現方法大體分為兩類：二因子分解和三因子分解。二因子分解，即將非負數據矩陣分解為兩個低維的非負矩陣的乘積。進一步，可將其分為標準的非負矩陣分解和對稱的非負矩陣分解。三因子分解是指數據矩陣通過3個因子的乘積來逼近，得到節點的隸屬度矩陣和社區間的關聯矩陣（表示社區與社區的關聯強度）。根據是否添加了先驗知識進行社區劃分，可以將基于NMF的社區發現方法分為無監督的社區發現方法和半監督的社區發現方法。下面以此為劃分準則，對基于NMF的社區發現方法進行總結。

4　基于NMF的無監督社區發現方法

Zhang等人[34]率先以鄰接矩陣作為數據矩陣，采用標準的非負矩陣分解方法NMFLSE進行分解，得到新的特征空間的基矩陣W和節點在該特征空間的系數矩陣，即節點到社區的隸屬度矩陣H。該分解模型是一個通用模型，能夠同時處理有向網絡和無向網絡，可表示為：

之后，根據具體的應用，相繼提出不同的擴展模型來挖掘網絡中的社區結構。網絡根據邊的方向性可分為有向網絡和無向網絡。Wang等人[32]針對無向網絡，提出了對稱的二因子模型SNMF（symmetric nonnegative matrix factorization），將數據矩陣分解為兩個對稱的低維非負矩陣的乘積，該模型表示為：

其中，H是隸屬度矩陣，其每行元素的值表示每個節點隸屬于各社區的程度。針對有向網絡，對非對稱數據矩陣進行三因子分解，得到節點對社區的隸屬度矩陣和社區之間的關系矩陣，該ANMF（asymmetric nonnegative matrix factorization）模型表示為：

其中，S是社團間的關系矩陣，元素值表示社團間的關聯強度。根據社區的定義，社區內節點連邊緊密，社區間連邊稀疏，因此通常得到的S矩陣的主對角元素值較大。

復雜網絡分析中，鄰接矩陣A通常用來表示網絡中節點間的鏈接關系。一般認為，矩陣中的零元素意味著兩個節點間不存在鏈接，然而，未被實際觀測到的邊也會給對應元素賦值為0。如果直接逼近鄰接矩陣A，未觀測的邊會增加模型的噪音，影響最終的結果。并且考慮到實際網絡中節點通常不會同時屬于多個社區，因此Zhang等人[35]對隸屬度矩陣用l1范數進行約束以增強其稀疏性，得到每個節點到各社區的概率，提出了BNMTF（bounded nonnegative matrix factorization）模型，用三因子的乘積對鄰接矩陣中非零元素進行逼近，其定義如下：

其中，I為單位向量；D為損失函數，可以采用均方誤差DLSE（A，HSHT）或廣義KL散度DKL（A，HSHT）。該模型通過逐個逼近鄰接矩陣中非零元素，求解得到節點隸屬于每個社區的概率矩陣。

Nguyen等人[29]為了更有效地處理有權網絡，提出了iSNMF方法和iANMF方法，以廣義KL散度作為損失函數，將鄰接矩陣A分解為對稱的二因子和三因子，即分別最小化如下目標函數：

其中，H為節點的隸屬度矩陣；S為社區間關系矩陣，其對應元素的值表示社團間連接的緊密程度。這兩種方法不僅能處理有權網絡，也能處理無權網絡。

BNMF[30]是一種基于概率圖模型的社區發現方法。根據實際的網絡結構，構建一個圖模型，通過學習模型的參數以擬合觀測到的網絡結構。假設實際網絡的鄰接矩陣為A，A?是期望的鏈接結構，A?由兩個低秩的非負矩陣W＝[Wic]∈和H＝[Hjc]∈組成。對于節點vi和節點vj，其連邊數（或鏈接權重）建模為＝，表示節點vi和vj在各社區中的共同參與程度。

圖1給出了算法的概率圖，其中βc為參數，其分布又受兩個固定參數a和b影響，稱為超參數。通過概率圖模型，根據實際觀測到的網絡中節點的連邊情況，最大化后驗概率：

其中，p（A）為實際觀測到的，屬于自由參數。等價地，上式可以表示為最小化目標函數：

Ψ＝?lnp（A|W，H）?lnp（W|β）?lnp（H|β）?lnp（β）

Fig.1 Graph model of W and H圖1　生成矩陣W和H的圖模型

通過交替地固定其中任意兩個變量，更新另一個變量，不斷更新W、H和β，直到算法收斂，得到了網絡中每個節點到k個社區的隸屬度矩陣H。

其中，H是節點到各社區的隸屬度矩陣；S是社區度的對角矩陣，對角元素的值表示各社區中期望的節點度。由于S是一個對角矩陣，則得到如下變換：

HSHT＝HS1/2S1/2HT＝（HS1/2）（HS1/2）T＝UUT

因此，目標函數退化為對稱的矩陣分解形式：

通過求解得到U，根據上式等價變換和對H的約束，求得S＝（IU）2，其中I為n維列向量，那么得到U＝HS1/2，進而得到隸屬度矩陣H＝U（S1/2）?1。

阿里不明白這些，只覺得好熱鬧，他不禁高興起來。拍著巴掌又蹦又跳地大聲唱：“阿里的弟弟過來了!阿里的爸爸過來了!”

以上介紹的方法都是通過得到節點對各社區的隸屬度，從而得到節點的劃分。He等人[27]從鏈接社區的角度，利用生成模型提出基于NMF的鏈接社區發現方法NMFIB。首先，定義社區c的規模為Bc，即該社區內邊權重和的兩倍，?ic表示從社區c生成一條連接節點vi的邊的概率，從社區c連邊所有節點的概率和為1。那么，生成一條連接節點vi和vj的邊的概率為A?ij＝∑cBc?ic?jc。對于一個有m條邊的網絡，得到如下目標函數：

通過引入輔助變量H，將該問題轉化為帶約束的對稱矩陣分解模型：

其中，Hic＝?ic，I為n維列向量。通過梯度下降法，對Hic進行更新直至算法收斂。根據約束條件＝1，易得到每條邊屬于各社區的隸屬度?ic＝Hic/∑iHic。根據隸屬度矩陣，實現網絡中邊的劃分，從而得到邊連接的節點的社區指派：屬于同一類的邊所對應的節點屬于同一社區，如果存在節點同時屬于多個社區，則根據邊的隸屬度將節點指派到最大隸屬度對應的社區。

Table 1 Statistics of community detection algorithms based on NMF表1　基于NMF的社區發現方法統計表

基于NMF的社區發現方法取得了一定的研究成果，然而傳統方法通常對初始矩陣W和H進行隨機初始化，這樣會造成結果的不穩定，而且降低算法的收斂速度。為解決初始化問題，Tang等人提出了IBNMF（initialized Bayesian nonnegative matrix factorization）方法[31]。該方法基于對稱的非負矩陣分解模型BNMF[30]，通過NNDSVD（nonnegative double singular value decomposition）[49]近似方法對W和H進行初始化，明顯提高了算法的收斂速度，而且能夠得到更加穩定的結果。更多基于NMF的無監督社區發現方法的統計信息見表1上部分。

5　基于NMF的半監督社區發現方法

以上基于NMF的社區發現方法只根據網絡中節點間的鏈接關系發現社區結構，屬于無監督的社區發現方法。如果考慮網絡的先驗信息，則得到半監督的社區發現方法。該類方法能夠更準確地發現復雜網絡中的社團結構，尤其在社區結構不清晰的情況下，仍能得到較好的結果。

Ma等人[28]融合網絡的領域知識對原來的數據矩陣X進行更新來指導節點的聚類過程，提出了半監督的對稱非負矩陣分解方法SNMF-SS。他們將節點對之間的約束分為兩類：“一定鏈接”（must-link）約束指屬于CML的節點對一定屬于同一個社區；“不能鏈接”（cannot-link）約束指屬于CCL的節點對分屬不同社區。文中，首先通過SK方法[40]構造數據矩陣X。通過向X中增加約束，使得處于同一個社區的兩個節點具有較高相似性，降低屬于不同社區的節點對間的相似度值，得到新的數據矩陣：

其中，γ和β是參數；MML和MCL是通過以上介紹的相似度方法構造的兩個相似度矩陣。文中選用對稱矩陣分解，用兩個對稱矩陣的乘積逼近新的數據矩陣。因此，SNMF-SS最小化如下目標函數：

SNMF-SS采用不同的相似度方法構造節點對的約束矩陣，通過對原始相似度矩陣進行補充，得到新的數據矩陣，從而增強原來待分解矩陣。特殊地，當γ＝β＝0時，SNMF-SS退化為無監督的對稱非負矩陣分解方法。

類似地，Zhang直接對網絡的鄰接矩陣增加成對的約束（“一定鏈接”和“不能鏈接”），提出了半監督的社區發現方法SS-master1[36]。成對約束中，如果兩個節點屬于同一個社區，對應鄰接矩陣的相應元素取值為α（文中α＝2）；如果兩個節點一定不屬于同一個社區，則鄰接矩陣對應元素取值為0。

Zhang等人在對鄰接矩陣直接增加約束后，通過考慮節點對約束的傳遞性，對增加的約束進一步增強，提出了增強的半監督社區發現方法SS-master2[37]。約束的傳遞性（邏輯推理）主要從以下兩點考慮：

（1）朋友的朋友是朋友。如果節點i和k屬于同一個社區，節點i和t屬于同一個社區，那么節點k和t也屬于同一社區。

（2）敵人的朋友也是敵人。如果節點i和k屬于同一個社區，節點i和t屬于不同的社區，那么節點k 和t分屬不同的社區。

對約束后的鄰接矩陣，通過標準的非負矩陣分解得到節點的隸屬度矩陣，從而實現對節點的劃分。Zhang通過實驗發現，“一定鏈接”約束相比于“不能鏈接”約束能夠得到更好的劃分結果，說明“一定鏈接”能夠為提高算法的準確率提供更多的先驗知識。

以上介紹的半監督的社區發現方法都是根據先驗知識對待分解的數據矩陣X進行更新，Yang等人[33]提出一種基于節點隱空間約束的模型，對屬于同一社區的節點增加圖正則化項，使得越相近的節點在隱空間的向量表示盡可能相近。若分別用均方距離和廣義KL散度作為節點間的度量，即最小化如下目標函數，分別記為G-LSE和G-KL： FKL（A，W，H）＝

其中，λ是調節網絡拓撲結構信息和節點先驗信息所占比重的參數。L＝D?C是拉普拉斯矩陣，C是節點的約束矩陣，如果vi和vj屬于同一個社區，那么Cij≠0，D是對角矩陣（Dii＝∑jCij）。該方法通過考慮“一定鏈接”的約束，使得屬于同一社區的兩個節點，在低維空間的表示更相近（距離更近），從而能夠得到更加準確的劃分結果。更多基于NMF的半監督社區發現方法的統計信息見表1下部分。

6　實驗對比和分析

為了比較基于NMF的社區發現方法的性能并進行分析，以準確率和標準互信息作為評價指標，選取6個真實數據和兩組人工生成網絡進行測試。實際網絡包括經典的Zachary空手道俱樂部網絡[45]、海豚關系網絡[50]、美國大學足球賽網絡[2]、美國政治書籍網絡（http://www.orgnet.com）、博客網絡[51]和蛋白質交互（protein-protein interaction，PPI）網絡[51]。人工生成網絡包括的GN網絡[1]和LFR網絡[52]。所有實驗都是用Matlab實現，在Intel Core CPU 3.00 GHz，4.00 GB內存的Windows 8（64位）計算機上運行，各社區發現方法的迭代終止條件為最大迭代次數達到200或兩次迭代目標函數值的變化小于e?10。

6.1數據矩陣對社區發現結果分析

首先，比較數據矩陣對社區劃分結果的影響。在6個真實網絡中用12種矩陣構建方法構造數據矩陣，用NMFLSE

[17，34]對數據矩陣進行分解。為保證實驗的公平性，在同一數據集上，每次采用同一組初始化因子矩陣W和H進行隨機初始化（IBNMF[31]用NNDSVD進行初始化），表2和表3列出了20次運行的平均結果。從表中可以得到以下結論：

（1）通過相似度計算得到新的數據矩陣對網絡進行表示，能夠更多地捕獲到網絡中節點間的關系信息，因此社區劃分準確性往往高于直接采取簡單的鄰接矩陣。

Table 2 Accuracy comparison of different data matrices表2　采取不同數據矩陣的準確率比較

Table 3 Normalized mutual information comparison of different data matrices表3　采取不同數據矩陣的標準互信息比較

（2）不同的相似度矩陣適應的網絡類型不同，因此在不同數據集上得到的結果不同。總體上，基于物理過程的方法，如信號傳播方法Signal和局部隨機游走方法NRW表現出較好的性能。

（3）進行相似度計算作為NMF的預處理步驟往往會增加算法的復雜度，因此在實際應用中，往往需要在算法的準確率和效率之間進行合理折中。

6.2基于NMF無監督社區發現方法比較

本節對基于NMF的無監督社區發現方法進行比較，結果如表4所示，所有方法都以網絡的鄰接矩陣作為數據矩陣。通過表4可以發現，以平方誤差作為損失函數得到的結果通常比廣義KL散度好。還觀察到模型的求解方法會影響算法的效率，例如BNMTF方法采取的優化方法需要逐個對矩陣中的元素進行更新，算法復雜度較高，因此不適用于處理規模較大的網絡。所有算法中，NMFIB方法通過對邊進行劃分，得到網絡中節點的社區結構在幾個數據集中都表現出比較好的性能。IBNMF方法通過NNDSVD對初始分解因子W和H進行初始化，在Zachary網絡、海豚網絡和政治書籍網絡中取得了較好結果，劃分結果更加魯棒。

6.3基于NMF半監督社區發現方法比較

本節通過在人工生成的GN網絡[1]和LFR網絡[52]上進行實驗，以無監督的NMFLSE[17]作為基準方法，比較半監督社區發現方法G-LSE[33]、G-KL[33]、SS-master1[36]、SS-master2[37]和SNMF-SS[28]的性能。實驗中，SNMF-SS的參數設置為γ＝0.3，β＝0.001，G-LSE和G-KL中λ＝5，SS-master1和SS-master2中α＝2。為了保證實驗的公平性，均勻隨機選擇增加的約束對，在不同先驗信息約束下，各算法選取同一組初始化因子進行隨機初始化，每個約束下運行算法20次。圖2為Zout＝Zin＝8時的GN網絡，圖3為LFR網絡（節點數n＝1 000，μ＝0.9），橫坐標表示增加的約束對比例，縱坐標表示算法的性能。通過比較，可以得到如下結論：

（1）與未增加任何約束的NMFLSE比較，通過增加先驗知識能夠提高網絡中社區劃分的準確率。

Table 4 Comparison results on accuracy and normalized mutual information of different algorithms on real-world networks表4　算法在實際網絡中的社區劃分準確率和標準互信息比較

Fig.2 Comparison results on GN networks圖2　GN網絡上的結果比較

（2）通過對G-LSE和G-KL進行比較，選取平方誤差作為損失函數往往得到更好的結果，這與無監督的社區發現方法得到的結果一致。

（3）在5個半監督社區發現方法中，簡單地在鄰接矩陣上增加約束的方法，如SS-master1和SS-master2方法能夠得到較好的劃分效果，其中通過邏輯推理進行增強的SS-master2表現出最好的效果，尤其當增加的約束比例較低時，SS-master2能夠顯著提高社區劃分的準確率。

Fig.3 Comparison results on LFR networks（n＝1 000，μ＝0.9）圖3　LFR網絡上的結果比較（n＝1 000，μ＝0.9）

7　結束語

本文對目前已有的基于NMF的社區發現方法進行了總結，通過在人工網絡和實際網絡上實驗，對不同的算法性能進行了比較和分析。NMF已經在圖像處理、生物信息處理和文本處理等領域得到了成功應用，但是在復雜網絡分析中的應用仍處于起步階段。盡管現有的工作對網絡中社區發現問題進行了一定的研究，但是還有很多問題值得深入探索。

（1）NMF初始化。NMF需要對初始因子W和H進行初始化，好的初始化因子能夠極大提高算法的準確率和收斂速度。目前常通過隨機初始化方法對因子矩陣賦初始值，此時不能對算法給出好的估計，會影響算法的性能。目前已經提出一些NMF初始化方法，如K均值初始化、中心初始化、NNDSVD等，但是初始化作為NMF的預處理步驟會增大算法的計算復雜度，而且不同的NMF求解算法對因子的初始化要求也不同，如有些算法需要同時對兩個因子進行初始化，有些則只需要初始化W。因此，針對社區發現方法的特殊應用，如何設計有效的因子矩陣初始化方法，以及確定初始化的因子矩陣個數是有待解決的問題。

（2）隱含因子數的確定。目前基于NMF的社區發現方法中，大都需要提前設定隱含因子數k，即社區劃分的個數。一種簡單的處理方法是通過設置不同的k值，從中選擇使得劃分結果最好的作為最終的劃分，這無疑也會降低算法的效率。盡管現在有些方法提出了k選擇的策略，如BNMF首先設置最大可能的社區個數k0，通過迭代隱含因子W和H，根據非零列（非零行）的個數減小k0，當算法收斂時，得到最終的k0為社區的個數。NMFIB則通過迭代二分方法，將初始整個網絡首先通過NMF劃分為兩部分，然后對得到的兩個子網絡劃分成兩部分，每次劃分時，通過一定規則判定是否接受此次劃分，當算法結束時，得到社區的個數。然而這些方法都是嵌入在社區劃分過程中，容易受到多種因素的影響，如矩陣的初始和更新情況等，可能會得到不同的k，難以準確確定社區的個數。因此，社區劃分個數k的選擇值得進一步研究。

（3）處理具有復雜特性的網絡。隨著社交媒體的發展，實際網絡呈現出更加復雜的特性，如網絡大多具有動態變化性，如何應用NMF模型發現動態網絡中的社區結構及其演變規律，設計在線的NMF算法為探索網絡中社區結構提出新的要求。另外，目前網絡多呈異構特性，網絡不僅包含節點間的鏈接關系，而且還包含豐富的節點和鏈接的屬性信息，如何根據網絡中節點的鏈接關系和屬性信息，應用NMF模型處理這類復雜的網絡為進一步的研究提出新的挑戰。

（4）處理大規模網絡數據。目前網絡規模成指數級增長，為了處理大規模網絡數據，采取快速的求解算法以提高NMF收斂速率提供了一條解決思路。然而，為了更有效挖掘大規模網絡中的社區結構，設計分布式NMF以及并行NMF策略將成為重要的研究內容，也是亟待解決的問題。

References:

[1] Girvan M，Newman M E. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences，2002，99（12）: 7821-7826.

[2] Newman M E，Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E，2004，69（2）: 026113.

[3] Newman M E. The structure and function of complex networks[J]. SIAM Review，2003，45（2）: 167-256.

[4] Fiedler M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal，1973，23（2）: 298-305.

[5] Pothen A，Simon H D，Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on Matrix Analysis and Applications，1990，11（3）: 430-452.

[6] Shiga M，Takigawa I，Mamitsuka H. A spectral clustering approach to optimally combining numerical vectors with a modular network[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，San Joze，USA，Aug 12-15，2007. New York，USA: ACM，2007: 647-656.

[7] Aldecoa，R，Marín I. Surprise maximization reveals the community structure of complex networks[J]. Scientific Reports，2013，3: 1060.

[8] Blondel V D，Guillaume J L，Lambiotte R，et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment，2008（10）: P10008.

[9] Jiang Yawen，Jia Caiyan，Yu Jian. An efficient community detection algorithm using greedy surprise maximization[J]. Journal of Physics A: Mathematical and Theoretical，2014，47（16）: 165101.

[10] Newman M E. Detecting community structure in networks[J]. The European Physical Journal B: Condensed Matter and Complex Systems，2004，38（2）: 321-330.

[11] Fortunato S，Latora V，Marchiori M. Method to find community structures based on information centrality[J]. Physical Review E，2004，70（5）: 056104.

[12] Frey B J，Dueck D. Clustering by passing messages between data points [J]. Science，2007，315（5814）: 972-976.

[13] Jiang Yawen，Jia Caiyan，Yu Jian. An efficient community detection method based on rank centrality[J]. Physica A: Statistical Mechanics and Its Applications，2013，392（9）: 2182-2194.

[14] Mete M，Tang Fusheng，Xu Xiaowei，et al. A structural approach for finding functional modules from large biological networks[J]. BMC Bioinformatics，2008，9（S9）: S19.

[15] Xu Xiaowei，Yuruk N，Feng Zhidan，et al. Scan: a structural clustering algorithm for networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，San Joze，USA，Aug 12-15，2007. New York，USA:ACM，2007: 824-833.

[16] Paatero P，Tapper U. Positive matrix factorization: a nonnegative factor model with optimal utilization of error estimates of data values[J]. Environmetrics，1994，5（2）: 111-126.

[17] Lee D D，Seung H S. Learning the parts of objects by nonnegative matrix factorization[J]. Nature，1999，401（6755）: 788-791.

[18] Ding C，Li Tao，Jordan M I. Convex and semi-nonnegative matrix factorizations[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（1）: 45-55.

[19] Ding C，Li Tao，Peng Wei. On the equivalence between nonnegative matrix factorization and probabilistic latent semantic indexing[J]. Computational Statistics＆Data Analysis，2008，52（8）: 3913-3927.

[20] Ding C，He Xiaofeng，Simon H D. On the equivalence of nonnegative matrix factorization and spectral clustering[C]// Proceedings of the 5th International Conference on Data Mining，Newport Beach，USA，Apr 21-23，2005. Philadelphia，USA: SIAM，2005: 606-610.

[21] Li S Z，Hou Xinwen，Zhang Hongjiang，et al. Learning spatially localized，parts-based representation[C]//Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Kauai，Hawaii，USA，Dec 8-14，2001. Piscataway，USA: IEEE，2001: I-207-I-212.

[22] Pauca V P，Shahnaz F，Berry M W，et al. Text mining using non-negative matrix factorizations[C]//Proceedings of the 4th International Conference on Data Mining，Lake BuenaVista，USA，Apr 22-24，2004. Philadelphia，USA: SIAM，2004: 452-456.

[23] Shahnaz F，Berry M W，Pauca V P，et al. Document clustering using nonnegative matrix factorization[J]. Information Processing＆Management，2006，42（2）: 373-386.

[24] Cooper M，Foote J. Summarizing video using non-negative similarity matrix factorization[C]//Proceedings of the IEEE 5th Workshop on Multimedia Signal Processing，Virgin Islands，USA，Dec 9-11，2002. Piscataway，USA: IEEE，2002: 25-28.

[25] Pascual-Montano A，Carazo J M，Kochi K，et al. Nonsmooth nonnegative matrix factorization（nsNMF）[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28（3）: 403-415.

[26] Cao Xiaochun，Wang Xiao，Jin Di，et al. Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization[J]. Scientific Reports，2013，3: 2993.

[27] He Dongxiao，Jin Di，Baquero C，et al. Link community detection using generative model and nonnegative matrix factorization[J]. PloS One，2014，9（1）: e86899.

[28] Ma Xiaoke，Gao Lin，Yong Xuerong，et al. Semi-supervised clustering algorithm for community structure detection in complex networks[J]. Physica A: Statistical Mechanics and Its Applications，2010，389（1）: 187-197.

[29] Nguyen N P，Thai M T. Finding overlapped communities in online social networks with nonnegative matrix factorization[C]//Proceedings of the 2012 Military Communications Conference，Orlando，USA，Oct 29-Nov 1，2012. Piscataway，USA: IEEE，2012: 1-6.

[30] Psorakis I，Roberts S，Ebden M，et al. Overlapping community detection using Bayesian non-negative matrix factorization[J]. Physical Review E，2011，83（6）: 066114.

[31] Tang Xianchao，Xu Tao，Feng Xia，et al. Uncovering community structures with initialized Bayesian nonnegative matrix factorization[J]. PloS One，2014，9（9）: e107884.

[32] Wang Fei，Li Tao，Wang Xin，et al. Community discovery using nonnegative matrix factorization[J]. Data Mining and Knowledge Discovery，2011，22（3）: 493-521.

[33] Yang Liang，Cao Xiaochun，Jin Di，et al. A unified semisupervised community detection framework using latent space graph regularization[J]. IEEE Transactions on Cybernetics，2015，45（11）: 2585-2598.

[34] Zhang Shihua，Wang Ruisheng，Zhang Xiangsun. Uncovering fuzzy community structure in complex networks[J]. Physical Review E，2007，76（4）: 046103.

[35] Zhang Yu，Yeung D Y. Overlapping community detection via bounded nonnegative matrix tri-factorization[C]//Proceedings of the 18th International Conference on Knowledge Discovery and Data Mining，Beijing，China，Aug 12-16，2012. Piscataway，USA: IEEE，2012: 606-614.

[36] Zhang Zhongyuan. Community structure detection in complex networks with partial background information[J]. Europhysics Letters，2013，101（4）: 48005.

[37] Zhang Zhongyuan，Sun Kaidi，Wang Siqi. Enhanced community structure detection in complex networks with partial background information[J]. Scientific Report，2013，3: 3241. [38] Wang Ruisheng，Zhang Shihua，Wang Yong，et al. Clustering complex networks and biological networks by nonnegative matrix factorization with various similarity measures[J]. Neurocomputing，2008，72（1/3）: 134-141.

[39] Leicht E，Holme P，Newman M E. Vertex similarity in networks[J]. Physical Review E，2006，73（2）: 026120.

[40] Kondor R I，Lafferty J. Diffusion kernels on graphs and other discrete input spaces[C]//Proceedings of the 19th International Conference on Machine Learning，Sydney，Australia，Jul 8-12，2002. New York，USA:ACM，2002: 315-322.

[41] Hu Yanqing，Li Menghui，Zhang Peng，et al. Community detection by signaling on complex networks[J]. Physical Review E，2008，78（1）: 016115.

[42] Ma Hao，King I，Lyu M R. Mining Web graphs for recommendations[J]. IEEE Transactions on Knowledge and Data Engineering，2012，24（6）: 1051-1064.

[43] Liu Weiping，Lv Linyuan. Link prediction based on local random walk[J]. Europhysics Letters，2010，89（5）: 58007.

[44] Zhou Yang，Cheng Hong，Yu J X. Graph clustering based on structural/attribute similarities[J]. Proceedings of the VLDB Endowment，2009，2（1）: 718-729.

[45] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research，1977，33（4）: 452-473.

[46] Jiao Junyong，Hu Di，Zhang Zhongyuan. A novel similarity measurement for community structure detection[C]//Procee-dings of the 4th International Conference on Intelligent Human-Machine Systems and Cybernetics，Nanchang，China，Aug 26-27，2012. Piscataway，USA: IEEE，2012: 301-306.

[47] Gustafsson M，H?rnquist M，Lombardi A. Comparison and validation of community structures in complex networks[J]. Physica A: Statistical Mechanics and Its Applications，2006，367: 559-576.

[48] Lv Linyuan，Zhou Tao. Link prediction in complex networks: a survey[J]. Physica A: Statistical Mechanics and Its Applications，2011，390（6）: 1150-1170.

[49] Boutsidis C，Gallopoulos E. SVD based initialization: a head start for nonnegative matrix factorization[J]. Pattern Recognition，2008，41（4）: 1350-1362.

[50] Lusseau D，Schneider K，Boisseau O J，et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology，2003，54（4）: 396-405.

[51] Adamic L A，Glance N. The political blogosphere and the 2004 US election: divided they blog[C]//Proceedings of the 3rd International Workshop on Link Discovery，Chicago，USA，Aug 21-24，2005. New York，USA:ACM，2005: 36-43.

[52] Lancichinetti A，Fortunato S，Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E，2008，78（4）: 046110.

LI Yafang was born in 1988. She is a Ph.D. candidate at Beijing Jiaotong University，and the student member of CCF. Her research interests include data mining and complex network analysis，etc.

李亞芳（1988—），女，河北滄州人，北京交通大學博士研究生，CCF學生會員，主要研究領域為數據挖掘，復雜網絡分析等。

JIA Caiyan was born in 1976. She received the Ph.D. degree in computer software and theory from Institute of Computing Technology，Chinese Academy of Sciences in 2004. Now she is an associate professor at Beijing Jiaotong University，and the member of CCF. Her research interests include data mining，bioinformatics and complex network analysis，etc.

賈彩燕（1976—），女，寧夏石嘴山人，2004年于中國科學院計算技術研究所計算機軟件與理論專業獲得博士學位，現為北京交通大學計算機學院副教授，CCF會員，主要研究領域為數據挖掘，生物信息學，復雜網絡分析等。

YU Jian was born in 1969. He received the Ph.D. degree from Department of Mathematics，Peking University in 2000. Now he is a professor and Ph.D. supervisor at Beijing Jiaotong University，and the senior member of CCF. His research interests include machine learning，data mining and image segmentation，etc.

于劍（1969—），男，山東淄博人，2000年于北京大學數學系獲得博士學位，現為北京交通大學計算機學院教授、博士生導師，CCF高級會員，主要研究領域為機器學習，數據挖掘，圖像分割等。

Survey on Community Detection Algorithms Using Nonnegative Matrix Factorization Model*

LI Yafang1，2，JIACaiyan1，2＋，YU Jian1，2
1. School of Computer and Information Technology，Beijing Jiaotong University，Beijing 100044，China
2. Beijing Key Lab of Traffic Data Analysis and Mining，Beijing 100044，China
＋Corresponding author: E-mail: cyjia@bjtu.edu.cn

LI Yafang，JIA Caiyan，YU Jian. Survey on community detection algorithms using nonnegative matrix factorization model. Journal of Frontiers of Computer Science and Technology，2016，10（1）：1-13.

Abstract:Nonnegative matrix factorization（NMF）has good ability in extracting inherent patterns and structures in high dimensional data and has been one of hot research topics in data mining. Nonnegative matrix factorization is a tool for unsupervised learning and has been widely applied in pattern recognition，text mining，image processing and bioinformatics. Recently，many researchers have paid attention to network-based data mining via nonnegative matrix factorization in order to detect cohesively connected community in networks. This paper summarizes community detection algorithms using nonnegative matrix factorization，including unsupervised methods and semi-supervised algorithms. Then，this paper compares and analyzes the performance of different algorithms by conducting experiments on artificial networks and real-world networks. Finally，this paper discusses challenges and further work on detecting communities in networks by using nonnegative matrix factorization.

Key words:data mining; nonnegative matrix factorization; community detection

文獻標志碼：A

中圖分類號：TP181

doi:10.3778/j.issn.1673-9418.1505047