基于語義路徑的異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法

吳　奇,陳福才,黃瑞陽,常振超

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,河南鄭州 450001)

?

基于語義路徑的異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法

吳奇,陳福才,黃瑞陽,常振超

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,河南鄭州 450001)

社區(qū)發(fā)現(xiàn)是社會網(wǎng)絡(luò)研究的熱點(diǎn)問題,綜合利用社會網(wǎng)絡(luò)中不同對象間的異質(zhì)信息,可以更加有效地挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu).針對傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法無法有效地利用異質(zhì)信息的問題,本文提出了一種基于語義路徑的異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法,該方法首先定義網(wǎng)絡(luò)中的語義路徑,通過語義路徑來衡量不同類型對象間的異質(zhì)信息相似度,然后以此構(gòu)造可靠性矩陣,作為半監(jiān)督非負(fù)矩陣分解的正則化約束項(xiàng),進(jìn)而實(shí)現(xiàn)異質(zhì)網(wǎng)絡(luò)的社區(qū)劃分.在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,所提出的方法能夠更準(zhǔn)確地發(fā)現(xiàn)異質(zhì)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu).

異質(zhì)網(wǎng)絡(luò);社區(qū)發(fā)現(xiàn);語義路徑;非負(fù)矩陣分解

1　引言

隨著Web2.0時代的到來,博客、微博等社交網(wǎng)絡(luò)應(yīng)用發(fā)展迅速.這些網(wǎng)絡(luò)不僅包含不同類型的節(jié)點(diǎn),還包含不同類型的關(guān)系.傳統(tǒng)社會網(wǎng)絡(luò)分析方法主要針對同質(zhì)網(wǎng)絡(luò)(homogenesis network),難以描述這種結(jié)構(gòu)復(fù)雜的網(wǎng)絡(luò),針對包含多類型節(jié)點(diǎn)、多類型關(guān)系的異質(zhì)網(wǎng)絡(luò)(heterogeneous network)[1]的研究應(yīng)運(yùn)而生.目前,異質(zhì)網(wǎng)絡(luò)的研究已成為數(shù)據(jù)挖掘領(lǐng)域最為活躍的研究課題之一.

異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)挖掘的核心研究問題之一是社區(qū)發(fā)現(xiàn)(community detection)[2].社區(qū)發(fā)現(xiàn)即根據(jù)網(wǎng)絡(luò)包含的鏈接、內(nèi)容等大量屬性信息,對網(wǎng)絡(luò)中功能或性質(zhì)對等的潛在結(jié)構(gòu)進(jìn)行識別[3].挖掘異質(zhì)網(wǎng)絡(luò)中有用的、相對穩(wěn)定的社區(qū),對網(wǎng)絡(luò)信息的挖掘、推薦及網(wǎng)絡(luò)的演化預(yù)測具有重要的研究價值[4].

通過引入先驗(yàn)知識輔助社區(qū)劃分,以半監(jiān)督方式挖掘網(wǎng)絡(luò)結(jié)構(gòu)是目前社區(qū)發(fā)現(xiàn)的研究熱點(diǎn).Eaton和Mansbach利用統(tǒng)計(jì)物理中的spin-grass模型[5],將先驗(yàn)信息融入模塊度Q的計(jì)算,輔助進(jìn)行社區(qū)發(fā)現(xiàn).Ma[6]等在研究對稱非負(fù)矩陣分解模型時發(fā)現(xiàn),預(yù)先指定部分節(jié)點(diǎn)信息,并將其融入鄰接矩陣可以有效提高社區(qū)發(fā)現(xiàn)精度.Zhang[7]等擴(kuò)展了這種方法,利用網(wǎng)絡(luò)的先驗(yàn)信息直接修改鄰接矩陣,擴(kuò)展了模型的使用范圍.這些方法雖然都利用網(wǎng)絡(luò)的先驗(yàn)信息,進(jìn)而優(yōu)化社區(qū)劃分,但它們只能利用同質(zhì)網(wǎng)絡(luò)中的先驗(yàn)知識,當(dāng)網(wǎng)絡(luò)為異質(zhì)網(wǎng)絡(luò)時,這些方法不再適用[8].因此,本文設(shè)計(jì)了一種基于語義路徑的非負(fù)矩陣分解的方法(Semantic-Path Nonnegative Matrix Factorization,SPNMF),該方法利用語義路徑計(jì)算異質(zhì)網(wǎng)絡(luò)中不同類型節(jié)點(diǎn)之間的相似度信息,以此作為社區(qū)發(fā)現(xiàn)的先驗(yàn)條件,進(jìn)而指導(dǎo)異質(zhì)網(wǎng)絡(luò)的社區(qū)劃分,提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確性.

2　傳統(tǒng)非負(fù)矩陣分解方法

Lee和Seung[9]在Nature上首先提出了非負(fù)矩陣分解(Nonnegative Matrix Factorization,NMF)算法,NMF算法要求被分解的數(shù)據(jù)矩陣的元素值非負(fù),該約束條件符合實(shí)際數(shù)據(jù)的物理屬性,具有良好的可解釋性和物理意義.NMF算法的目標(biāo)函數(shù)為:

(1)

(2)

(3)

當(dāng)且僅當(dāng)W和H都是穩(wěn)定點(diǎn)的時候,迭代停止.

Lee和Seung的NMF方法具有迭代簡單,可以提取出局部特征的優(yōu)點(diǎn).但未對已知先驗(yàn)信息進(jìn)行研究,算法精度不高.基于此,Yang[10]等提出了基于半監(jiān)督聚類學(xué)習(xí)的NMF-LSE方法.方法假定網(wǎng)絡(luò)數(shù)據(jù)經(jīng)非負(fù)矩陣分解后,同一社區(qū)節(jié)點(diǎn)間的局部鄰域結(jié)構(gòu)能夠在分解后的矩陣中保留,即高維空間中距離較近的向量映射到低維空間上時,距離依然較小.基于這一假設(shè),方法引入正則化約束輔助NMF進(jìn)行社區(qū)劃分,使用式(4)衡量節(jié)點(diǎn)i和j的相似程度:

(4)

并進(jìn)一步引入矩陣O,矩陣O的元素Oij由節(jié)點(diǎn)i和j的拓?fù)湎嗨贫却_定,該矩陣可衡量節(jié)點(diǎn)間相似程度的可靠性:

(5)

(6)

修正后更新準(zhǔn)則為:

(7)

(8)

NMF-LSE方法通過半監(jiān)督學(xué)習(xí)方法引入了可靠性矩陣O,結(jié)合可信度參數(shù)λ,提高了NMF方法的發(fā)現(xiàn)精度,但該方法沒考慮到異質(zhì)網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈接的復(fù)雜關(guān)系,缺乏對多種屬性的合理度量,該方法難以有效應(yīng)用于異質(zhì)網(wǎng)絡(luò)的處理場景中.

3　基于語義路徑的非負(fù)矩陣分解方法

本文提出的基于語義路徑的非負(fù)矩陣分解方法SPNMF,主要針對傳統(tǒng)NMF方法無法分析異質(zhì)網(wǎng)絡(luò)的問題,通過優(yōu)化NMF-LSE方法中的可靠性矩陣O,充分利用了異質(zhì)網(wǎng)絡(luò)的語義路徑先驗(yàn)信息,將其作為監(jiān)督項(xiàng),進(jìn)而指導(dǎo)異質(zhì)網(wǎng)絡(luò)的社區(qū)劃分.

3.1語義路徑相似度

以論文-作者-標(biāo)簽網(wǎng)絡(luò)為例,如圖1所示,若以論文(P)作為中心節(jié)點(diǎn),則網(wǎng)絡(luò)(圖1(a))包含2種語義路徑:論文(P)-標(biāo)簽(L)之間的內(nèi)容關(guān)系(圖1(b))和論文(P)-作者(A)之間的撰寫關(guān)系(圖1(c)),這兩種語義路徑都是論文引用網(wǎng)絡(luò)的輔助劃分信息.

3.2語義路徑相似度的計(jì)算

為方便模型的構(gòu)建及計(jì)算,語義路徑的開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)需設(shè)置為同類型節(jié)點(diǎn),仍以論文-作者-標(biāo)簽網(wǎng)絡(luò)為例,則網(wǎng)絡(luò)的兩種語義路徑可以表示為圖1(b)和1(c).

由于中心節(jié)點(diǎn)被設(shè)定為論文(P),則語義路徑論文(P)-標(biāo)簽(L)可以表示為P-L-P,如圖1(b),可以使用關(guān)系矩陣計(jì)算語義路徑P-L-P之間的語義路徑相似度.

定義3關(guān)系矩陣若存在異質(zhì)網(wǎng)絡(luò),即可定義語義路徑P,則語義路徑P的關(guān)系矩陣可以表示為

M=UA1A2UA2A3…UAl-1Al

(9)

sim(xi,xj)M=

(10)

針對某條語義路徑P-L-P而言,其關(guān)系矩陣可以表示為MPL,則兩個節(jié)點(diǎn)之間的語義路徑相似度為:

sim(xi,xj)MPLP=

(11)

定義3、定義4有其物理意義,定義3給出的關(guān)系矩陣本質(zhì)上就是將網(wǎng)絡(luò)其他類型的節(jié)點(diǎn)看成中心節(jié)點(diǎn)的特征向量,而定義4給出的語義路徑相似度就是利用余弦相似度計(jì)算中心節(jié)點(diǎn)多種特征之間的關(guān)系相似度.由于論文標(biāo)簽之間沒有交互關(guān)系,定義3、定義4可以較為準(zhǔn)確地衡量標(biāo)簽對中心節(jié)點(diǎn)的影響.

論文(P)-作者(A)關(guān)于中心節(jié)點(diǎn)的語義路徑可以表示為P-A-P,但由于論文的作者之間存在論文標(biāo)簽之間沒有的復(fù)雜合作關(guān)系,定義3中關(guān)系矩陣并不能很好的衡量語義路徑P-A-P中包含的關(guān)系.如圖2所示,論文101、論文102、論文103都是關(guān)于社區(qū)發(fā)現(xiàn)的文章,論文104是其它領(lǐng)域的文章,這些論文由A、B、C、D、E五個作者完成,他們相互之間存在合作關(guān)系,但A與C、D之間并沒有直接合作過,若僅依靠定義4中語義路徑相似度的計(jì)算,論文101和論文103并不屬于同一個研究領(lǐng)域,這并不符合實(shí)際劃分.

針對定義3中的關(guān)系矩陣并不適合例如作者合作網(wǎng)絡(luò)等內(nèi)部存在聯(lián)系的網(wǎng)絡(luò)的問題,考慮到這種內(nèi)部網(wǎng)絡(luò)本質(zhì)上是同質(zhì)網(wǎng)絡(luò),可以使用拓?fù)湎嗨菩灾笜?biāo)對該類網(wǎng)絡(luò)進(jìn)行相似度計(jì)算,采用Jaccard相似度對關(guān)系矩陣進(jìn)行優(yōu)化:

(12)

其中,I表示節(jié)點(diǎn)Xi的鄰居節(jié)點(diǎn)的集合,J表示節(jié)點(diǎn)Xi的鄰居節(jié)點(diǎn)的集合.

計(jì)算得到的節(jié)點(diǎn)Jaccard相似度反映了作者合作網(wǎng)絡(luò)內(nèi)部的合作關(guān)系,將這些關(guān)系融入關(guān)系矩陣M的計(jì)算中:

(13)

針對語義路徑P-A-P而言,其優(yōu)化的關(guān)系矩陣變?yōu)?

(14)

優(yōu)化后的關(guān)系矩陣可以較為準(zhǔn)確衡量異質(zhì)網(wǎng)絡(luò)中同類節(jié)點(diǎn)間的直接交互關(guān)系對語義路徑的影響.仍以圖2為例,優(yōu)化后矩陣如圖3(b),可以看出,在優(yōu)化后的關(guān)系矩陣中,論文101、論文102、論文103的作者A、作者B、作者C、作者D明顯特征相關(guān),可以將論文101、論文102、論文103劃為同一社區(qū);而論文104特征繼續(xù)與其他論文無關(guān),仍被看為另一社區(qū),劃分結(jié)果與真實(shí)劃分相同.

最后計(jì)算優(yōu)化后關(guān)系矩陣的語義路徑相似度simMj:

(15)

針對語義路徑P-A-P而言,其語義路徑相似度變?yōu)?

sim(xi,xj)MPAP=

(16)

3.3基于語義路徑的非負(fù)矩陣分解算法

將各條語義路徑相似度矩陣融合:

(17)

其中Osim表示混合語義路徑相似度矩陣,Osimh表示單條語義路徑相似度矩陣,l表示網(wǎng)絡(luò)中語義路徑的數(shù)量.

考慮到語義路徑的關(guān)系矩陣中包含大量的特征信息,計(jì)算語義路徑相似度時利用全部信息會大大增加網(wǎng)絡(luò)的分析成本.為提高算法的運(yùn)行效率,本文利用主成分分析法(Principal Components Analysis,PCA)對網(wǎng)絡(luò)各條語義路徑的關(guān)系矩陣進(jìn)行降維處理[11].此外,為提高相似度計(jì)算速度,算法采用隨機(jī)映射方法[12],將節(jié)點(diǎn)特征映射為哈希信號,在哈希信號空間中計(jì)算節(jié)點(diǎn)的特征相似度.

計(jì)算得到的混合語義路徑相似度矩陣即為NMF-LSE方法的可靠性矩陣O,利用該矩陣,可以充分利用網(wǎng)絡(luò)的先驗(yàn)信息,進(jìn)而監(jiān)督異質(zhì)網(wǎng)絡(luò)的社區(qū)劃分.SPNMF算法流程及相關(guān)說明如下:

算法1基于語義路徑的非負(fù)矩陣分解算法(SPNMF)

輸入:異質(zhì)網(wǎng)絡(luò)G,社區(qū)個數(shù)K,參數(shù)λ;

輸出:基矩陣W,隸屬矩陣H;

Step1:根據(jù)式(9)、式(13)計(jì)算M;

Step2:M←PCA(M)

Step3:根據(jù)式(10)計(jì)算simM;

Step4:根據(jù)式(15)計(jì)算simMJ;

Step5:根據(jù)式(17)計(jì)算O;

Step6:由K-Means方法初始化W,H;

Step7:由式(7)更新W;

Step8:由式(8)更新H;

Step9:根據(jù)式(6)計(jì)算F(H|X,O);

Step10:判斷式(6)是否收斂,若不收斂,則返回Step7;否則轉(zhuǎn)入Step11;

Step11:輸出W,H.

其中,步驟6中非負(fù)基向量組W,H利用K-Means方法進(jìn)行聚類初始化.設(shè)W0和H0分別為K-Means對鄰接矩陣X的行與列的聚類結(jié)果.使用W←W0和H←H0來初始化W和H.

分步分析算法的時間復(fù)雜度.步驟2的復(fù)雜度為O(N×d),d為標(biāo)簽特征數(shù);步驟3～5的最大復(fù)雜度為O(N×|Γi|×ln|Γi|),|Γi|為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)個數(shù),|Γi|一般遠(yuǎn)小于節(jié)點(diǎn)個數(shù)N;步驟6～10的復(fù)雜度為O((NK+M)K),M為邊的個數(shù).算法總復(fù)雜度為O(TN2K),T為迭代次數(shù).

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

本節(jié)首先給出實(shí)驗(yàn)數(shù)據(jù)集來源以及驗(yàn)證方案,而后進(jìn)行了三類實(shí)驗(yàn):

(1)分析了可信度參數(shù)λ選擇對算法精度的影響;

(2)分析了關(guān)系矩陣特征維數(shù)對算法性能的影響;

(3)驗(yàn)證SPNMF算法和NMF-LSE算法具有近似的運(yùn)行速度的同時,SPNMF算法的社區(qū)劃分精度相對于NMF-LSE算法有大幅度的提升.

4.1實(shí)驗(yàn)相關(guān)說明

(1)數(shù)據(jù)集

為了驗(yàn)證SPNMF算法在異質(zhì)網(wǎng)絡(luò)上的有效性,實(shí)驗(yàn)采用兩種真實(shí)網(wǎng)絡(luò)進(jìn)行驗(yàn)證:

(a)Cora論文引用數(shù)據(jù)集[13],該數(shù)據(jù)集由30714篇學(xué)術(shù)論文、20224位作者以及17265個關(guān)鍵字組成,共包含7個研究領(lǐng)域:案例學(xué)習(xí)、遺傳算法、神經(jīng)網(wǎng)絡(luò)、概率方法、增強(qiáng)學(xué)習(xí)、規(guī)則學(xué)習(xí)、理論研究.數(shù)據(jù)集存在關(guān)鍵字(K)、作者(A)和論文(P)這三種節(jié)點(diǎn),實(shí)驗(yàn)選擇論文作為中心節(jié)點(diǎn),輔助利用論文-作者撰寫網(wǎng)絡(luò)和論文-關(guān)鍵字標(biāo)簽網(wǎng)絡(luò),對論文網(wǎng)絡(luò)進(jìn)行劃分,劃分所需要的語義路徑分別為P-K-P和P-A-P.

(b)Digg數(shù)據(jù)集[14],Digg是集合了新聞信息和社交信息的網(wǎng)站,用戶可以在該網(wǎng)站上發(fā)布、評論新聞,也可以在網(wǎng)站上進(jìn)行交友活動.Digg數(shù)據(jù)集由9583個用戶節(jié)點(diǎn),44005條新聞和8596個關(guān)鍵字組成,共包含4個興趣小組:游戲小組、政治小組、體育小組和商業(yè)小組.數(shù)據(jù)集中的3類節(jié)點(diǎn)可表示為:用戶(U)、新聞(N)和關(guān)鍵詞(K),實(shí)驗(yàn)選擇用戶作為中心節(jié)點(diǎn),輔助利用用戶-新聞關(guān)注網(wǎng)絡(luò)和新聞-關(guān)鍵詞標(biāo)簽網(wǎng)絡(luò),對用戶網(wǎng)絡(luò)進(jìn)行劃分,劃分所需要的語義路徑分別為U-N-U和U-N-K-N-U.

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

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

定義5聚類準(zhǔn)確率(clustering accuracy)定義為

(18)

定義6標(biāo)準(zhǔn)互信息(Normalized Mutual Information,NMI)定義為:

(19)

4.2實(shí)驗(yàn)及結(jié)果分析

(1)可信度參數(shù)選擇

為了分析可信度參數(shù)λ對算法劃分質(zhì)量的影響,從0至3按照0.3為步長,調(diào)整參數(shù)λ的值,分析NMI值的變化.結(jié)果如圖4所示.

從圖4中可以看出,當(dāng)沒有任何語義路徑信息,即λ=0時,算法變?yōu)闃?biāo)準(zhǔn)NMF算法,社區(qū)劃分效果較差.隨著λ的增長,大量語義路徑信息被加入,算法的劃分效果有明顯提高.但無論是Cora數(shù)據(jù)集還是Digg數(shù)據(jù)集,當(dāng)λ=1.8時,算法的劃分效果開始下降,這是由于過量的語義路徑信息會降低網(wǎng)絡(luò)中心節(jié)點(diǎn)本身結(jié)構(gòu)信息的重要性,進(jìn)而影響社區(qū)劃分.在以下實(shí)驗(yàn)中.算法的可靠性參數(shù)均設(shè)為λ=1.8.

(2)關(guān)系矩陣特征維數(shù)的選擇

由于數(shù)據(jù)集中各語義路徑的關(guān)系矩陣的行向量包含大量特征元素,全部計(jì)算會大大增加運(yùn)算成本,實(shí)驗(yàn)中采用PCA方法對這些特征集合進(jìn)行降維,其中特征信息保留多少主成分元素,取決于保留部分的累計(jì)方差在方差總和中所占百分比.本文選取百分比為85%時的主成分信息作為特征信息,其中,Cora數(shù)據(jù)集中語義路徑P-K-P關(guān)系矩陣的行向量特征由17265維降為6300維,語義路徑P-A-P關(guān)系矩陣的行向量特征由20224維降為7000維.Digg數(shù)據(jù)集中語義路徑U-N-U關(guān)系矩陣的行向量特征由44005維降為7200維,語義路徑U-N-K-N-U關(guān)系矩陣的行向量特征由8596維降為3500維.

圖5表示Cora數(shù)據(jù)集中兩條語義路徑P-K-P和P-A-P的關(guān)系矩陣經(jīng)PCA特征降維后SPNMF算法的準(zhǔn)確率和運(yùn)行時間,圖6表示Digg數(shù)據(jù)集中兩條語義路徑U-N-U和U-N-K-N-U的關(guān)系矩陣經(jīng)PCA特征降維后SPNMF算法的準(zhǔn)確率和運(yùn)行時間.圖5和圖6表明,對數(shù)據(jù)集中關(guān)系矩陣的行向量特征進(jìn)行合理的降維,可以有效減少噪聲特征對算法劃分的影響,在保證算法精度的同時,大大提高算法的運(yùn)行時間.

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

為了驗(yàn)證算法的有效性,算法與經(jīng)典K-Means算法,NMF算法和NMF-LSE算法對比,其中經(jīng)典K-Means算法和NMF算法只分析同質(zhì)網(wǎng)絡(luò),算法只對Cora數(shù)據(jù)集中的論文網(wǎng)絡(luò)和Digg數(shù)據(jù)集中的用戶網(wǎng)絡(luò)進(jìn)行劃分;NMF-LSE算法通過引入半監(jiān)督學(xué)習(xí)的方法,利用網(wǎng)絡(luò)拓?fù)錁?gòu)建可信度矩陣,輔助對論文網(wǎng)絡(luò)和用戶網(wǎng)絡(luò)進(jìn)行劃分;SPNMF算法利用各類節(jié)點(diǎn)與關(guān)系信息,可以綜合網(wǎng)絡(luò)的異質(zhì)信息構(gòu)建可信度矩陣,進(jìn)而對論文網(wǎng)絡(luò)和用戶網(wǎng)絡(luò)進(jìn)行劃分.

實(shí)驗(yàn)利用方法[15]得到論文網(wǎng)絡(luò)和用戶網(wǎng)絡(luò)的社區(qū)數(shù)量,該方法已被證明可以很好地預(yù)測網(wǎng)絡(luò)社區(qū)數(shù).實(shí)驗(yàn)在數(shù)據(jù)集上運(yùn)行5次,計(jì)算度量指標(biāo)的均值.4種算法的運(yùn)算時間、聚類準(zhǔn)確率和標(biāo)準(zhǔn)互信息如表1所示.

表1　真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中4種算法的性能

從表1中可以看出,運(yùn)算時間方面,K-Means聚類速度最快,在四種方法中運(yùn)行時間最短;而其余三種算法都應(yīng)用了非負(fù)矩陣分解的方法,涉及到大量的矩陣乘法迭代運(yùn)算,計(jì)算復(fù)雜度較高,其中NMF算法的運(yùn)算時間最短,SPNMF與NMF-LSE算法的時間復(fù)雜度類似,SPNMF的運(yùn)行時間相對較短,表明充分利用異質(zhì)網(wǎng)絡(luò)的先驗(yàn)信息可以提高算法的運(yùn)行效率.

準(zhǔn)確率方面,K-Means和NMF兩種方法的聚類質(zhì)量一般都比較差,因?yàn)樗鼈兌紱]有利用異質(zhì)網(wǎng)絡(luò)中蘊(yùn)含的結(jié)構(gòu)信息.NMF-LSE算法比單純的NMF算法性能略優(yōu),這是因?yàn)镹MF-LSE算法引入了先驗(yàn)信息,使用半監(jiān)督學(xué)習(xí)的方法指導(dǎo)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn).SPNMF算法的準(zhǔn)確率比其他三種算法都要高,表明適當(dāng)利用異質(zhì)網(wǎng)絡(luò)中多種節(jié)點(diǎn)間的關(guān)系信息,可以有效提高算法的精度.

5　結(jié)束語

異質(zhì)網(wǎng)絡(luò)中存在多種不同屬性的節(jié)點(diǎn)和關(guān)系信息,迫切需要新的方法應(yīng)對這種需求.本文提出了一種新的異質(zhì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法,該方法有效融合了語義路徑和非負(fù)矩陣分解方法,利用異質(zhì)網(wǎng)絡(luò)中不同類型節(jié)點(diǎn)之間的語義路徑相似度,得到其社區(qū)劃分的先驗(yàn)信息,精確指導(dǎo)社區(qū)劃分.算法適用于異質(zhì)網(wǎng)絡(luò),可以提高社區(qū)劃分的精度,并通過對比實(shí)驗(yàn)驗(yàn)證了算法的有效性.目前,算法的計(jì)算復(fù)雜度仍然較高,如何優(yōu)化算法,使算法適用于大規(guī)模網(wǎng)絡(luò)的分析是本文下一步的研究內(nèi)容.

[1]Jiang F,Hong X,Peng Z,et al.Finding dimensions for text based on heterogeneous information network[A].International Conference on Software Engineering and Service Science[C].Beijing:IEEE,2014.819-823.

[2]程學(xué)旗,沈華偉.復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)[J].復(fù)雜性系統(tǒng)與復(fù)雜性科學(xué),2011,8(1):57-70.

CHENG Xue-qi,SHEN Hua-wei.Community structure of complex networks[J].Complex Systems and Complexity Science,2011,8(1):57-70.(in Chinese)

[3]柴變芳,賈彩燕,于劍,等.融合內(nèi)容和鏈接的網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)概率模型綜述[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(11):2524-2528.

CHAI Bian-fang,JIA Cai-yan,YU Jian,et al.Survey of probabilistic models combining content and link for network structure detection[J].Journal of Chinese Computer Systems,2013,34(11):2524-2528.(in Chinese)

[4]張偉哲,王佰玲,何慧,等.基于異質(zhì)網(wǎng)絡(luò)的意見領(lǐng)袖社區(qū)發(fā)現(xiàn)[J].電子學(xué)報,2012,40(10):1927-1932.

ZHANG Wei-zhe,WANG Bai-ling,HE Hui,et al.Public opinion leader community mining based on the heterogeneous network[J].Acta Electronica Sinica,2012,40(10):1927-1932.(in Chinese)

[5]Eaton E,Mansbach R.A spin-glass model for semi-supervised community detection[A].Twenty-Sixth AAAI Conference on Artificial Intelligence[C].Toronto:AAAI,2012.900-906.

[6]Ma X,Gao L,Yong X,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.

[7]Zhang Z Y.Community structure detection in complex networks with partial background information[J].Europhysics Letters,2013,101(4):005-021.

[8]Meng Q,Tafavogh S,Kennedy P J.Community detection on heterogeneous networks by multiple semantic-path clustering[A].International Conference on Computational Aspects of Social Networks[C].Porto:IEEE,2014.7-12.

[9]Lee D D,Seung H S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999,401(6755):788-791.

[10]Yang L,Cao X,Jin D,et al.A unified semi-supervised community detection framework using latent space graph regularization[J].IEEE Transactions on Cybernetics,2014,PP(99):1-14.

[11]柴變芳,趙曉鵬,賈彩燕,等.內(nèi)容網(wǎng)絡(luò)廣義社區(qū)發(fā)現(xiàn)有效算法[J].計(jì)算機(jī)科學(xué)與探索,2014,8(9):1076-1084.

CHAI Bian-fang,ZHAO Xiao-peng,JIA Cai-yan,et al.An efficient algorithm for general community detection in content networks [J].Journal of Frontiers of Computer Science and Technology,2014,8(9):1076-1084.(in Chinese)

[12]Charikar M S.Similarity estimation techniques from rounding algorithms[A].Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing[C].Quebec:ACM,2002.380-388.

[13]McCallum A K,Nigam K,Rennie J,et al.Automating the construction of internet portals with machine learning[J].Information Retrieval,2000,3(2):127-163.

[14]Lin Y R,Sun J,Sundaram H,et al.Community discovery via metagraph factorization[J].ACM Transactions on Knowledge Discovery from Data,2011,5(3):1284-1310.

[15]Hopcroft John,Khan Omar,Kulis Brian,et al.Tracking evolving communities in large linked networks[J].PNAS,2004,101(1):5249-5253.

吳奇男,1991年生于江蘇徐州.現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士研究生.主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)和社區(qū)發(fā)現(xiàn).

E-mail:wqstudyy@126.com

陳福才男,1974年生于江西高安.現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心研究員、碩士生導(dǎo)師.主要研究方向?yàn)榇髷?shù)據(jù)處理.

E-mail:13503827650@139.com

Community Detection in Heterogeneous Network with Semantic Paths

WU Qi,CHEN Fu-cai,HUANG Rui-yang,CHANG Zhen-chao

(NationalDigitalSwitchingSystemEngineeringandTechnologicalR&DCenter,Zhengzhou,Henan450001,China)

Community detection is an important and crucial issue in social networks.Using different objects’ information can help detect the community structure.However,many existing community detection methods are hardly applied in heterogeneous networks.To address the above problem,we propose a semantic-path based community detection method.This method first calculates the similarity matrix based on semantic paths,obtaining the reliability matrix to build a graph regularization term.Then the nonnegative matrix factorization is employed to achieve the community detection in heterogeneous networks.Simulation on real web data demonstrates that our proposed algorithm can detect the community structure in heterogeneous networks.

heterogeneous network;community detection;semantic path;nonnegative matrix factorization

2015-04-28;修回日期:2015-07-16；責(zé)任編輯：覃懷銀

國家科技支撐計(jì)劃(No.2014BAH30B01)

TP393

A

0372-2112 (2016)06-1465-07