基于圖正則化非負(fù)矩陣分解的二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

汪 濤 劉 陽(yáng) 席耀一

1 引言

隨著Internet和移動(dòng)通信技術(shù)的發(fā)展，大量異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)在現(xiàn)實(shí)世界中廣泛出現(xiàn)。這些網(wǎng)絡(luò)往往由多種不同類型的異質(zhì)節(jié)點(diǎn)構(gòu)成，異質(zhì)節(jié)點(diǎn)間的交互往往代表不同的連接關(guān)系。二分網(wǎng)絡(luò)是異質(zhì)網(wǎng)絡(luò)的一種重要而具有代表性的表現(xiàn)形式，例如話題與文檔，電影與電影評(píng)價(jià)、上網(wǎng)用戶與網(wǎng)頁(yè)，合著者與其合著論文等等。二分網(wǎng)絡(luò)由兩類節(jié)點(diǎn)群體組成，并具有特殊的二分結(jié)構(gòu)：異質(zhì)節(jié)點(diǎn)間存在連接，而同類節(jié)點(diǎn)間沒有連接。當(dāng)二分網(wǎng)絡(luò)中的用戶節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)建立邊連接后，擁有共同連接節(jié)點(diǎn)的不同類型節(jié)點(diǎn)之間也具有了連通性。

社區(qū)作為網(wǎng)絡(luò)中廣泛存在的典型中尺度拓?fù)浣Y(jié)構(gòu)，能夠直接有效地反映網(wǎng)絡(luò)結(jié)構(gòu)和特性，是理解復(fù)雜網(wǎng)絡(luò)性質(zhì)和局部功能的基礎(chǔ)。單模的同質(zhì)網(wǎng)絡(luò)將社區(qū)定義為：網(wǎng)絡(luò)中具有某種相似特性的節(jié)點(diǎn)集合，社區(qū)內(nèi)部節(jié)點(diǎn)聯(lián)系緊密而社區(qū)間聯(lián)系相對(duì)稀疏。推廣到二分網(wǎng)絡(luò)，可以認(rèn)為[1,2]：社區(qū)內(nèi)部不同類型節(jié)點(diǎn)間的連接緊密，而社區(qū)間的不同節(jié)點(diǎn)間的連接則比較稀疏。二分網(wǎng)絡(luò)中兩類節(jié)點(diǎn)通過彼此間的作用、耦合形成各自所屬的二分結(jié)構(gòu)群組，說明同一社區(qū)內(nèi)的目標(biāo)節(jié)點(diǎn)群體與用戶節(jié)點(diǎn)群體相互吸引，內(nèi)聚性較強(qiáng)。因此，二分網(wǎng)絡(luò)社區(qū)除了刻畫傳統(tǒng)意義上的網(wǎng)絡(luò)結(jié)構(gòu)特征，還有助于挖掘和理解網(wǎng)絡(luò)中異質(zhì)節(jié)點(diǎn)間的作用和關(guān)系。

近年來，基于原始的二分網(wǎng)絡(luò)信息進(jìn)行社區(qū)發(fā)現(xiàn)的研究思路開始引起關(guān)注。文獻(xiàn)[3]將標(biāo)簽傳播算法應(yīng)用于二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，但其二分結(jié)構(gòu)會(huì)引起節(jié)點(diǎn)標(biāo)簽振蕩、穩(wěn)定性差等問題。在文獻(xiàn)[4～7]中分別提出了各自基于二分網(wǎng)絡(luò)的模塊度函數(shù)進(jìn)行社區(qū)結(jié)構(gòu)發(fā)現(xiàn)，這些方法沿用了單模網(wǎng)絡(luò)環(huán)境下基于NG（Newman-Girvan）模塊度來進(jìn)行社區(qū)發(fā)現(xiàn)的思想。然而，二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)與常見的單模網(wǎng)絡(luò)有著明顯區(qū)別，即同類型節(jié)點(diǎn)沒有連接，節(jié)點(diǎn)社區(qū)歸屬隱藏在二分結(jié)構(gòu)下的異質(zhì)節(jié)點(diǎn)連接關(guān)系里。二分網(wǎng)絡(luò)這種特有的二分結(jié)構(gòu)限制了基于共享鄰接節(jié)點(diǎn)的傳統(tǒng)節(jié)點(diǎn)相似性評(píng)估方法的有效性，使得僅僅依靠模塊度指標(biāo)對(duì)節(jié)點(diǎn)進(jìn)行貪婪搜索易導(dǎo)致社區(qū)聚類陷入局部最優(yōu)，難以有效地揭示二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。然而，二分網(wǎng)絡(luò)特有的二分結(jié)構(gòu)限制了基于圖分割、相似度聚類等傳統(tǒng)算法的社區(qū)發(fā)現(xiàn)性能。因?yàn)槎志W(wǎng)絡(luò)鄰接矩陣的行和列分別代表用戶節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，每個(gè)矩陣元素表示對(duì)應(yīng)異質(zhì)節(jié)點(diǎn)之間的連接關(guān)系。由于二分網(wǎng)絡(luò)特征矩陣的行和列有很強(qiáng)的相關(guān)性，若單從某一維度進(jìn)行社區(qū)發(fā)現(xiàn)，都將缺失另一維度的信息。而已有的 NMF解決方案大多基于最小化目標(biāo)函數(shù)的擬合誤差值，對(duì)二分網(wǎng)絡(luò)中的兩種節(jié)點(diǎn)子集進(jìn)行簡(jiǎn)單化地獨(dú)立處理，難以有效地揭示二分網(wǎng)絡(luò)特殊的社區(qū)結(jié)構(gòu)。

受非負(fù)矩陣分解啟發(fā)，文獻(xiàn)[8,9]分別提出了不同的非負(fù)矩陣分解模型來解決異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的問題，以挖掘異質(zhì)網(wǎng)絡(luò)中隱藏的結(jié)構(gòu)與關(guān)系。盡管上述方法能夠無監(jiān)督地應(yīng)用于復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，但是由于缺乏監(jiān)督信息（約束條件或標(biāo)簽信息）使得矩陣分解的收斂速度和結(jié)果往往并不能令人滿意，其不足主要體現(xiàn)在如下兩個(gè)方面：（1）僅僅依靠原始數(shù)據(jù)信息（即類間信息）進(jìn)行矩陣分解，忽略了類內(nèi)節(jié)點(diǎn)內(nèi)部重要的關(guān)聯(lián)信息；（2）由于矩陣分解的迭代過程中，涉及到大量而密集的矩陣乘法和求逆運(yùn)算，使得 NMF算法普遍存在時(shí)間復(fù)雜度高，收斂慢等問題。

為了解決上述問題，本文將基于圖正則化的三重非負(fù)矩陣分解方法（Fast Nonnegative Matrix Tri-Factorization, F-NMTF）應(yīng)用于二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，該模型在考慮異質(zhì)網(wǎng)絡(luò)的原始連接關(guān)系的同時(shí)，通過圖正則化將用戶子空間和目標(biāo)子空間的內(nèi)部連接關(guān)系作為圖正則化約束，從而為NMTF模型引入了類間與類內(nèi)信息以提高矩陣分解的精確度和穩(wěn)定性，以改善二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的性能。

2 問題描述

非負(fù)矩陣分解是一種有效的矩陣低秩逼近方法，能夠有效地揭示異質(zhì)網(wǎng)絡(luò)中多維數(shù)據(jù)潛在的結(jié)構(gòu)特征，已經(jīng)有多種方法被應(yīng)用于文本挖掘和協(xié)同過濾等領(lǐng)域。然而，直接將 NMF應(yīng)用于二分網(wǎng)絡(luò)數(shù)據(jù)聯(lián)合聚類，需要向其分解因子矩陣F,G同時(shí)施加非負(fù)正交的約束，約束太強(qiáng)會(huì)使矩陣分解的逼近程度大大降低，從而限制了社區(qū)發(fā)現(xiàn)的聚類性能。因此，這里引入一個(gè)新矩陣S以構(gòu)建三重非負(fù)矩陣分解，該方法的優(yōu)勢(shì)主要體現(xiàn)在以下 3個(gè)方面[10]：（1）三重非負(fù)矩陣分解通過引入光滑因子矩陣S，極大改善了聯(lián)合聚類過程中矩陣分解的自由度；（2）通過全面引入類間信息和類內(nèi)信息，NMTF可結(jié)合雙重子空間的流形約束提高聯(lián)合聚類的性能；（3）優(yōu)化后的迭代規(guī)則大大減小了NMTF的計(jì)算復(fù)雜度，能夠快速地發(fā)現(xiàn)不同規(guī)模網(wǎng)絡(luò)的各種潛在結(jié)構(gòu)及社區(qū)間的交互規(guī)律。

圖1所示的用戶-網(wǎng)頁(yè)網(wǎng)絡(luò)即為一種典型的二分網(wǎng)絡(luò)，其中用戶和網(wǎng)頁(yè)表示兩類不同類型的異質(zhì)節(jié)點(diǎn)，并可以進(jìn)一步描述為由用戶節(jié)點(diǎn)集U（Users）和目標(biāo)節(jié)點(diǎn)集O（Objects）構(gòu)成的二分網(wǎng)絡(luò)模型。令G（ U, O, E）表示一個(gè)二分網(wǎng)絡(luò)，U為用戶節(jié)點(diǎn)集，O為目標(biāo)節(jié)點(diǎn)集，E為邊集。假設(shè)用戶節(jié)點(diǎn)數(shù)|U |= m ，目標(biāo)節(jié)點(diǎn)數(shù)|O | =n，給定二分網(wǎng)絡(luò)G的鄰接矩陣X ∈ ?m×n，則NMTF定義為其中， ?為 Frobenius范數(shù)（簡(jiǎn)稱 F范數(shù)），用來度量目標(biāo)函數(shù)的逼近程度；NMTF通過尋找最大近似原始網(wǎng)絡(luò)數(shù)據(jù)X的3個(gè)低階因子矩陣來實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)，F(xiàn)∈?m×r和G ∈ ?n×r分別為用戶子空間和目標(biāo)子空間的劃分矩陣，S ∈?l×r作為引入的光滑因子矩陣，表示二分網(wǎng)絡(luò)中用戶子空間與目標(biāo)子空間的特征向量組之間的關(guān)聯(lián)性。l和r表示用戶子空間和目標(biāo)子空間的聚類個(gè)數(shù)，由于基于非負(fù)矩陣分解的社區(qū)發(fā)現(xiàn)算法需要預(yù)設(shè)置網(wǎng)絡(luò)中的社區(qū)個(gè)數(shù)，一般設(shè)置l = r 。由此，NMTF通過F,G共同揭示了二分網(wǎng)絡(luò)隱藏的社區(qū)結(jié)構(gòu)，將其劃分為由二模（2-mode）節(jié)點(diǎn)混合組成的r個(gè)社區(qū)。

圖1 基于用戶-網(wǎng)頁(yè)網(wǎng)絡(luò)的二分網(wǎng)絡(luò)模型

需要指出的是，在社區(qū)發(fā)現(xiàn)的研究背景下，非負(fù)矩陣分解后的維數(shù)r與二分網(wǎng)絡(luò)中的社區(qū)個(gè)數(shù)相關(guān)，其取值直接影響著算法的收斂性能。理論上r?（m, n），但r的取值過大或過小都會(huì)影響算法的收斂性速度和最終分解結(jié)果的精確度。目前，許多基于 NMF的社區(qū)發(fā)現(xiàn)方法[11,12]提出了不同的解決方案以預(yù)估網(wǎng)絡(luò)中社區(qū)個(gè)數(shù)。由于文獻(xiàn)[11]中的預(yù)估方法相對(duì)簡(jiǎn)單有效，能夠準(zhǔn)確地估計(jì)網(wǎng)絡(luò)社區(qū)數(shù)量，故采用該方法確定r值。

3 基于圖正則化的二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)

本文基于圖正則化的三重非負(fù)矩陣分解方法以二分網(wǎng)絡(luò)矩陣非負(fù)分解的擬合誤差作為目標(biāo)函數(shù)，同時(shí)分別構(gòu)建兩種異質(zhì)節(jié)點(diǎn)子空間的k-近鄰圖，并以其關(guān)聯(lián)矩陣作為NMTF的正則化約束，并提出了一種F-NMTF的快速優(yōu)化算法，從而在二分網(wǎng)絡(luò)上實(shí)現(xiàn)基于圖正則化的半監(jiān)督社區(qū)發(fā)現(xiàn)。

3.1 二模節(jié)點(diǎn)的圖正則化

基于圖的半監(jiān)督學(xué)習(xí)在實(shí)際中應(yīng)用較為廣泛，它主要通過構(gòu)造圖結(jié)構(gòu)來引入半監(jiān)督信息，以輔助數(shù)據(jù)聚類。本文的F-NMTF通過分別構(gòu)建二模節(jié)點(diǎn)的近鄰圖來估算用戶子空間和目標(biāo)子空間的結(jié)構(gòu)特征，并作為正則化約束項(xiàng)添加到 NMTF目標(biāo)函數(shù)中，以增強(qiáng)非負(fù)矩陣分解的正交性和收斂性。這里首先分別構(gòu)建子空間U和O的k-近鄰圖，并以該關(guān)聯(lián)矩陣作為類內(nèi)（Intra-type）信息作為 NMTF模型的正則化約束。該k-近鄰圖有效融合了同類節(jié)點(diǎn)的相似性信息（即類內(nèi)信息）。

定義 1 定義用戶子集 NU關(guān)于k-近鄰圖的權(quán)重矩陣WF為

其中， N （Ui）為用戶節(jié)點(diǎn)Ui的k-最近鄰集合，并采用0-1加權(quán)方式創(chuàng)建k-近鄰圖的權(quán)重矩陣：如果Ui是 Uj的k近鄰節(jié)點(diǎn)，或 Uj是 Ui的k近鄰節(jié)點(diǎn)時(shí)，WF（ i, j）=1；否則，WF（ i, j）=0。這里可以引入權(quán)重矩陣進(jìn)一步凸顯同類節(jié)點(diǎn)間連接模式的差異性，并以此作為正則化項(xiàng)來優(yōu)化目標(biāo)函數(shù)。

根據(jù)流形假設(shè)[13]，異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)經(jīng)非負(fù)矩陣分解后，同類節(jié)點(diǎn)間的局部鄰域結(jié)構(gòu)在低維特征空間中能夠得以保持，則當(dāng)高維空間中距離較近的向量Xi.,Xj.映射到對(duì)應(yīng)的低維流形上 Fi.,Fj.時(shí)，距離依然較小。從而定義基于用戶子空間的正則化項(xiàng)為

其中?表示Frobenius范數(shù)。若令矩陣F的行向量Fi.,Fj.分別對(duì)應(yīng)用戶節(jié)點(diǎn) Ui,Uj的社區(qū)指示向量，該正則化項(xiàng)刻畫了用戶子集社區(qū)劃分的平滑程度。

由矩陣的兩個(gè)性質(zhì)：tr（A B ）= tr（B A ）和tr（A）= t r（AT） ，式（3）可以進(jìn)一步轉(zhuǎn)換為

其中， LF= DF-WF表示用戶子集 NU的拉普拉斯矩陣，其標(biāo)準(zhǔn)化拉普拉斯矩陣為 LF=I-WF。 DF表示用戶節(jié)點(diǎn)度的對(duì)角矩陣，即

定義 2 定義目標(biāo)子集 NO關(guān)于k-近鄰圖的權(quán)重矩陣WG為

其中， N （ Oi） 為目標(biāo)節(jié)點(diǎn) Oi的k-最近鄰集合。

同理，當(dāng)高維空間中距離較近的向量 Xi.,Xj.映射到對(duì)應(yīng)的低維流形上 G.i,G.j時(shí)，距離依然較小，從而定義基于目標(biāo)子空間的正則化項(xiàng)為

類似地， LG= DG-WG表示目標(biāo)子集 NO的拉普拉斯矩陣，其標(biāo)準(zhǔn)化拉普拉斯矩陣為 LG=I -WG。 DG是用戶節(jié)點(diǎn)度的對(duì)角矩陣，即 DG（j, j） =∑ixij。若令矩陣G的行向量 G.i,G.j分別對(duì)應(yīng)用戶節(jié)點(diǎn) Oi,Oj的社區(qū)指示向量，該正則化項(xiàng)刻畫了目標(biāo)子集社區(qū)劃分的平滑程度。需要指出的是，通過增加圖正則化項(xiàng)，能夠?qū)?shù)據(jù)內(nèi)在的結(jié)構(gòu)特征作為約束信息引入到非負(fù)矩陣分解模型中，以優(yōu)化二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)。

3.2 一種基于圖正則化的三重非負(fù)矩陣分解算法

在三重非負(fù)矩陣分解模型中，引入二模節(jié)點(diǎn)的雙重正則化約束，從而將式（1）轉(zhuǎn)化為約束優(yōu)化求解問題，目標(biāo)函數(shù)定義為其中，α≥0,β≥0表示正則化約束系數(shù)，用于平衡第2正則項(xiàng)和第3正則項(xiàng)在目標(biāo)函數(shù)中的權(quán)重。當(dāng)α= 0 時(shí)，該模型（式（7））轉(zhuǎn)化為單一的圖正則非負(fù)矩陣分解模型[14]；而當(dāng) α =β=0時(shí)，則該模型（式（7））轉(zhuǎn)化為一般的非負(fù)矩陣分解模型（式（1））。

將定理 1 應(yīng)用到目標(biāo)函數(shù)（式（5）-式（7））中，其中的正則約束項(xiàng)可分別改寫為

由此，F(xiàn)-NMTF的目標(biāo)函數(shù)可轉(zhuǎn)化為最小化問題：

其中， BF和 BG分別源自標(biāo)準(zhǔn)化拉普拉斯矩陣 LF,LG。式（10）給出了基于圖正則化的 NMTF聯(lián)合聚類模型。該模型基于用戶子空間和目標(biāo)子空間的流形結(jié)構(gòu)，構(gòu)建二者的k-近鄰圖的權(quán)重矩陣添加到目標(biāo)函數(shù)中作為正則化項(xiàng)。由此，F(xiàn)-NMTF成功引入了異質(zhì)節(jié)點(diǎn)的類內(nèi)信息以輔助并改善二分網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。

3.3 算法優(yōu)化

由于NMTF模型是關(guān)于3個(gè)因子矩陣F,S和G的非凸函數(shù)，難以直接獲取其全局最優(yōu)解。因此，本節(jié)提出了一種乘性交替迭代算法，即每次迭代都固定兩個(gè)因子矩陣為最新值，求解剩下的因子矩陣。于是，NMTF模型轉(zhuǎn)化為關(guān)于單一變量的凸優(yōu)化問題。通過交替地迭代更新，從而得到問題的穩(wěn)定點(diǎn)或局部極值點(diǎn)。不同于 NMF分解中引入拉格朗日乘子進(jìn)行矩陣乘性迭代的一般思路，F(xiàn)-NMTF算法對(duì)最小化子問題進(jìn)行奇異值分解以期進(jìn)一步簡(jiǎn)化。優(yōu)化后的迭代算法主要運(yùn)用矩陣向量進(jìn)行乘法運(yùn)算，使得在每步迭代中求解因子矩陣較為簡(jiǎn)便，從而加速算法收斂。

定理2 定義一個(gè)優(yōu)化問題為

令H = ATB，且其奇異值分解（Singular Value Decomposition, SVD）為 H =UΛ VT。當(dāng)矩陣A和B確定時(shí)，矩陣Q的最優(yōu)解為 Q = UVT。

證明 根據(jù)矩陣的跡性質(zhì)：tr（A B ） = tr（B A ） 和tr（A） = tr（AT），當(dāng)矩陣B確定時(shí)，min B - AQ2等同于tr（QTH ）。通過奇異值分解，得到 t r（QTH）=tr（Q U Λ VT）=tr（ΛVTQU ） = t r（Λ Z ）=，其中λii和zii分別表示Λ和Z對(duì)應(yīng)的矩陣元素。

令Z =VTQU為正交矩陣，即 ZTZ =I,zii≤ 1 , λii≥ 0 是矩陣H的奇異值。由此，進(jìn)一步得到 t r（QTH ） = ∑iλiizii≤ ∑iλii。 當(dāng) Z =I時(shí)，tr（QTH）獲得其最大值，由此說明Q = UZTVT=UVT是優(yōu)化問題min B - AQ2的最優(yōu)解，則定理2得證。

根據(jù)定理 2, F-NMTF優(yōu)化問題可以有效地分解為兩個(gè)關(guān)于較小規(guī)模矩陣的子問題，涉及到的矩陣乘法運(yùn)算也會(huì)相應(yīng)減少。因此，該方法更應(yīng)用于大規(guī)模的真實(shí)異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)。這里首先確定因子矩陣F和G，對(duì)式（10）求偏導(dǎo)以求解S：

確定S后，將目標(biāo)函數(shù)（式10）的第2和第3正則項(xiàng)分解為兩個(gè)子問題

FF

下面對(duì)兩個(gè)子問題交替迭代求其最小解，這里分別求出每一個(gè)參數(shù)的偏導(dǎo)數(shù)，然后對(duì)偏導(dǎo)數(shù)求解以更新參數(shù)。對(duì)于子問題1，這里確定矩陣F,S和QG以迭代更新剩余變量G。令 YG=FS, ZG=BGQG，則原目標(biāo)函數(shù)被簡(jiǎn)化為其中，（ZG）i.表示矩陣 ZG的第i個(gè)行向量。

由于分解因子G為目標(biāo)節(jié)點(diǎn)子空間的社區(qū)指示矩陣，假定 Gi.表示目標(biāo)節(jié)點(diǎn) Oi的社區(qū)指示向量，則對(duì)簡(jiǎn)化后的目標(biāo)函數(shù)求偏導(dǎo)，選擇與其具有最小近似誤差的社區(qū)j作為該節(jié)點(diǎn)的歸屬社區(qū)，從而將 Gij設(shè)置為1，同一行的其他元素設(shè)置為0，得到分解后的矩陣G為

其中，argmink（X.i- （YG）.k2-2α（ZG）ik）返回社區(qū)集合中與目標(biāo)節(jié)點(diǎn) Oi有最小近似誤差的社區(qū)標(biāo)號(hào)。

對(duì)于子問題 2，確定矩陣G,S和 QF以迭代更新剩余變量F。令YF=SGT,ZF=BFQF，則原目標(biāo)函數(shù)被簡(jiǎn)化為其中，（ZF）.j表示矩陣 ZF的第j個(gè)列向量。

類似地，由于分解因子F為用戶節(jié)點(diǎn)子空間的社區(qū)指示矩陣，假定 Fj.表示用戶節(jié)點(diǎn) Uj的社區(qū)指示向量，則對(duì)簡(jiǎn)化后的目標(biāo)函數(shù)求偏導(dǎo)，選擇與其具有最小近似誤差的社區(qū)i作為該節(jié)點(diǎn)的歸屬社區(qū)，從而將 Fji設(shè)置為 1，同一行的其他元素設(shè)置為 0，得到分解后的矩陣F為

其中，argmink（Xj.- （YF）k.2-2β（ZF）jk） 返回社區(qū)集合中與用戶節(jié)點(diǎn) Uj有最小近似誤差的社區(qū)標(biāo)號(hào)。

重復(fù)迭代上述的矩陣分解過程，并不斷更新因子矩陣F,S和G，直至目標(biāo)函數(shù)值趨于收斂或達(dá)到最大迭代次數(shù)。迭代結(jié)束后，最終得到的矩陣F和G分別對(duì)應(yīng)對(duì)用戶子空間和目標(biāo)子空間的社區(qū)劃分，二者共同決定二分網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。其中，列向量 F.i與行向量 Gi.對(duì)應(yīng)第i個(gè)網(wǎng)絡(luò)社區(qū)。對(duì)于 Fij=1，則說明用戶節(jié)點(diǎn) Ui隸屬于社區(qū)j；對(duì)于 Gij=1，則說明用戶節(jié)點(diǎn) Oj隸屬于社區(qū)i。對(duì)因子矩陣F,G的元素進(jìn)行 0,1賦值，由此可以直接推導(dǎo)二分網(wǎng)絡(luò)中異質(zhì)節(jié)點(diǎn)的社區(qū)歸屬。

基于三重非負(fù)矩陣分解的 F-NMTF算法開銷主要包括計(jì)算目標(biāo)函數(shù)J和因子矩陣分解迭代。算法每次迭代需要同步更新 3個(gè)不同規(guī)模的因子矩陣：基矩陣F∈?m×r，光滑因子矩陣S ∈ ?r×r和系數(shù)矩陣G ∈ ?n×r。由于 r ? （m, n），其迭代求解的計(jì)算復(fù)雜度為 O （ tr m n），則F-NMTF的算法復(fù)雜度為O（ tr m n）, t為算法迭代次數(shù)。優(yōu)化后的迭代算法對(duì)因子矩陣F,G的元素進(jìn)行0,1賦值，并主要基于向量進(jìn)行矩陣分解運(yùn)算，從而簡(jiǎn)化了每步迭代求解，使其能夠適用于較大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)。

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)同時(shí)基于計(jì)算機(jī)生成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)進(jìn)行測(cè)試，并采用不同的指標(biāo)來評(píng)估二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的性能。由于計(jì)算機(jī)生成網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)已知，采用經(jīng)典標(biāo)準(zhǔn)互信息（Normalized Mutual Information, NMI）和運(yùn)行時(shí)間作為衡量標(biāo)準(zhǔn)。對(duì)于未知結(jié)構(gòu)的真實(shí)網(wǎng)絡(luò)，則采用二分模塊度（bipartite modularity）和運(yùn)行時(shí)間。需要指出的是，二分模塊度是文獻(xiàn)[4]中擴(kuò)展自模塊度的指標(biāo)，專門應(yīng)用于衡量二分網(wǎng)絡(luò)的社區(qū)劃分質(zhì)量，并被大量相關(guān)工作中所采納接受。為全面分析比較二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的性能，實(shí)驗(yàn)選取Guimera[7], NMF[15], GNMF[14]和BNMTF[16]4種典型算法作與F-NMTF算法進(jìn)行對(duì)比。其中，Guimera是關(guān)于二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的基準(zhǔn)算法，NMF, GNMF與BNMTF則是近年來提出的基于NMF的社區(qū)發(fā)現(xiàn)方法。

對(duì)于 NMF方法（NMF, GNMF, BNMTF和F-NMTF），根據(jù)文獻(xiàn)[17]設(shè)置最大近鄰數(shù)k為{1,2,,…10}，正則化系數(shù)α和β為0.1。此外，根據(jù)文獻(xiàn)[11]提供的方法計(jì)算網(wǎng)絡(luò)社區(qū)數(shù)目，該方法已被證明能夠較為準(zhǔn)確地預(yù)測(cè)網(wǎng)絡(luò)社區(qū)的數(shù)量。每個(gè)方法在所有網(wǎng)絡(luò)數(shù)據(jù)上重復(fù)實(shí)驗(yàn)50次，并計(jì)算度量指標(biāo)的均值。

4.1 計(jì)算機(jī)生成網(wǎng)絡(luò)

計(jì)算機(jī)生成網(wǎng)絡(luò)采用文獻(xiàn)[7]提出的二分網(wǎng)絡(luò)基準(zhǔn)生成模型。該模型可以靈活設(shè)置各項(xiàng)網(wǎng)絡(luò)參數(shù)，以生成較高質(zhì)量的二分網(wǎng)絡(luò)標(biāo)準(zhǔn)數(shù)據(jù)集。一般來說，社區(qū)內(nèi)連接概率值inρ越高，則說明二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越強(qiáng)；反之，隨著outin/ρρ的遞增，二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)逐步趨于模糊，社區(qū)發(fā)現(xiàn)也就越困難。通過設(shè)置參數(shù)inρ和outρ控制二分網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的強(qiáng)弱程度，從而有效地驗(yàn)證不同算法的社區(qū)發(fā)現(xiàn)的性能。實(shí)驗(yàn)中生成9組網(wǎng)絡(luò)測(cè)試數(shù)據(jù)集，每組包含10個(gè)同樣配置的二分網(wǎng)絡(luò)，outin/ρρ間隔為0.1，具體配置如表1所示。

由于計(jì)算機(jī)生成網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)已知，實(shí)驗(yàn)從 9組測(cè)試數(shù)據(jù)集中每組隨機(jī)抽取5個(gè)網(wǎng)絡(luò)，分別計(jì)算各種算法在不同測(cè)試數(shù)據(jù)集下的指標(biāo)均值。如圖2（a）所示，當(dāng)ρout/ρin逐步遞增，所有算法的運(yùn)行時(shí)間急劇上升，不同算法間的運(yùn)行時(shí)間差也逐步擴(kuò)大。這是因?yàn)槎志W(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)較弱時(shí)，導(dǎo)致社區(qū)發(fā)現(xiàn)困難程度較大，需要反復(fù)迭代使得矩陣分解消耗大量的運(yùn)行時(shí)間。由于Guimera算法不同于NMF類算法，基于最大化模塊度進(jìn)行貪婪聚類，因而試驗(yàn)中針對(duì)性地比較NMF類4種算法的運(yùn)行時(shí)間。而在NMF類算法中，F(xiàn)-NMTF運(yùn)行時(shí)間短，收斂速度較快；且隨著二分網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的弱化，其快速收斂的優(yōu)勢(shì)也逐步擴(kuò)大。說明F-NMTF計(jì)算復(fù)雜度低，相比其它 NMF算法具有更好的收斂性和適應(yīng)性。

表1 網(wǎng)絡(luò)配置參數(shù)

圖2（b）給出了5種算法在計(jì)算機(jī)生成網(wǎng)絡(luò)下社區(qū)發(fā)現(xiàn)的NMI均值。當(dāng) ρout/ρin≤ 0 .4時(shí)，二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)較為明顯，5種算法都表現(xiàn)出良好的社區(qū)發(fā)現(xiàn)性能，NMI均值都大于 0.8。其中 Kmeans社區(qū)發(fā)現(xiàn)的準(zhǔn)確率略差。但當(dāng) ρout/ ρin≥ 0 .5時(shí)，二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)趨于模糊，使得社區(qū)發(fā)現(xiàn)準(zhǔn)確性下降，5種算法的NMI值均呈現(xiàn)下降趨勢(shì)，社區(qū)發(fā)現(xiàn)的精確度急劇下降。其中，F(xiàn)-NMTF仍保持了相對(duì)較高的NMI值，F(xiàn)-NMTF的NMI均值比NMF提升了5.83%，相比GNMF算法則提升了3.13%。這說明 F-NMTF算法對(duì)二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的準(zhǔn)確率較優(yōu)且維持在較高水平，能夠發(fā)現(xiàn)更接近于標(biāo)準(zhǔn)二分網(wǎng)絡(luò)的真實(shí)社區(qū)結(jié)構(gòu)。

4.2 真實(shí)網(wǎng)絡(luò)

真實(shí)網(wǎng)絡(luò)相比計(jì)算機(jī)生成網(wǎng)絡(luò)更不規(guī)則，因而其社區(qū)結(jié)構(gòu)往往也更加復(fù)雜。這里采用5個(gè)具有不同規(guī)模的真實(shí)二分網(wǎng)絡(luò)數(shù)據(jù)集：南方婦女網(wǎng)絡(luò)（Southwomen）[18]、蘇格蘭公司網(wǎng)絡(luò)（Scotland）[19]、論壇話題網(wǎng)絡(luò)（Irvine forum）[20]、電影評(píng)分網(wǎng)絡(luò)（Movielens）[21]、2004年凝固態(tài)物理引文網(wǎng)絡(luò)（Condmat）[22]來進(jìn)一步測(cè)試算法性能，表2描述了這些真實(shí)網(wǎng)絡(luò)的基本屬性。這里根據(jù)文獻(xiàn)[11]提供的方法預(yù)估真實(shí)網(wǎng)絡(luò)數(shù)據(jù)中的社區(qū)數(shù)目r，同時(shí)也就確定了NMF算法中因子矩陣的維數(shù)。

表2 實(shí)驗(yàn)中真實(shí)網(wǎng)絡(luò)的基本屬性

由于真實(shí)二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)未知，這里采用運(yùn)行時(shí)間和二分模塊度來衡量不同算法社區(qū)劃分質(zhì)量的優(yōu)劣，以此作為對(duì)計(jì)算機(jī)生成網(wǎng)絡(luò)實(shí)驗(yàn)的補(bǔ)充和佐證。如表3所示，NMF方法的時(shí)間復(fù)雜度明顯要高于Guimera算法。在NMF算法中，F(xiàn)-NMTF算法的運(yùn)行時(shí)間最接近于Guimera算法，這說明該算法有效地加快了非負(fù)矩陣分解的收斂速度，相比同類算法消耗了最少的運(yùn)行時(shí)間。但由于網(wǎng)絡(luò)規(guī)模不同，F(xiàn)-NMTF在不同二分網(wǎng)絡(luò)下社區(qū)發(fā)現(xiàn)的時(shí)間增益也呈現(xiàn)出較大差別。對(duì)于較大規(guī)模的二分網(wǎng)絡(luò)，F(xiàn)-NMTF時(shí)間復(fù)雜度較低的優(yōu)勢(shì)更為明顯。

表4給出了5種算法社區(qū)發(fā)現(xiàn)的二分模塊度BQ值，準(zhǔn)確的網(wǎng)絡(luò)社區(qū)劃分對(duì)應(yīng)于較大的BQ 值。由于網(wǎng)絡(luò)結(jié)構(gòu)不同，使得二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的BQ 值也處于不同的水平。Guimera是基于二分模塊度最大化的社區(qū)發(fā)現(xiàn)算法，與NMF算法相比，其BQ 值較優(yōu)；但作為模塊度優(yōu)化的方法存在分辨極限（resolution limit）等問題。比較5種NMF算法發(fā)現(xiàn)：F-NMTF在 5種真實(shí)二分網(wǎng)絡(luò)上獲得了較大的二分模塊度QB，說明該算法的社區(qū)發(fā)現(xiàn)質(zhì)量最優(yōu)。對(duì)于南方婦女網(wǎng)絡(luò)，蘇格蘭公司網(wǎng)絡(luò)，論壇話題網(wǎng)絡(luò)3個(gè)具有較弱社區(qū)結(jié)構(gòu)的二分網(wǎng)絡(luò)，F(xiàn)-NMTF算法對(duì)于社區(qū)發(fā)現(xiàn)準(zhǔn)確率的改善幅度較小。對(duì)于電影評(píng)分網(wǎng)絡(luò)，凝固態(tài)物理引文網(wǎng)絡(luò)具有較強(qiáng)社區(qū)結(jié)構(gòu)的二分網(wǎng)絡(luò)，F(xiàn)-NMTF算法的社區(qū)發(fā)現(xiàn)準(zhǔn)確率改善幅度較大。對(duì)比NMF, BNMTF算法，F(xiàn)-NMTF的BQ 值在前3個(gè)真實(shí)網(wǎng)絡(luò)上平均增幅分別為0.057和0.011；在后兩個(gè)真實(shí)網(wǎng)絡(luò)上，F(xiàn)-NMTF的BQ 值平均增幅分別為0.036和0.015。

圖2 社區(qū)發(fā)現(xiàn)算法在計(jì)算機(jī)生成網(wǎng)絡(luò)上的性能對(duì)比

表3 真實(shí)網(wǎng)絡(luò)中5種算法社區(qū)發(fā)現(xiàn)的運(yùn)行時(shí)間

表4 真實(shí)網(wǎng)絡(luò)中5種算法社區(qū)發(fā)現(xiàn)的二分模塊度

綜合 F-NMTF算法在計(jì)算機(jī)生成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中的表現(xiàn)，可以得出結(jié)論：相比 Guimera，GNMF等算法，通過圖正則化引入類內(nèi)信息的F-NMT算法更適合具有特殊二分結(jié)構(gòu)的二分網(wǎng)絡(luò)，從而挖掘得到更真實(shí)有效的社區(qū)結(jié)構(gòu)。

5 結(jié)束語(yǔ)

本文提出了一種基于圖正則化的三重非負(fù)矩陣分解算法應(yīng)用于二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，該方法通過分別構(gòu)建兩類異質(zhì)節(jié)點(diǎn)的 k-近鄰圖來估計(jì)用戶子空間和目標(biāo)子空間的結(jié)構(gòu)特征，將其作為正則化約束項(xiàng)添加到F-NMTF目標(biāo)函數(shù)中，從而同時(shí)引入了類間信息與類內(nèi)信息，以增強(qiáng)非負(fù)矩陣分解的正交性和收斂性；同時(shí)將NMTF模型分解為兩個(gè)關(guān)于交替求解最小化函數(shù)的子問題，簡(jiǎn)化矩陣分解迭代以加快收斂，從而改善 NMF方法時(shí)間復(fù)雜度高等問題。實(shí)驗(yàn)和分析證明：對(duì)于計(jì)算機(jī)生成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)，F(xiàn)-NMTF的社區(qū)劃分方案均表現(xiàn)出有較高的準(zhǔn)確率和穩(wěn)定性，能夠準(zhǔn)確有效地挖掘二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。同時(shí)，如何將非負(fù)矩陣分解進(jìn)一步應(yīng)用于擴(kuò)展到多?；蚨嚓P(guān)系異質(zhì)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，并保證復(fù)雜網(wǎng)絡(luò)環(huán)境下社區(qū)劃分的合理性和有效性，將是下一步工作的研究重點(diǎn)。

[1] 全佳妮. 基于二分網(wǎng)絡(luò)的協(xié)同推薦研究[D]. [碩士論文], 蘇州大學(xué), 2012.Quan Jia-ni. Research on collaborative recommendation based on bipartite network[D]. [Master dissertation], Suzhou University, 2012.

[2] 熊湘云. 基于二分網(wǎng)絡(luò)的多維度推薦技術(shù)研究[D]. [碩士論文],蘇州大學(xué), 2013.Xiong Xiang-yun. Research on multi-dimensional recommendation based on bipartite network[D]. [Master dissertation], Suzhou University, 2013.

[3] Liu X and Murata T. How does label propagation algorithm work in bipartite networks[C]. Proceedings of the IEEE International Joint Conference on Web Intelligence and Intelligent Agent Technology, Milano, Italy, 2009: 5-8.

[4] Barber M J. Modularity and community detection in bipartite networks[J]. Physical Review E, 2007, 76（6）: 066102.

[5] Murata T. Detecting communities from bipartite networks based on bipartite modularities[C]. Proceedings of the Computational Science and Engineering, Vancouver, Canada,2009, 4: 50-57.

[6] Suzuki K and Wakita K. Extracting multi-facet community structure from bipartite networks[C]. Proceedings of the Computational Science and Engineering, Vancouver, Canada,2009, 4: 312-319.

[7] Roger Guimera, Marta Sales Pardo, Luis A, et al.. Module identification in bipartite and directed networks[J]. Physical Review E, 2007, 76（3）: 036102.

[8] Tang L, Wang X, and Liu H. Community detection via heterogeneous interaction analysis[J]. Data Mining and Knowledge Discovery, 2012, 25（1）: 1-33.

[9] Sun Y, Tang J, Han J, et al.. Community evolution detection in dynamic heterogeneous information networks[C].Proceedings of the 8th Workshop on Mining and Learning with Graphs, Washington DC, USA, 2010: 137-146.

[10] Wang H, Nie F, Huang H, et al.. Nonnegative matrix trifactorization based high-order co-clustering and its fast implementation[C]. Proceedings of 11th International Conference on Data Mining, Vancouver, Canada, 2011:774-783.

[11] Nguyen N P, Dinh T N, Tokala S, et al.. Overlapping communities in dynamic networks: their detection and mobile applications[C]. Proceedings of the 17th Annual International Conference on Mobile Computing and Networking, Las Vegas,USA, 2011: 85-96.

[12] Zhang Z Y, Wang Y, and Ahn Y Y. Overlapping community detection in complex networks using symmetric binary matrix factorization[J]. Physical Review E, 2013, 87（6）:062803.

[13] Li Ping, Bu Jia-jun, Chen Chun, et al.. Relational multimanifold coclustering[J]. IEEE Transactions on Cybernetics, 2013, 43（6）: 1871-1881.

[14] Cai D, He X, Han J, et al.. Graph regularization non-negative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2011, 33（8）: 1548-1560.

[15] Wang F, Li T, Wang X, et al.. Community discovery using nonnegative matrix factorization[J]. Data Mining and Knowledge Discovery, 2011, 22（3）: 493-521.

[16] Zhang Yu and Yeung Dit-Yan. Overlapping community detection via bounded nonnegative matrix tri-factorization[C]. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Beijing, China, 2012: 606-614.

[17] Shang Fan-hua, Jiao L C, and Wang Fei. Graph dual regularization non-negative matrix factorization for coclustering[J]. Pattern Recognition, 2012, 45（6）: 2237-2250.

[18] Southwomen network. http://konect.uni-koblenz.de/networks/Southwomen[OL]. 1930.

[19] Scott J and Hughes M. The Anatomy of Scottish Capital:Scottish Companies and Scottish Capital[M]. London: Croom Helm, 1980: 291.

[20] Opsahl T. Triadic closure in two-mode networks: redefining the global and local clustering coefficients[J]. Social Networks,2013, 35（2）: 159-167.

[21] MovieLens network. http://konect.uni-koblenz.de/networks/movielens-100k_rating[OL]. 2009.

[22] Arxiv cond-mat network. http://konect.uni-koblenz.De/networks/opsahl-collaboration[OL]. 2004.