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

?

應(yīng)用非負矩陣分解模型的社區(qū)發(fā)現(xiàn)方法綜述*

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

* The National Natural Science Foundation of China under Grant Nos. 61473030，61370129（國家自然科學(xué)基金）; the Fundamental Research Funds for the Central Universities of China under Grant Nos. K15JB00070，2014JBM031（中央高?；究蒲袠I(yè)務(wù)費專項資金）; the Opening Project of State Key Laboratory of Digital Publishing Technology（數(shù)字出版國家重點實驗室專項課題）.

Received 2015-05，Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-08-12，http://www.cnki.net/kcms/detail/11.5602.TP.20150812.1638.008.html

李亞芳，賈彩燕，于劍.應(yīng)用非負矩陣分解模型的社區(qū)發(fā)現(xiàn)方法綜述[J].計算機科學(xué)與探索，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）在提取高維數(shù)據(jù)中隱含模式和結(jié)構(gòu)方面具有良好性能，已成為數(shù)據(jù)挖掘領(lǐng)域的熱點研究之一。NMF作為無監(jiān)督學(xué)習(xí)的有效工具，在模式識別、文本處理、多媒體數(shù)據(jù)分析以及生物信息學(xué)等研究領(lǐng)域得到了廣泛應(yīng)用。目前，已有工作將NMF模型應(yīng)用于網(wǎng)絡(luò)數(shù)據(jù)挖掘，發(fā)現(xiàn)網(wǎng)絡(luò)中隱含的社區(qū)結(jié)構(gòu)。對基于NMF的社區(qū)發(fā)現(xiàn)方法進行了總結(jié)，包括無監(jiān)督的社區(qū)發(fā)現(xiàn)方法和半監(jiān)督的社區(qū)發(fā)現(xiàn)方法，通過在實際網(wǎng)絡(luò)和人工網(wǎng)絡(luò)進行實驗，比較分析了不同算法的性能，進一步研究了當(dāng)前基于NMF發(fā)現(xiàn)社區(qū)結(jié)構(gòu)所面臨的挑戰(zhàn)，并對下一步研究方向進行了展望。

關(guān)鍵詞：數(shù)據(jù)挖掘；非負矩陣分解；社區(qū)發(fā)現(xiàn)

1　引言

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

目前，網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的研究已經(jīng)取得很多研究成果，可以大體將社區(qū)發(fā)現(xiàn)方法分為圖切割方法[4-6]、目標(biāo)函數(shù)優(yōu)化方法[7-10]、聚類方法[11-13]和啟發(fā)式方法[14-15]等。本質(zhì)上，社區(qū)發(fā)現(xiàn)問題屬于無監(jiān)督學(xué)習(xí)范疇，因此研究者逐漸將目光投向無監(jiān)督學(xué)習(xí)領(lǐng)域中取得成功應(yīng)用的非負矩陣分解（nonnegative matrix factorization，NMF）模型處理網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)探測的問題。

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

本文對基于NMF的社區(qū)發(fā)現(xiàn)方法進行了總結(jié)，分析了當(dāng)前研究面臨的挑戰(zhàn)，并對下一步研究方向進行了展望。本文組織結(jié)構(gòu)為：第2章介紹非負矩陣分解基本模型以及應(yīng)用于社區(qū)發(fā)現(xiàn)的解釋；第3章介紹構(gòu)建NMF模型中數(shù)據(jù)矩陣的方法；第4章對基于NMF的無監(jiān)督社區(qū)發(fā)現(xiàn)方法進行總結(jié)；第5章介紹基于NMF的半監(jiān)督社區(qū)發(fā)現(xiàn)方法；第6章進行實驗比較和分析；最后指出基于NMF發(fā)現(xiàn)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)遇到的挑戰(zhàn)，并對未來的研究工作進行展望。

2　NMF基本概念和定義

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

min D（X，WHT）

s.t. W≥0，H≥0

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

稱該方法為NMFKL。損失函數(shù)的選擇，通常依據(jù)不同的應(yīng)用而定。為了優(yōu)化該目標(biāo)函數(shù)，常用的優(yōu)化方法有多步迭乘法、梯度下降法、投影梯度法和交替最小二乘法等。

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

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

通過以上兩種方法得到的隸屬度矩陣通常是節(jié)點的軟化分矩陣，對應(yīng)元素是取值為0到1的實數(shù)，表示每個節(jié)點屬于各社區(qū)的程度。如果將節(jié)點指派到較大的隸屬度對應(yīng)的社區(qū)，則得到網(wǎng)絡(luò)的重疊社區(qū)劃分結(jié)果；如果將節(jié)點唯一指派到最大隸屬度對應(yīng)的社區(qū)，就得到非重疊劃分的社區(qū)結(jié)構(gòu)。

3　構(gòu)建基于NMF社區(qū)發(fā)現(xiàn)方法的數(shù)據(jù)矩陣

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

根據(jù)數(shù)據(jù)矩陣的構(gòu)造方法進行劃分，大體可以分為以下幾類：

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

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

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

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

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

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

4　基于NMF的無監(jiān)督社區(qū)發(fā)現(xiàn)方法

Zhang等人[34]率先以鄰接矩陣作為數(shù)據(jù)矩陣，采用標(biāo)準(zhǔn)的非負矩陣分解方法NMFLSE進行分解，得到新的特征空間的基矩陣W和節(jié)點在該特征空間的系數(shù)矩陣，即節(jié)點到社區(qū)的隸屬度矩陣H。該分解模型是一個通用模型，能夠同時處理有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)，可表示為：

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

其中，H是隸屬度矩陣，其每行元素的值表示每個節(jié)點隸屬于各社區(qū)的程度。針對有向網(wǎng)絡(luò)，對非對稱數(shù)據(jù)矩陣進行三因子分解，得到節(jié)點對社區(qū)的隸屬度矩陣和社區(qū)之間的關(guān)系矩陣，該ANMF（asymmetric nonnegative matrix factorization）模型表示為：

其中，S是社團間的關(guān)系矩陣，元素值表示社團間的關(guān)聯(lián)強度。根據(jù)社區(qū)的定義，社區(qū)內(nèi)節(jié)點連邊緊密，社區(qū)間連邊稀疏，因此通常得到的S矩陣的主對角元素值較大。

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

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

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

其中，H為節(jié)點的隸屬度矩陣；S為社區(qū)間關(guān)系矩陣，其對應(yīng)元素的值表示社團間連接的緊密程度。這兩種方法不僅能處理有權(quán)網(wǎng)絡(luò)，也能處理無權(quán)網(wǎng)絡(luò)。

BNMF[30]是一種基于概率圖模型的社區(qū)發(fā)現(xiàn)方法。根據(jù)實際的網(wǎng)絡(luò)結(jié)構(gòu)，構(gòu)建一個圖模型，通過學(xué)習(xí)模型的參數(shù)以擬合觀測到的網(wǎng)絡(luò)結(jié)構(gòu)。假設(shè)實際網(wǎng)絡(luò)的鄰接矩陣為A，A?是期望的鏈接結(jié)構(gòu)，A?由兩個低秩的非負矩陣W＝[Wic]∈和H＝[Hjc]∈組成。對于節(jié)點vi和節(jié)點vj，其連邊數(shù)（或鏈接權(quán)重）建模為＝，表示節(jié)點vi和vj在各社區(qū)中的共同參與程度。

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

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

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

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

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

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

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

因此，目標(biāo)函數(shù)退化為對稱的矩陣分解形式：

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

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

以上介紹的方法都是通過得到節(jié)點對各社區(qū)的隸屬度，從而得到節(jié)點的劃分。He等人[27]從鏈接社區(qū)的角度，利用生成模型提出基于NMF的鏈接社區(qū)發(fā)現(xiàn)方法NMFIB。首先，定義社區(qū)c的規(guī)模為Bc，即該社區(qū)內(nèi)邊權(quán)重和的兩倍，?ic表示從社區(qū)c生成一條連接節(jié)點vi的邊的概率，從社區(qū)c連邊所有節(jié)點的概率和為1。那么，生成一條連接節(jié)點vi和vj的邊的概率為A?ij＝∑cBc?ic?jc。對于一個有m條邊的網(wǎng)絡(luò)，得到如下目標(biāo)函數(shù)：

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

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

Table 1 Statistics of community detection algorithms based on NMF表1　基于NMF的社區(qū)發(fā)現(xiàn)方法統(tǒng)計表

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

5　基于NMF的半監(jiān)督社區(qū)發(fā)現(xiàn)方法

以上基于NMF的社區(qū)發(fā)現(xiàn)方法只根據(jù)網(wǎng)絡(luò)中節(jié)點間的鏈接關(guān)系發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，屬于無監(jiān)督的社區(qū)發(fā)現(xiàn)方法。如果考慮網(wǎng)絡(luò)的先驗信息，則得到半監(jiān)督的社區(qū)發(fā)現(xiàn)方法。該類方法能夠更準(zhǔn)確地發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)，尤其在社區(qū)結(jié)構(gòu)不清晰的情況下，仍能得到較好的結(jié)果。

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

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

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

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

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

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

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

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

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

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

6　實驗對比和分析

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

6.1數(shù)據(jù)矩陣對社區(qū)發(fā)現(xiàn)結(jié)果分析

首先，比較數(shù)據(jù)矩陣對社區(qū)劃分結(jié)果的影響。在6個真實網(wǎng)絡(luò)中用12種矩陣構(gòu)建方法構(gòu)造數(shù)據(jù)矩陣，用NMFLSE

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

（1）通過相似度計算得到新的數(shù)據(jù)矩陣對網(wǎng)絡(luò)進行表示，能夠更多地捕獲到網(wǎng)絡(luò)中節(jié)點間的關(guān)系信息，因此社區(qū)劃分準(zhǔn)確性往往高于直接采取簡單的鄰接矩陣。

Table 2 Accuracy comparison of different data matrices表2　采取不同數(shù)據(jù)矩陣的準(zhǔn)確率比較

Table 3 Normalized mutual information comparison of different data matrices表3　采取不同數(shù)據(jù)矩陣的標(biāo)準(zhǔn)互信息比較

（2）不同的相似度矩陣適應(yīng)的網(wǎng)絡(luò)類型不同，因此在不同數(shù)據(jù)集上得到的結(jié)果不同?？傮w上，基于物理過程的方法，如信號傳播方法Signal和局部隨機游走方法NRW表現(xiàn)出較好的性能。

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

6.2基于NMF無監(jiān)督社區(qū)發(fā)現(xiàn)方法比較

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

6.3基于NMF半監(jiān)督社區(qū)發(fā)現(xiàn)方法比較

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

（1）與未增加任何約束的NMFLSE比較，通過增加先驗知識能夠提高網(wǎng)絡(luò)中社區(qū)劃分的準(zhǔn)確率。

Table 4 Comparison results on accuracy and normalized mutual information of different algorithms on real-world networks表4　算法在實際網(wǎng)絡(luò)中的社區(qū)劃分準(zhǔn)確率和標(biāo)準(zhǔn)互信息比較

Fig.2 Comparison results on GN networks圖2　GN網(wǎng)絡(luò)上的結(jié)果比較

（2）通過對G-LSE和G-KL進行比較，選取平方誤差作為損失函數(shù)往往得到更好的結(jié)果，這與無監(jiān)督的社區(qū)發(fā)現(xiàn)方法得到的結(jié)果一致。

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

Fig.3 Comparison results on LFR networks（n＝1 000，μ＝0.9）圖3　LFR網(wǎng)絡(luò)上的結(jié)果比較（n＝1 000，μ＝0.9）

7　結(jié)束語

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

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

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

（3）處理具有復(fù)雜特性的網(wǎng)絡(luò)。隨著社交媒體的發(fā)展，實際網(wǎng)絡(luò)呈現(xiàn)出更加復(fù)雜的特性，如網(wǎng)絡(luò)大多具有動態(tài)變化性，如何應(yīng)用NMF模型發(fā)現(xiàn)動態(tài)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)及其演變規(guī)律，設(shè)計在線的NMF算法為探索網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)提出新的要求。另外，目前網(wǎng)絡(luò)多呈異構(gòu)特性，網(wǎng)絡(luò)不僅包含節(jié)點間的鏈接關(guān)系，而且還包含豐富的節(jié)點和鏈接的屬性信息，如何根據(jù)網(wǎng)絡(luò)中節(jié)點的鏈接關(guān)系和屬性信息，應(yīng)用NMF模型處理這類復(fù)雜的網(wǎng)絡(luò)為進一步的研究提出新的挑戰(zhàn)。

（4）處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)。目前網(wǎng)絡(luò)規(guī)模成指數(shù)級增長，為了處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)，采取快速的求解算法以提高NMF收斂速率提供了一條解決思路。然而，為了更有效挖掘大規(guī)模網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，設(shè)計分布式NMF以及并行NMF策略將成為重要的研究內(nèi)容，也是亟待解決的問題。

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，F(xiàn)eng 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，F(xiàn)oote 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，F(xiàn)eng 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，F(xiàn)ortunato 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—），女，河北滄州人，北京交通大學(xué)博士研究生，CCF學(xué)生會員，主要研究領(lǐng)域為數(shù)據(jù)挖掘，復(fù)雜網(wǎng)絡(luò)分析等。

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年于中國科學(xué)院計算技術(shù)研究所計算機軟件與理論專業(yè)獲得博士學(xué)位，現(xiàn)為北京交通大學(xué)計算機學(xué)院副教授，CCF會員，主要研究領(lǐng)域為數(shù)據(jù)挖掘，生物信息學(xué)，復(fù)雜網(wǎng)絡(luò)分析等。

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年于北京大學(xué)數(shù)學(xué)系獲得博士學(xué)位，現(xiàn)為北京交通大學(xué)計算機學(xué)院教授、博士生導(dǎo)師，CCF高級會員，主要研究領(lǐng)域為機器學(xué)習(xí)，數(shù)據(jù)挖掘，圖像分割等。

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

文獻標(biāo)志碼：A

中圖分類號：TP181

doi:10.3778/j.issn.1673-9418.1505047