劉家驥，包崇明，周麗華，王崇云，孔 兵

1.云南大學(xué) 信息學(xué)院，昆明 650091

2.云南大學(xué) 軟件學(xué)院，昆明 650091

3.云南大學(xué) 生態(tài)學(xué)與環(huán)境學(xué)院，昆明 650091

1 引言

現(xiàn)實(shí)世界中，許多復(fù)雜的系統(tǒng)都可以抽象成網(wǎng)絡(luò)的形式，對(duì)于復(fù)雜網(wǎng)絡(luò)的研究能夠加深對(duì)于不同系統(tǒng)性質(zhì)的了解。目前，針對(duì)同質(zhì)節(jié)點(diǎn)網(wǎng)絡(luò)有比較深入的研究，如社區(qū)發(fā)現(xiàn)[1]、影響最大化[2]和網(wǎng)絡(luò)傳播[3]等。然而，現(xiàn)實(shí)世界網(wǎng)絡(luò)往往由多種不同類型的異質(zhì)節(jié)點(diǎn)構(gòu)成，異質(zhì)節(jié)點(diǎn)間的交互往往代表不同的連接關(guān)系。在實(shí)際網(wǎng)絡(luò)中，多種類型的節(jié)點(diǎn)由多種類型的鏈路連接，從而形成異質(zhì)信息網(wǎng)絡(luò)（Heterogeneous Information Networks，HIN）[4]。例如，從論文合作網(wǎng)絡(luò)[5]中提取的數(shù)據(jù)包含作者、論文、關(guān)鍵詞和會(huì)議等多類型對(duì)象。這些不同類型的對(duì)象之間形成了不同類型的連接關(guān)系。

異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)挖掘的關(guān)鍵研究問題之一是社區(qū)發(fā)現(xiàn)[1]（community detection）。社區(qū)發(fā)現(xiàn)即根據(jù)網(wǎng)絡(luò)包含的鏈接、內(nèi)容等大量屬性信息，對(duì)網(wǎng)絡(luò)中具有共同屬性的潛在結(jié)構(gòu)進(jìn)行挖掘。挖掘異質(zhì)網(wǎng)絡(luò)中有用的、具有穩(wěn)定性的社區(qū)，同樣具有重要的研究價(jià)值。同質(zhì)網(wǎng)絡(luò)[6]將社區(qū)定義為：網(wǎng)絡(luò)中具有某種相似特性的節(jié)點(diǎn)集合，社區(qū)內(nèi)部節(jié)點(diǎn)聯(lián)系緊密而社區(qū)間聯(lián)系相對(duì)稀疏。推廣到異質(zhì)網(wǎng)絡(luò)，可以認(rèn)為：社區(qū)內(nèi)部各種相同或不同類型節(jié)點(diǎn)間的連接緊密，而社區(qū)間的各種相同或不同類型節(jié)點(diǎn)間的連接則比較稀疏。但在異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中，異質(zhì)網(wǎng)絡(luò)中的異構(gòu)性導(dǎo)致以下兩個(gè)問題[7]：（1）異質(zhì)網(wǎng)絡(luò)中互動(dòng)噪聲很多，引起算法的性能降低。網(wǎng)絡(luò)中節(jié)點(diǎn)的屬性可以看作是連接到節(jié)點(diǎn)的所有邊相互作用和疊加的結(jié)果，一些不重要的信息往往能夠給聚類帶來很大影響，這就是異質(zhì)網(wǎng)絡(luò)中大量存在的噪音。（2）各個(gè)異質(zhì)節(jié)點(diǎn)關(guān)系錯(cuò)綜復(fù)雜，難以在同一維度中有效整合網(wǎng)絡(luò)中的異質(zhì)信息，挖掘出符合實(shí)際的社區(qū)結(jié)構(gòu)。將多維的異質(zhì)網(wǎng)絡(luò)轉(zhuǎn)換成同質(zhì)網(wǎng)絡(luò)是當(dāng)前針對(duì)異質(zhì)網(wǎng)絡(luò)聚類的主流方法，但是在降維的過程中如何最大限度保留異質(zhì)信息以及在同一維度有效整合異質(zhì)信息，是當(dāng)前所面臨的一大挑戰(zhàn)。

針對(duì)異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)存在的難點(diǎn)，研究人員進(jìn)行了很多嘗試。主題模型是對(duì)網(wǎng)絡(luò)中蘊(yùn)藏的語義信息進(jìn)行統(tǒng)一建模的方法，代表性的有潛在語義分析（LSA）[8]、概率潛在語義分析（PLSA）[9]和潛在狄利克雷分配（LDA）[10]等模型，它們能夠有效地對(duì)異質(zhì)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)進(jìn)行挖掘。Deng等人[11]提出TMGP算法，將異質(zhì)網(wǎng)絡(luò)中的不同節(jié)點(diǎn)信息集成到主題模型中，初步完成對(duì)社區(qū)的有效劃分，不過多數(shù)的主題模型，都僅僅單純地利用了文本集中的語義信息，而語義信息在一定程度上并不能很好地代表社區(qū)結(jié)構(gòu)的特征，且必須滿足異質(zhì)節(jié)點(diǎn)相互獨(dú)立的條件，有一定的局限性。

最近研究發(fā)現(xiàn)，將排序算法和聚類算法組合到一起，能產(chǎn)生一定的“化學(xué)反應(yīng)”，從而達(dá)到令人較為滿意的研究結(jié)果。RankClus[12]是基于排序的經(jīng)典聚類方法，先對(duì)目標(biāo)對(duì)象進(jìn)行排序，由排序結(jié)果決定聚類對(duì)象向量，通過迭代對(duì)目標(biāo)對(duì)象類別進(jìn)行調(diào)整，可以得到較為準(zhǔn)確的聚類效果?；谂判蚝途垲愊嘟Y(jié)合的方法雖然充分考慮了異質(zhì)鏈接關(guān)系的信息，但是都沒有考慮同類型節(jié)點(diǎn)之間的交互關(guān)系。

異質(zhì)網(wǎng)絡(luò)中節(jié)點(diǎn)復(fù)雜多樣，呈高維態(tài)勢，因此通過降維完成異質(zhì)網(wǎng)絡(luò)到同質(zhì)網(wǎng)絡(luò)或者二分網(wǎng)絡(luò)的轉(zhuǎn)換也是目前一種常用而有效的方法。常用的降維方法包括主成分分析（PCA）[13]、線性降維分析（LDA）[14]、非負(fù)矩陣分解（NMF）[15]等。當(dāng)前大部分相關(guān)算法并不能很好地去除異質(zhì)節(jié)點(diǎn)之間噪聲，在網(wǎng)絡(luò)轉(zhuǎn)化過程中會(huì)丟失大量網(wǎng)絡(luò)信息，同時(shí)無法在同一維度對(duì)網(wǎng)絡(luò)信息進(jìn)行有效整合[16]。而非負(fù)矩陣分解已經(jīng)被證明了能夠很好地保持網(wǎng)絡(luò)原始信息，且方法簡單明了、解釋性強(qiáng)、效率高。如何將NMF 應(yīng)用于異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，是本文研究的重點(diǎn)。

本文以異質(zhì)網(wǎng)絡(luò)中的星型網(wǎng)絡(luò)作為研究對(duì)象，提出了一種融合各個(gè)子網(wǎng)絡(luò)異構(gòu)信息和各個(gè)子網(wǎng)絡(luò)內(nèi)部拓?fù)湫畔⒌穆?lián)合優(yōu)化算法，即基于圖正則化非負(fù)矩陣分解的異質(zhì)網(wǎng)社區(qū)發(fā)現(xiàn)方法。為了將異質(zhì)信息在同一維度進(jìn)行有效整合，該算法首先對(duì)反映了不同子網(wǎng)絡(luò)共有潛在結(jié)構(gòu)的共識(shí)矩陣進(jìn)行學(xué)習(xí)，使用共識(shí)矩陣中每個(gè)行向量作為中心類型節(jié)點(diǎn)在每個(gè)社區(qū)當(dāng)中的隸屬度分布，通過不斷迭代優(yōu)化系數(shù)矩陣和共識(shí)矩陣，對(duì)兩個(gè)反映不同類型節(jié)點(diǎn)的子空間進(jìn)行優(yōu)化，在降維過程中也較大限度地保留了異質(zhì)信息的完整性。同時(shí)，在考慮了不同子網(wǎng)絡(luò)之間異質(zhì)關(guān)系的基礎(chǔ)上，算法結(jié)合多重子空間的流形約束，利用圖正則化，將中心類型子空間和屬性類型子空間的連接關(guān)系（即各個(gè)子網(wǎng)絡(luò)內(nèi)蘊(yùn)的拓?fù)浣Y(jié)構(gòu)信息）作為約束項(xiàng)，引入到正則化聯(lián)合優(yōu)化算法之中。通過優(yōu)化法則不斷迭代系數(shù)矩陣，找到高維數(shù)據(jù)在低維空間的緊致嵌入，成功消除了異質(zhì)節(jié)點(diǎn)之間的部分噪聲。

2 算法思想

非負(fù)矩陣分解（NMF）算法具有簡便、可解釋性強(qiáng)和存儲(chǔ)空間少等優(yōu)點(diǎn)，能夠在降維過程中較好地保持信息的完整性。在對(duì)異質(zhì)網(wǎng)絡(luò)進(jìn)行聚類時(shí)，它最關(guān)鍵的作用是能夠有效地揭示異質(zhì)網(wǎng)絡(luò)中多維數(shù)據(jù)潛在的結(jié)構(gòu)特征[17-18]。同時(shí)，由于NMF算法中分解得到的矩陣元素都必須滿足非負(fù)條件，因此該模型幾乎滿足了所有現(xiàn)實(shí)數(shù)據(jù)的物理屬性，可解釋性強(qiáng)。與大多數(shù)最先進(jìn)的無監(jiān)督算法相比，NMF 顯然擁有更加具有競爭力的性能。然而，當(dāng)前鮮有將NMF運(yùn)用于異質(zhì)網(wǎng)絡(luò)聚類的算法，因?yàn)橹苯訉MF 應(yīng)用于異質(zhì)網(wǎng)絡(luò)聚類，需要向其分解因子矩陣U和V同時(shí)施加非負(fù)正交的約束，約束太強(qiáng)會(huì)使矩陣分解的逼近程度大大降低，從而限制了異質(zhì)網(wǎng)絡(luò)的聚類性能。另一方面，當(dāng)前算法無法有效解決去噪問題，也難以在同一維度整合異質(zhì)信息。本文提出的HINGMF算法，優(yōu)勢主要有以下幾個(gè)方面：（1）在非負(fù)矩陣分解中，通過引入共識(shí)矩陣V*，找到不同類型節(jié)點(diǎn)之間有意義且具有可比性的因式分解，從而充分利用了異質(zhì)信息，讓其在同一維度得到有效整合；（2）通過圖正則化，將中心類型子空間和屬性類型子空間的內(nèi)部連接關(guān)系作為約束項(xiàng)引入非負(fù)矩陣分解，結(jié)合多重子空間的流形約束，有效利用子網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，達(dá)到去噪效果。

在實(shí)際生活中，許多的網(wǎng)絡(luò)都有一類中心節(jié)點(diǎn)，所有的屬性節(jié)點(diǎn)都通過中心節(jié)點(diǎn)相連接。在異質(zhì)網(wǎng)絡(luò)中，存在著大量的星型結(jié)構(gòu)網(wǎng)絡(luò)[18]，多種類型的節(jié)點(diǎn)通過同一種中心類型節(jié)點(diǎn)聯(lián)系在一起。圖1 所示的論文發(fā)表網(wǎng)絡(luò)即為一種具有星型模式的網(wǎng)絡(luò)，由關(guān)于研究論文的多種信息組成。每篇論文由一組作者撰寫，使用一組關(guān)鍵字，并在會(huì)議中發(fā)布。這樣的書目網(wǎng)絡(luò)由四種類型的對(duì)象組成：作者、會(huì)議、關(guān)鍵字和論文。論文和作者之間存在“被撰寫”和“撰寫”之間的關(guān)系，論文和術(shù)語之間存在“包含”和“被包含”的關(guān)系，而論文和會(huì)議則存在“被發(fā)表”和“發(fā)表”的關(guān)系。從圖1 可看出，書目信息網(wǎng)絡(luò)呈星形網(wǎng)絡(luò)模式，其中論文屬于中心類型，并且所有其他通過論文鏈接的對(duì)象，都稱為屬性類型。在書目信息網(wǎng)絡(luò)中，存在三個(gè)子網(wǎng)絡(luò)，分別是：論文-會(huì)議網(wǎng)絡(luò)、論文-作者網(wǎng)絡(luò)、論文-會(huì)議網(wǎng)絡(luò)。

圖1 星型網(wǎng)絡(luò)模型

假設(shè)有一個(gè)由中心類型和T種屬性類型之間的二分網(wǎng)絡(luò)組成的異質(zhì)網(wǎng)絡(luò)，用{X(1),…,X(t),…,X(T)}表示所有子圖的鄰接矩陣，其中X(t)的每一列表示一個(gè)中心類型節(jié)點(diǎn)而每一行表示一個(gè)屬性類型節(jié)點(diǎn)。對(duì)于每一個(gè)子網(wǎng)絡(luò)X(t)∈RM(t)×N，希望找到滿足X(t)≈U(t)(V(t))T的低秩因式分解U(t)∈RM(t)×K和V(t)∈RN×K。在這里M(t)是屬性類型t的節(jié)點(diǎn)個(gè)數(shù)，N表示中心類型的節(jié)點(diǎn)個(gè)數(shù)，K代表希望發(fā)現(xiàn)的聚類個(gè)數(shù)。HINGMF 將通過U和V共同揭示異質(zhì)網(wǎng)絡(luò)中隱藏的社區(qū)結(jié)構(gòu)。

3 基于圖正則項(xiàng)非負(fù)矩陣分解的異質(zhì)網(wǎng)絡(luò)聚類方法

和NMF 算法類似，異質(zhì)網(wǎng)絡(luò)每個(gè)子網(wǎng)絡(luò)的目標(biāo)函數(shù)為：

||·||F即F范數(shù)，U(t)≥0,V(t)≥0 代表對(duì)矩陣中每個(gè)元素都非負(fù)的限制。但是，這種表述假設(shè)每個(gè)子網(wǎng)都是獨(dú)立的，并且無法以統(tǒng)一的方式對(duì)異質(zhì)網(wǎng)絡(luò)建模。通過將從子網(wǎng)絡(luò)中學(xué)到的系數(shù)矩陣V(t)與共識(shí)矩陣V*之間的差異結(jié)合起來，改變目標(biāo)函數(shù)為：

對(duì)角矩陣Q(t)定義如下：

在計(jì)算誤差之前，將V(t)乘以Q(t)，以確保從不同子網(wǎng)中學(xué)習(xí)的V(t)具有可比性，在這里||X(t)||1= 1。另外，使用α作為固定參數(shù)來調(diào)整V(t)和共識(shí)矩陣V*差異的權(quán)重，文獻(xiàn)[19]表明該參數(shù)不太敏感，因此在整個(gè)實(shí)驗(yàn)中將其設(shè)置為0.1。

文獻(xiàn)[20]表明，重視低維流形的幾何信息可以提高聚類質(zhì)量。根據(jù)流形假設(shè)[21]，異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)經(jīng)非負(fù)矩陣分解后，同類節(jié)點(diǎn)間的局部鄰域結(jié)構(gòu)在低維特征空間中能夠得以保持，則當(dāng)高維空間中距離較近的向量Xi·，Xj·映射到對(duì)應(yīng)的低維流形上Vi·，Vj·時(shí)，距離依然較小。從而定義基于用戶子空間的正則項(xiàng)（平滑度懲罰項(xiàng)）為：

tr(·)表示矩陣的跡，W表示正則項(xiàng)權(quán)重矩陣，而矩陣D是滿足稱為拉普拉斯矩陣。結(jié)合之前的模型得到了一個(gè)新的模型：

到目前為止，將整個(gè)異質(zhì)網(wǎng)絡(luò)的所有二分子網(wǎng)絡(luò)視為同等重要。考慮到不同子網(wǎng)絡(luò)的相對(duì)權(quán)重，通過將一組參數(shù)β(t)引入方程來開發(fā)自動(dòng)權(quán)重學(xué)習(xí)策略。采用以指數(shù)形式表示的相對(duì)權(quán)重的原因是為了避免完全有利于具有最小誤差的子網(wǎng)絡(luò)，目標(biāo)函數(shù)變?yōu)椋?/p>

RE(t)表示與屬性類型t相關(guān)的子網(wǎng)絡(luò)的重建誤差：

為了解決上述優(yōu)化問題，提出了一種迭代優(yōu)化算法，分為以下三個(gè)步驟：（1）初始化，（2）固定V*，更新U和V，（3）固定U和V，更新V*。迭代（2）和（3），直到公式（6）收斂。算法1總結(jié)了這個(gè)兩步過程。算法流程圖如圖2所示。

圖2 算法流程圖

3.1 初始化

基矩陣U(t)和系數(shù)矩陣V(t)的合理初始化在HGNMF算法的整體性能中起重要作用。文中使用各個(gè)子網(wǎng)絡(luò)中的幾何信息來初始化特定基矩陣和系數(shù)矩陣。為實(shí)現(xiàn)此目的，每個(gè)子網(wǎng)單獨(dú)進(jìn)行NMF聚類，單個(gè)子網(wǎng)絡(luò)的優(yōu)化問題可以簡寫為：

文獻(xiàn)[22]提出，可以使用乘法更新過程最小化單獨(dú)對(duì)子網(wǎng)內(nèi)部的系數(shù)矩陣和基矩陣進(jìn)行優(yōu)化。注意，此步驟是針對(duì)每個(gè)子網(wǎng)絡(luò)獨(dú)立執(zhí)行的。則可得到基矩陣和系數(shù)矩陣的迭代公式。

圖正則項(xiàng)權(quán)重矩陣W可定義為：

其中，N(i)為節(jié)點(diǎn)i的k-最近鄰集合，并采用0-1 加權(quán)方式創(chuàng)建k-近鄰圖的權(quán)重矩陣：如果節(jié)點(diǎn)i是節(jié)點(diǎn)j的k-近鄰節(jié)點(diǎn)，或者節(jié)點(diǎn)j是節(jié)點(diǎn)i的k-近鄰節(jié)點(diǎn)時(shí)，Wi,j=1；否則Wi,j=0。

若已知節(jié)點(diǎn)i和節(jié)點(diǎn)j或節(jié)點(diǎn)j和節(jié)點(diǎn)i屬于同一類，則Wi,j=1，否則Wi,j=0。

得到U和V后，根據(jù)之后推導(dǎo)得到的公式（22）初始化V*。

3.2 固定V*，優(yōu)化U 和V

一旦V*被固定，則每個(gè)子網(wǎng)絡(luò)就可以獨(dú)立進(jìn)行優(yōu)化。對(duì)于每個(gè)子網(wǎng)絡(luò)，將損失函數(shù)簡寫如下：

接下來，推導(dǎo)出可用于最小化公式（12）中的優(yōu)化問題的更新規(guī)則。

3.2.1 固定V*和V ，更新U

設(shè)ψ為滿足限制條件U≥0 的拉格朗日乘子矩陣，則拉格朗日函數(shù)L(U,V)=O(U,V)+tr(ψU)。只考慮包含U的項(xiàng)，可以把L(U,V)重新寫成：

結(jié)合式（3）：

R對(duì)U進(jìn)行求導(dǎo)可得：

運(yùn)用KKT（Karush-Kuhn-Tucker）條件可得：

結(jié)合以上條件，可得出以下U迭代公式：

3.2.2 固定V*和U ，更新V

為確保從不同子網(wǎng)中學(xué)習(xí)的V(t)具有可比性，首先對(duì)U的列向量用Q進(jìn)行正則化：

設(shè)Φ為滿足限制條件V≥0 的拉格朗日乘子矩陣，則拉格朗日函數(shù)：

和之前的步驟一樣，可以得到V的迭代公式：

3.3 固定U 和V ，優(yōu)化V*

損失函數(shù)O對(duì)V*求導(dǎo)：

可以得到V*的迭代式為：

算法1基于圖正則項(xiàng)非負(fù)矩陣分解的異質(zhì)網(wǎng)絡(luò)聚類方法

INPUT：HIN{X(1),…,X(t),…,X(T)}，parameters α，number of clusters K

OUTPUT：Clustering on both center type and attribute types

1.Normalize each subnetX(t)such that ||X(t)||1=1

2.InitializeU(t),V(t),V*andβ(t)(1 ≤t≤T)

3.while Eq.6 not converges do

4.for t=1 to T do

5.while Eq.12 not converges do

6.FixingV*,β(t)andV(t),updateU(t)by Eq.17

7.ComputeQ(t)as in Eq.3

8.NormalizeU(t)andV(t)as in Eq.18

9.FixingV*,β(t)andU(t),updateV(t)by Eq.20

10.end while

11.end for

12.FixingU(t)andV(t)(1 ≤t≤T), updateV*andβ(t)by Eqs.22 and 7.

13.end while

14.Cluster nodes of center type indicated by arg maxkVj*,k

15.For each attribute type t，cluster nodes of this type indicated by

3.4 時(shí)間復(fù)雜度分析

對(duì)于每個(gè)子網(wǎng)絡(luò)，內(nèi)循環(huán)的算術(shù)運(yùn)算并不復(fù)雜，這與公式（1）中單個(gè)子網(wǎng)絡(luò)NMF 的乘法更新規(guī)則非常相似。設(shè)M為中心類型節(jié)點(diǎn)個(gè)數(shù)，N為屬性節(jié)點(diǎn)個(gè)數(shù)，K為分類個(gè)數(shù)，T為子網(wǎng)絡(luò)個(gè)數(shù)。分步分析算法的復(fù)雜度，更新U的時(shí)間復(fù)雜度為O(MNK+(M+N)K2+(2N+3)K) ，更新V的時(shí)間復(fù)雜度為O(MNK+(M+N)K2+2NK)，更新共識(shí)矩陣V*時(shí)間復(fù)雜度為O(TMN)，算法的總復(fù)雜度為O(TMNK)。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)集

DBLP[5]是計(jì)算機(jī)領(lǐng)域的英文文獻(xiàn)數(shù)據(jù)庫，收錄了國際期刊和會(huì)議等公開發(fā)表的論文。它包含4 023 位作者，20個(gè)會(huì)議和11 771個(gè)關(guān)鍵詞，涵蓋了人工智能、信息檢索、數(shù)據(jù)挖掘和數(shù)據(jù)庫四個(gè)領(lǐng)域。其滿足星型結(jié)構(gòu)，可分為三個(gè)子網(wǎng)絡(luò)：論文-會(huì)議子網(wǎng)絡(luò)、論文-作者子網(wǎng)絡(luò)、論文-會(huì)議子網(wǎng)絡(luò)，中心類型節(jié)點(diǎn)為論文節(jié)點(diǎn)。

Digg[23]數(shù)據(jù)集是集合了新聞信息和社交信息的網(wǎng)站，用戶可以在該網(wǎng)站上發(fā)布、評(píng)論新聞，也可以在網(wǎng)站上進(jìn)行交友活動(dòng)。Digg 數(shù)據(jù)集由9 583 個(gè)用戶，44 005條新聞和8 596個(gè)關(guān)鍵字組成，共包含4個(gè)興趣小組：游戲小組、政治小組、體育小組和商業(yè)小組。在實(shí)驗(yàn)中取其40 000 條數(shù)據(jù)。其滿足星型結(jié)構(gòu)，可分為兩個(gè)子網(wǎng)絡(luò)：新聞-用戶子網(wǎng)絡(luò)、新聞-關(guān)鍵字子網(wǎng)絡(luò)，中心類型節(jié)點(diǎn)為新聞節(jié)點(diǎn)。

Cora[24]論文引用數(shù)據(jù)集，該數(shù)據(jù)集由30 714篇學(xué)術(shù)論文、20 224 位作者以及17 265 個(gè)關(guān)鍵字組成，共包含7個(gè)研究領(lǐng)域：案例學(xué)習(xí)、遺傳算法、神經(jīng)網(wǎng)絡(luò)、概率方法、增強(qiáng)學(xué)習(xí)、規(guī)則學(xué)習(xí)、理論研究。數(shù)據(jù)集中有關(guān)鍵字、作者和論文這三種節(jié)點(diǎn)，實(shí)驗(yàn)選擇論文作為中心類型節(jié)點(diǎn)，兩個(gè)子網(wǎng)絡(luò)為論文-作者網(wǎng)絡(luò)和論文-關(guān)鍵字網(wǎng)絡(luò)。三個(gè)網(wǎng)絡(luò)的主要特征如表1所示。

表1 三個(gè)數(shù)據(jù)集的特征

4.2 度量標(biāo)準(zhǔn)

由于實(shí)驗(yàn)選擇的數(shù)據(jù)集社區(qū)結(jié)構(gòu)已知，這里采用兩種通用的評(píng)價(jià)指標(biāo)來衡量各種聚類算法的聚類質(zhì)量：

聚類準(zhǔn)確度（AC）[25]：將預(yù)測結(jié)果與實(shí)際標(biāo)簽做對(duì)比。可定義為：

其中，AC為聚類準(zhǔn)確率，ci和ci分別為數(shù)據(jù)點(diǎn)xi的標(biāo)簽與實(shí)際標(biāo)簽；δ(i,j) 為 delta 函數(shù)，如果i=j，δ(i,j)=1，否則δ(i,j)=0 ；map(·) 為最優(yōu)映射函數(shù)。聚類準(zhǔn)確率越高，表明聚類算法的聚類質(zhì)量越好。

標(biāo)準(zhǔn)互信息（NMI）[26]：為了評(píng)價(jià)社區(qū)發(fā)現(xiàn)的有效性，引入標(biāo)準(zhǔn)互信息（NMI）指標(biāo)。通過對(duì)比網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)與算法發(fā)現(xiàn)的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的相似性驗(yàn)證算法的有效性。NMI 的取值范圍為[0，1]，值越大表示劃分得到的社區(qū)越接近真實(shí)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。NMI定義為：

其中，Ni表示聚類標(biāo)簽與實(shí)際標(biāo)簽集中第i類樣本的數(shù)目 (1 ≤i≤k)，Ni,j為第i個(gè)類簇中屬于實(shí)際的第j類的樣本數(shù)目。NMI值越大，這說明算法的社區(qū)劃分質(zhì)量越好。

4.3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文提出的 HINGMF 算法的有效性，本文分別在三個(gè)常用的異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集：DBLP 網(wǎng)絡(luò)、Digg網(wǎng)絡(luò)、Cora網(wǎng)絡(luò)上進(jìn)行了驗(yàn)證，度量標(biāo)準(zhǔn)有聚類準(zhǔn)確度和標(biāo)準(zhǔn)互信息，它們都能一定程度地反映算法聚類的效果。之后將其結(jié)果與其他三種經(jīng)典算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，HINGMF算法具有較高的精度和效率，聚類效果要明顯好于其他常用算法。

4.3.1 圖正則項(xiàng)參數(shù)λ 的選擇

為了分析圖正則項(xiàng)參數(shù)λ對(duì)HINGMF 算法聚類質(zhì)量的影響，從0至0.3選取9個(gè)點(diǎn)，調(diào)整參數(shù)λ的值，對(duì)三個(gè)數(shù)據(jù)集進(jìn)行測試，分析AC和NMI值的變化情況。結(jié)果如圖3所示。

從圖3中可以看出，當(dāng)沒有任何子網(wǎng)絡(luò)內(nèi)部連接信息時(shí)，即λ接近0時(shí)，算法變?yōu)镠INMF算法，聚類效果較差。隨著λ的增大，各個(gè)子網(wǎng)絡(luò)內(nèi)部拓?fù)湫畔⒈患尤耄垲愋Ч饾u變好。當(dāng)λ超過0.1 后，不論在DBLP 數(shù)據(jù)集、Digg 數(shù)據(jù)集，還是在Cora 數(shù)據(jù)集上，由于加入過量的子網(wǎng)絡(luò)內(nèi)部連接信息，降低了作為連接所有屬性類型節(jié)點(diǎn)的中心類型節(jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)中的重要性，算法的聚類效果開始下降。所以在后續(xù)實(shí)驗(yàn)中，圖正則項(xiàng)參數(shù)λ均設(shè)為0.1。

4.3.2 實(shí)驗(yàn)結(jié)果

為了證明所提方法聚類性能的有效性，與以下算法進(jìn)行了比較。

NetClus[27]：針對(duì)異質(zhì)網(wǎng)絡(luò)中大量存在的星型結(jié)構(gòu)網(wǎng)絡(luò)，進(jìn)行了排序迭代聚類，利用排序提高聚類的效果，并且劃分出具有相同星型結(jié)構(gòu)的社區(qū)集合。它是目前針對(duì)星型網(wǎng)絡(luò)比較有效且常用的聚類方法。

NMF-LSE[22]：該算法在非負(fù)矩陣分解的基礎(chǔ)上，結(jié)合空間流形約束加入了圖正則項(xiàng)，同樣將先驗(yàn)信息融入圖正則項(xiàng)權(quán)重矩陣，將先驗(yàn)信息與拓?fù)湫畔⑾嘟Y(jié)合，有效平衡了兩者的關(guān)系，提高了聚類的性能。

HINMF[28]：異質(zhì)網(wǎng)絡(luò)非負(fù)矩陣分解算法。該算法針對(duì)異質(zhì)網(wǎng)絡(luò)中的星型網(wǎng)絡(luò)，通過實(shí)現(xiàn)各個(gè)子網(wǎng)中中心類型節(jié)點(diǎn)最小化來平衡不同子網(wǎng)絡(luò)之間的差異，但是沒有考慮各個(gè)子網(wǎng)內(nèi)部的拓?fù)浣Y(jié)構(gòu)，不過依然能夠達(dá)到比較好的聚類效果。

表2 記錄了四種方法在不同數(shù)據(jù)集中的聚類效果?？梢钥吹?，HINGMF 的表現(xiàn)要優(yōu)于其他算法，因?yàn)樗ㄟ^對(duì)不同子網(wǎng)絡(luò)共有潛在結(jié)構(gòu)的共識(shí)矩陣進(jìn)行學(xué)習(xí)，充分挖掘并利用了各個(gè)子網(wǎng)絡(luò)之間的關(guān)聯(lián)信息，又引入了圖正則項(xiàng)，將中心類型子空間和屬性類型子空間的內(nèi)部連接關(guān)系作為約束項(xiàng)，引進(jìn)到算法中，有效地利用了子網(wǎng)絡(luò)內(nèi)部拓?fù)浣Y(jié)構(gòu)信息，成功整合了不同子網(wǎng)之間關(guān)聯(lián)信息和子網(wǎng)內(nèi)部幾何信息，去除了部分噪聲，所以算法在數(shù)據(jù)集上的效果都比較好。而HINMF 算法，同樣考慮了各個(gè)子網(wǎng)之間的關(guān)聯(lián)信息，但是并沒有考慮各個(gè)子圖內(nèi)部節(jié)點(diǎn)的幾何信息，從而算法精度較低。而NMF-LSE算法在針對(duì)同質(zhì)網(wǎng)絡(luò)進(jìn)行聚類時(shí)能夠有非常好的效果，但是沒有考慮星型結(jié)構(gòu)網(wǎng)絡(luò)的各個(gè)子網(wǎng)之間的關(guān)聯(lián)性，所以效果一般。NetClus 算法先對(duì)屬性類型節(jié)點(diǎn)進(jìn)行排序，再根據(jù)中心類型節(jié)點(diǎn)確定聚類對(duì)象向量，迭代調(diào)整中心類型節(jié)點(diǎn)類別，進(jìn)而完成社區(qū)劃分，但是當(dāng)數(shù)據(jù)較多時(shí)，排序過程耗費(fèi)時(shí)間比較復(fù)雜，且排序并不能讓節(jié)點(diǎn)精確劃分，故其聚類效果與幾類算法相比不夠理想。

表2 真實(shí)數(shù)據(jù)集中四種算法的性能 %

圖3 參數(shù)λ 對(duì)實(shí)驗(yàn)效果的影響

當(dāng)圖正則項(xiàng)權(quán)重矩陣中加入先驗(yàn)信息時(shí)，實(shí)驗(yàn)結(jié)果如表3所示?？梢钥吹?，加入少許先驗(yàn)信息加入權(quán)重矩陣效果要優(yōu)于采用0-1 加權(quán)方式創(chuàng)建的k-近鄰圖權(quán)重矩陣，同時(shí)避免了計(jì)算k-近鄰圖，減少了計(jì)算量。當(dāng)添加的先驗(yàn)信息只有2%的時(shí)候，其聚類效果已經(jīng)和權(quán)重矩陣為k-近鄰圖的原算法相當(dāng)，之后，隨著先驗(yàn)信息的增多，其效果遠(yuǎn)大于原算法。

表3 加入不同比例先驗(yàn)信息的聚類效果 %

四種算法的結(jié)果對(duì)比如圖4所示?？梢悦黠@看到，提出的算法在精度和NMI值兩個(gè)指標(biāo)上明顯要優(yōu)于其他三個(gè)算法。

5 結(jié)束語

異質(zhì)網(wǎng)絡(luò)中存在多種不同屬性的節(jié)點(diǎn)和關(guān)系信息，迫切需要新的方法應(yīng)對(duì)這種需求。本文提出了一種新的異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法，該方法在遵循星型異質(zhì)網(wǎng)絡(luò)中不同子網(wǎng)絡(luò)中的數(shù)據(jù)點(diǎn)將以高概率分配給相同聚類原則的基礎(chǔ)上，提出了一種可以融合各個(gè)子網(wǎng)絡(luò)異質(zhì)信息的聯(lián)合優(yōu)化算法，該算法對(duì)反映了不同子網(wǎng)絡(luò)共有潛在結(jié)構(gòu)的共識(shí)矩陣進(jìn)行學(xué)習(xí)，使用了共識(shí)矩陣中每個(gè)行向量作為中心類型節(jié)點(diǎn)的在每個(gè)社區(qū)當(dāng)中的隸屬度分布，通過輪流固定系數(shù)矩陣和共識(shí)矩陣，迭代對(duì)兩個(gè)反映不同類型節(jié)點(diǎn)的子空間進(jìn)行優(yōu)化，從而成功解決了無法有效整合異質(zhì)信息的問題。同時(shí)在降維過程中較大限度地保留了異質(zhì)信息的完整性。其次，將正則項(xiàng)引入到優(yōu)化算法之中，結(jié)合多重子空間的流形約束，有效利用了各個(gè)子網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，通過優(yōu)化法則不斷迭代系數(shù)矩陣，找到了高維數(shù)據(jù)在低維空間的緊致嵌入，成功消除了異質(zhì)節(jié)點(diǎn)之間的部分噪聲。如何優(yōu)化算法，使算法適用于大規(guī)模網(wǎng)絡(luò)的分析是本文下一步的研究內(nèi)容。

圖4 不同算法在不同數(shù)據(jù)集聚類效果對(duì)比