適用于大規(guī)模信息網(wǎng)絡(luò)的語義社區(qū)發(fā)現(xiàn)方法*

沈桂蘭，賈彩燕，于 劍，楊小平

1.北京聯(lián)合大學(xué) 商務(wù)學(xué)院，北京 100025

2.中國人民大學(xué) 信息學(xué)院，北京 100087

3.北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044

適用于大規(guī)模信息網(wǎng)絡(luò)的語義社區(qū)發(fā)現(xiàn)方法*

沈桂蘭1,2+，賈彩燕3，于 劍3，楊小平2

1.北京聯(lián)合大學(xué) 商務(wù)學(xué)院，北京 100025

2.中國人民大學(xué) 信息學(xué)院，北京 100087

3.北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044

對節(jié)點帶有內(nèi)容的信息網(wǎng)絡(luò)進(jìn)行語義社區(qū)發(fā)現(xiàn)是新的研究方向。融合節(jié)點內(nèi)容增加了算法的復(fù)雜度。提出了一種在線性時間內(nèi)進(jìn)行語義社區(qū)發(fā)現(xiàn)的標(biāo)簽傳播算法，用LDA（latent Dirichlet allocation）主題模型表示節(jié)點內(nèi)容，以節(jié)點內(nèi)容相似度和傳播影響力的乘性模型作為標(biāo)簽傳播的策略，在歸一化過程中，自然融合節(jié)點內(nèi)容和網(wǎng)絡(luò)結(jié)構(gòu)信息，標(biāo)簽迭代過程中，采用節(jié)點與絕大部分鄰居節(jié)點內(nèi)容不相同才進(jìn)行更新的策略，保證算法的運行效率。通過在不同規(guī)模的12個真實數(shù)據(jù)集上進(jìn)行實驗，以模塊度和純度作為度量標(biāo)準(zhǔn)，驗證了算法在語義社區(qū)發(fā)現(xiàn)上的有效性和可行性。

語義社區(qū)發(fā)現(xiàn)；LDA主題模型；內(nèi)容相似度；標(biāo)簽傳播策略；傳播影響力

1 引言

信息技術(shù)及互聯(lián)網(wǎng)技術(shù)的發(fā)展，節(jié)點帶有信息內(nèi)容的復(fù)雜網(wǎng)絡(luò)日益增多。根據(jù)節(jié)點所承載信息的類型，這些網(wǎng)絡(luò)可以分為Web網(wǎng)絡(luò)、郵件網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)、社交媒體網(wǎng)絡(luò)等，人們將其統(tǒng)稱為信息網(wǎng)絡(luò)。信息網(wǎng)絡(luò)是一種節(jié)點帶有明顯語義特征的現(xiàn)實復(fù)雜網(wǎng)絡(luò)。信息網(wǎng)絡(luò)在宏觀上具有網(wǎng)絡(luò)的鏈接關(guān)系屬性，在微觀上每個節(jié)點具有語義內(nèi)容屬性。節(jié)點內(nèi)容屬性的增加給社區(qū)發(fā)現(xiàn)帶來了新的內(nèi)涵。有意義的社區(qū)應(yīng)是節(jié)點鏈接緊密，且內(nèi)容一致的語義社區(qū)。語義社區(qū)發(fā)現(xiàn)是信息網(wǎng)絡(luò)研究的良好擴(kuò)充和發(fā)展，對于分析信息網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，理解網(wǎng)絡(luò)的功能，發(fā)現(xiàn)隱藏的規(guī)律和預(yù)測信息網(wǎng)絡(luò)的行為有著非常重要的理論意義，在實際應(yīng)用中對智能信息檢索、個性化服務(wù)、社會推薦等信息管理領(lǐng)域的技術(shù)發(fā)展和應(yīng)用具有深刻的促進(jìn)作用。

目前，對信息網(wǎng)絡(luò)語義社區(qū)進(jìn)行發(fā)現(xiàn)的研究主要集中在以下三方面：（1）單純利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；（2）單純利用節(jié)點內(nèi)容屬性；（3）融合節(jié)點屬性和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

第一類方式是目前語義社區(qū)發(fā)現(xiàn)的主流方法，基于緊密鏈接的節(jié)點趨于具有相同的興趣愛好或主題內(nèi)容的前提假設(shè)，以發(fā)現(xiàn)鏈接緊密的社區(qū)結(jié)構(gòu)為目標(biāo)。根據(jù)社區(qū)定義及其潛在原理，這些方法可分為以下幾類：（1）以社區(qū)質(zhì)量作為目標(biāo)函數(shù)進(jìn)行優(yōu)化的方法，目前廣泛采用的社區(qū)質(zhì)量的衡量標(biāo)準(zhǔn)是2004年Newman等人[1]提出了模塊度函數(shù)Q，可用貪心[2]、迭代啟發(fā)[3]、譜優(yōu)化[4]、模擬退火[5]等方案進(jìn)行優(yōu)化，從而發(fā)現(xiàn)社區(qū)；（2）節(jié)點聚類的方法，這類方法把社區(qū)看作節(jié)點相似度高的簇，采用譜圖理論[6]或根據(jù)節(jié)點的結(jié)構(gòu)相似度[7]進(jìn)行聚類，從而發(fā)現(xiàn)社區(qū)結(jié)構(gòu)；（3）圖分割的方法，此類方法選取具有某些特性的邊或者節(jié)點，并將其全部刪除，以實現(xiàn)社區(qū)發(fā)現(xiàn)，選取策略包括邊介數(shù)大的優(yōu)先[4]、邊聚集系數(shù)小的優(yōu)先[8]等；（4）動態(tài)的方法，如采用標(biāo)簽傳播[9]或馬爾科夫隨機游走[10]的方法進(jìn)行社區(qū)發(fā)現(xiàn)。另外，也有一些研究將社區(qū)發(fā)現(xiàn)轉(zhuǎn)化為統(tǒng)計推理問題[11-12]?；诰W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)的方法雖然總能發(fā)現(xiàn)鏈接緊密的社區(qū)結(jié)構(gòu)，卻忽略了節(jié)點內(nèi)容對語義社區(qū)質(zhì)量的改善作用，無法保證社區(qū)節(jié)點在語義上的一致性。

第二類方法則把社區(qū)看作節(jié)點相似度高的簇，基于節(jié)點的內(nèi)容相似度矩陣發(fā)現(xiàn)社區(qū)。如Newman[13]采用自底向上的層次聚類方法發(fā)現(xiàn)社區(qū)，Nguyen等人[14]則采用LDA（latent Dirichlet allocation）模型從博客中提取社區(qū)，并對每個主題下的單詞聚類，進(jìn)而提取元社區(qū)。這類方法本質(zhì)上可歸結(jié)為文本聚類問題，可發(fā)現(xiàn)內(nèi)容一致的節(jié)點集合，但忽略了節(jié)點間真實鏈接關(guān)系，無法保證社區(qū)在鏈接上的緊密性。

第三類方法基于節(jié)點內(nèi)容有助于提高社區(qū)發(fā)現(xiàn)質(zhì)量的假設(shè)，將節(jié)點內(nèi)容和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)統(tǒng)一起來，采用屬性圖聚類的方法或概率組合模型的方法。如SA-Cluster算法[15]是一種屬性圖聚類的方法，該算法首先構(gòu)建屬性增廣圖，然后利用自動學(xué)習(xí)結(jié)構(gòu)相似度和屬性相似度共享率的鄰居隨機游走模型來計算屬性增廣圖中兩點之間的距離，算法以隨機游走距離為基礎(chǔ)進(jìn)行圖聚類，聚類后的結(jié)果是具有同質(zhì)屬性節(jié)點且緊密連接的子圖，即語義社區(qū)。同樣基于馬爾科夫隨機游走的策略，并結(jié)合局部擴(kuò)充的思想，辛宇等人[16]采用LDA模型將節(jié)點內(nèi)容進(jìn)行語義空間量化，采用語義坐標(biāo)的內(nèi)積Eij=mi·mj作為節(jié)點di和節(jié)點dj的語義相似度。其中mi是節(jié)點di在語義空間中的坐標(biāo)，可以通過di的Ni個關(guān)鍵字的加權(quán)均值形式表達(dá)，內(nèi)積越大，節(jié)點語義的相似度越高，據(jù)此構(gòu)造語義社會網(wǎng)絡(luò)的加權(quán)鄰接矩陣E，將其行向量歸一化后加權(quán)鄰接矩陣作為隨機游走策略的一步轉(zhuǎn)移概率矩陣E，從網(wǎng)絡(luò)中選擇語義影響力大的節(jié)點s作為出發(fā)點，經(jīng)過l次轉(zhuǎn)移后最終到達(dá)節(jié)點di的概率為，該概率值超過某個閾值，就將節(jié)點di與節(jié)點s劃在同一個社區(qū)，由此檢測語義社區(qū)。PCL-DC[17]（popularity-based conditional link model-discriminative content）是概率組合模型方法的代表。該方法把鏈接模型和內(nèi)容模型通過一個隱藏變量連接起來發(fā)現(xiàn)語義社區(qū)。

與前兩類方法相比，這類方法綜合考慮了節(jié)點的內(nèi)容屬性和網(wǎng)絡(luò)結(jié)構(gòu)兩方面的特征，所劃分的社區(qū)結(jié)構(gòu)是基于節(jié)點內(nèi)容相似性的，其劃分的結(jié)果更具有內(nèi)聚性。但因節(jié)點的語義信息內(nèi)容多以文本分析為基礎(chǔ)，通常會帶來節(jié)點屬性維數(shù)災(zāi)難，算法復(fù)雜度普遍高等問題，僅適合分析規(guī)模比較小的信息網(wǎng)絡(luò)。

為實現(xiàn)鏈接緊密且語義一致的研究目標(biāo)，在語義社區(qū)發(fā)現(xiàn)中融合節(jié)點內(nèi)容屬性和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)已成為一個研究趨勢。亟待解決兩個關(guān)鍵問題：一是節(jié)點內(nèi)容屬性和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)融合；二是如何保證算法的效率，使其適用于大規(guī)模的信息網(wǎng)絡(luò)。

本文在穩(wěn)定標(biāo)簽傳播算法的基礎(chǔ)上，用LDA主題概率模型對節(jié)點內(nèi)容進(jìn)行主題建模，根據(jù)節(jié)點內(nèi)容的相似度進(jìn)行標(biāo)簽傳播，在傳播概率的歸一化過程中，將內(nèi)容屬性和網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)自然融合。此外，算法在標(biāo)簽傳播策略中加入節(jié)點傳播影響力的作用，保證語義社區(qū)鏈接緊密且語義一致的特征。在標(biāo)簽傳播迭代時，設(shè)置條件更新策略，保證了算法的運行效率。以模塊度和純度作為標(biāo)準(zhǔn)評價，在12個不同規(guī)模的真實信息網(wǎng)絡(luò)上進(jìn)行實驗，驗證了本文算法在語義社區(qū)發(fā)現(xiàn)上的有效性和可行性。分析表明，與標(biāo)簽傳播算法相比，本文算法雖然增加了節(jié)點內(nèi)容屬性，但沒有增加算法復(fù)雜度，適用于大規(guī)模的信息網(wǎng)絡(luò)。

2 節(jié)點內(nèi)容的表示

本文主要考慮節(jié)點內(nèi)容為文本的信息網(wǎng)絡(luò)。經(jīng)典的向量空間模型采用TF-IDF（term frequency-inverse document frequency）的方法表示文本內(nèi)容，常具有高維稀疏性。采用LDA主題概率模型對節(jié)點內(nèi)容進(jìn)行主題建模，把節(jié)點的內(nèi)容從詞向量空間映射到主題向量空間，可以極大地降低內(nèi)容屬性維數(shù)。

2.1 LDA主題建模

LDA[18]是由Blei等人在2003年提出的一種三層貝葉斯概率模型，包含文檔-主題-詞三層結(jié)構(gòu)，文檔到主題服從Dirichlet分布[19]，主題到詞服從多項式分布。LDA主題模型的突出優(yōu)點是具有清晰的層次結(jié)構(gòu)，且LDA主題模型參數(shù)空間的規(guī)模與訓(xùn)練文檔數(shù)量無關(guān)，適合處理大規(guī)模語料庫。

圖1為LDA概率模型圖。其中M為文檔集的個數(shù)；α和β分別是文檔-主題概率分布和主題-單詞概率分布的先驗知識；Nm是第m個文檔的單詞數(shù)；T是主題數(shù)；Zm,n是第m個文檔中第n個詞的主題；Wm,n是第m個文檔中的第n個詞。在LDA中，集合中的每篇文檔代表了潛在主題所構(gòu)成的一個概率分布，而每個主題又代表了很多詞匯所構(gòu)成的一個概率分布。該模型可以對文檔集進(jìn)行建模，并可以將文檔表示為由特定數(shù)目的潛在主題信息組成。

Fig.1 LDAprobability model圖1LDA概率模型圖

圖1中的單圈實線圓表示固定值，由用戶事先指定，雙圈實線圓表示可觀測的數(shù)據(jù)，單圈虛線圓表示隱藏參數(shù)。文檔的隱藏參數(shù)需要通過概率推導(dǎo)求解，通常采用Gibbs采樣法近似求解隱藏參數(shù)θ和φ。

LDA主題模型將潛在語義相同的詞劃歸在同一主題下，降低了文本內(nèi)容的表示維數(shù)。

2.2 節(jié)點的內(nèi)容相似度

用LDA主題模型提取K個主題作為K維語義空間的基，節(jié)點的內(nèi)容表示為主題的概率分布，用KL距離（Kullback-Leibler divergence，KL）度量兩個節(jié)點的內(nèi)容相似度，KL距離越小，表明兩個概率分布的相似度越大。

假設(shè)兩節(jié)點u和v內(nèi)容的主題分布為P和Q，P(ti)表示節(jié)點u的文本內(nèi)容在第i個主題上的概率，Q(ti)表示節(jié)點v的文本內(nèi)容在第 j個主題上的概率，則兩節(jié)點的內(nèi)容相似度Sim(u,v)歸一化形式表示為：

其中，Mind是所有節(jié)點對中KL距離的最小值；Maxd是最大值。因KL距離是非對稱性的，故dPQ用下列形式表示：

3 基于語義的標(biāo)簽傳播

3.1 標(biāo)簽傳播算法

標(biāo)簽傳播算法LPA[9]是在線性時間O(m+n)內(nèi)發(fā)現(xiàn)社區(qū)的經(jīng)典算法，效率高，便于處理大規(guī)模的網(wǎng)絡(luò)，但算法具有隨機性的因素，社區(qū)發(fā)現(xiàn)的結(jié)果不穩(wěn)定。LabelRank[20]是Xie等人2013年基于改進(jìn)MCL（Markov clustering algorithm）提出的穩(wěn)定的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法，算法以模塊度作為目標(biāo)函數(shù)，為每個節(jié)點存儲、傳播和排序標(biāo)簽，通過傳播（propagation）、膨脹（inflation）、剪枝（cutoff）、條件更新（conditional update）4個算子，進(jìn)行循環(huán)同步標(biāo)簽傳播及標(biāo)簽更新，直到標(biāo)簽更新穩(wěn)定時，將具有同一標(biāo)簽的節(jié)點劃分為同一個社區(qū)。

算法用觀察到鄰居節(jié)點的概率初始化節(jié)點的標(biāo)簽分布：

傳播算子表示為A×P，在傳播過程中，每個節(jié)點向其鄰居節(jié)點傳播自己的標(biāo)簽分布。為了有效地控制標(biāo)簽的傳播過程，使概率高的標(biāo)簽更易于傳播，LabelRank在標(biāo)簽分布矩陣P上應(yīng)用了膨脹算子Γin，并引入剪枝算子Φr，移除閾值低于r的標(biāo)簽，以便減少標(biāo)簽的存儲空間，降低算法的空間復(fù)雜度，且算法性能對r的取值不明顯，實現(xiàn)時無需調(diào)參。算法第四步是條件更新算子Θ，規(guī)定只有當(dāng)節(jié)點標(biāo)簽和其鄰接節(jié)點標(biāo)簽明顯不同時，才進(jìn)行標(biāo)簽更新。

LabelRank算法的每輪迭代運行時間和網(wǎng)絡(luò)的邊的數(shù)量m呈線性關(guān)系，時間復(fù)雜度為O(n+m+4tm)，可近似看作O(n+m)，運行效率較高，輸出的社區(qū)結(jié)構(gòu)具有穩(wěn)定性。另外，LabelRank節(jié)點的標(biāo)簽更新只和局部信息相關(guān)，可以并行處理，適用于大規(guī)模的網(wǎng)絡(luò)。

但LabelRank算法是基于拓?fù)浣Y(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)的方法，節(jié)點的標(biāo)簽分布取決于其觀測到鄰居節(jié)點的概率，沒有考慮節(jié)點與其鄰居節(jié)點在語義上的相似性，無法規(guī)避鏈接結(jié)構(gòu)中噪聲的干擾。本文改進(jìn)了LabelRank算法，在節(jié)點標(biāo)簽傳播過程中，綜合考慮節(jié)點的內(nèi)容屬性和網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特性，便于挖掘鏈接緊密且內(nèi)容一致的高質(zhì)量語義社區(qū)。

3.2 基于內(nèi)容相似度的標(biāo)簽傳播策略

標(biāo)簽傳播策略直接影響社區(qū)的劃分結(jié)果?；诠?jié)點內(nèi)容有助于提高社區(qū)發(fā)現(xiàn)質(zhì)量的假設(shè)，在語義社區(qū)的發(fā)現(xiàn)中，標(biāo)簽按照節(jié)點的內(nèi)容相似度進(jìn)行傳播比單純地按照節(jié)點的鏈接結(jié)構(gòu)進(jìn)行傳播更能發(fā)現(xiàn)語義一致的社區(qū)。首先，標(biāo)簽在傳播時，易向內(nèi)容與其相近的鄰居節(jié)點傳播。把節(jié)點的語義相似度作為節(jié)點標(biāo)簽的傳播概率，考慮了節(jié)點的內(nèi)容屬性特征；其次，在將鄰居節(jié)點標(biāo)簽的傳播概率進(jìn)行歸一化過程中，自然地融入了網(wǎng)絡(luò)的結(jié)構(gòu)特征。以圖2（a）所示的網(wǎng)絡(luò)結(jié)構(gòu)為例，分析不同的標(biāo)簽傳播策略對節(jié)點分配標(biāo)簽的影響。

在LabelRank中，標(biāo)簽根據(jù)節(jié)點觀測到鄰居節(jié)點的概率進(jìn)行傳播。以節(jié)點4為例，從結(jié)構(gòu)特性出發(fā)，將每條連接邊的權(quán)重設(shè)為1，則節(jié)點4以同樣的概率觀測到鄰居節(jié)點1、5、6、7，如圖2（b）所示，其歸一化的觀測概率如圖2（d）所示，節(jié)點4觀測到每個鄰居節(jié)點，即鄰居節(jié)點向節(jié)點4傳遞標(biāo)簽的概率均為0.25，沒有體現(xiàn)出鄰居節(jié)點與節(jié)點4在內(nèi)容上的差異。將節(jié)點對之間的語義相似度作為每條連邊的權(quán)重，如圖2（c）所示，其歸一化的觀測概率如圖2（e）所示，節(jié)點1向節(jié)點4傳播標(biāo)簽的概率0.08遠(yuǎn)小于節(jié)點6向節(jié)點4傳播標(biāo)簽的概率0.34。顯然，針對節(jié)點4，接收節(jié)點6的標(biāo)簽的概率大于接收節(jié)點1的概率，更加符合社區(qū)節(jié)點語義一致性的特征。

3.3 基于傳播強度的標(biāo)簽傳播策略

如前所述，節(jié)點標(biāo)簽分布在歸一化過程中，融合了網(wǎng)絡(luò)的結(jié)構(gòu)特征，這只涉及鄰居節(jié)點，即節(jié)點的度，因此融合的網(wǎng)絡(luò)特征是局部的，沒有全面考慮整個網(wǎng)絡(luò)結(jié)構(gòu)對標(biāo)簽傳播的影響作用，易形成鏈接較為松散的社區(qū)結(jié)構(gòu)。

節(jié)點的標(biāo)簽是否會向其他節(jié)點傳播取決于它們是否有連接，但是傳播的難易程度則取決于節(jié)點之間的語義相似度以及節(jié)點之間的距離。節(jié)點的親近度[21]是該節(jié)點i到網(wǎng)絡(luò)中其他所有節(jié)點 j距離之和的倒數(shù)，表示為式（4），其中n為網(wǎng)絡(luò)中節(jié)點的數(shù)量，可度量節(jié)點在整個網(wǎng)絡(luò)中的全局影響力。親近度越大的節(jié)點在網(wǎng)絡(luò)中的全局影響力越大，向其他節(jié)點傳播的能力越強；反之，親近度越小的節(jié)點在網(wǎng)絡(luò)中的全局影響力越小，向其他節(jié)點傳播的能力越弱。

顯然，在標(biāo)簽傳播過程中，全局影響力大的節(jié)點的標(biāo)簽顯然更易于向全局影響力小的節(jié)點傳播。這里定義了節(jié)點的傳播影響力Inf(j,i)，表示節(jié)點 j的標(biāo)簽向節(jié)點i的傳播能力，值越大，表明節(jié)點 j的標(biāo)簽越容易傳播給節(jié)點i。

結(jié)合節(jié)點的內(nèi)容相似度，用乘性模型定義節(jié)點 j對節(jié)點i的標(biāo)簽傳播強度：

為便于敘述，本文將以節(jié)點的標(biāo)簽傳播強度為傳播策略的算法定義為simInfLPA，將以節(jié)點的內(nèi)容相似度為傳播策略的算法定義為simLPA。

Fig.2 Influence of different label propagation strategies for an information network圖2 信息網(wǎng)絡(luò)中不同標(biāo)簽傳播策略的影響示例圖

在simInfLPA中，節(jié)點的初始化標(biāo)簽分布定義為觀測到其鄰居的標(biāo)簽傳播強度的概率，即：

在傳播過程中，每個節(jié)點按照傳播強度向其鄰居節(jié)點傳播標(biāo)簽，為保證算法的穩(wěn)定性，節(jié)點接收到的標(biāo)簽只有滿足與絕大部分鄰居節(jié)點在語義內(nèi)容上不相似時，才進(jìn)行標(biāo)簽的更新。該條件形式化為：

其中，Sim(i,j)是節(jié)點i和其鄰居節(jié)點 j的內(nèi)容相似度；avgSim是節(jié)點i與其所有鄰居節(jié)點內(nèi)容相似度的平均值；ki是節(jié)點i的度；q是[0,1]之間的參數(shù)。

標(biāo)簽更新函數(shù)如式（9）所示：

圖2（a）所示的網(wǎng)絡(luò)中各節(jié)點的親近度如表1所示，節(jié)點之間的標(biāo)簽傳播強度如表2所示。節(jié)點標(biāo)簽強度綜合了網(wǎng)絡(luò)的結(jié)構(gòu)特性和節(jié)點的語義特性，從表2中顯示的歸一化標(biāo)簽分布數(shù)值來看，目標(biāo)節(jié)點更易于接收高影響力且內(nèi)容相似度高的源節(jié)點傳播過來的標(biāo)簽。

Table 1 Closeness for nodes表1 網(wǎng)絡(luò)節(jié)點親近度

4 評價標(biāo)準(zhǔn)

對信息網(wǎng)絡(luò)的社區(qū)劃分質(zhì)量既要考慮鏈接結(jié)構(gòu)的緊密性，又要考慮社區(qū)語義的一致性，用Newnan提出的經(jīng)典的模塊度Q函數(shù)[1]度量結(jié)構(gòu)緊密性，具體定義為：

Table 2 Propagation intensity for labels表2 標(biāo)簽的傳播強度

其中，m為網(wǎng)絡(luò)中的邊數(shù)；A是網(wǎng)絡(luò)的鄰接矩陣，Aij=0表示節(jié)點i和節(jié)點 j之間沒有邊；節(jié)點i的度表示為ki；節(jié)點i所在的社區(qū)為Ci，如節(jié)點i和 j在同一社區(qū)，則δ(Ci,Cj)=1，否則δ(Ci,Cj)=0，模塊度的大小取決于網(wǎng)絡(luò)的社區(qū)劃分情況C，值越接近1，表明網(wǎng)絡(luò)劃分出的社區(qū)結(jié)構(gòu)的質(zhì)量越好。

度量社區(qū)語義的一致性，用文獻(xiàn)中的評價方法[22]，以真實社區(qū)群組作為參照，利用純度（purity）對社區(qū)發(fā)現(xiàn)的結(jié)果進(jìn)行評價。把信息網(wǎng)絡(luò)數(shù)據(jù)集中真實社區(qū)集合G={G1,G2,…,GS}作為標(biāo)準(zhǔn)社區(qū)集合。算法生成的社區(qū)集合為C={C1,C2,…,CS}，生成社區(qū)Ci的純度定義為：

測試社區(qū)可能包含屬于不同標(biāo)準(zhǔn)社區(qū)的樣本，生成社區(qū)集合和各個標(biāo)準(zhǔn)社區(qū)集合求交，取最大純度作為最終純度。式（11）反映了生成社區(qū)中包含應(yīng)劃分在該社區(qū)的成員分布情況，純度越高，說明越接近標(biāo)準(zhǔn)社區(qū)集合。最終社區(qū)的質(zhì)量用社區(qū)的平均純度來度量，即：

5 實驗及結(jié)果分析

本文對不同規(guī)模的真實數(shù)據(jù)集進(jìn)行了實驗，分別驗證了算法中膨脹因子的取值對社區(qū)度量標(biāo)準(zhǔn)的影響，不同的標(biāo)簽傳播策略對社區(qū)質(zhì)量的影響，不同膨脹因子下算法的時間性能分析以及simInfLPA與經(jīng)典算法在社區(qū)評價標(biāo)準(zhǔn)上的對比分析。

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

選取包括Cora[23]、WebKB[24]、Wiki[24]和CiteSeer[23]在內(nèi)的12個真實的數(shù)據(jù)集，為簡化操作，把所有的數(shù)據(jù)集形成的網(wǎng)絡(luò)均看作無向圖。

WebKB是數(shù)據(jù)集包含了4所大學(xué)Cornell、Washington、Wisconsin和Texas計算機系5個類別的Web頁面，剔除重復(fù)節(jié)點和互引的重復(fù)邊，實驗中共用到859個節(jié)點，1 388條邊之間的引用關(guān)系。

Cora數(shù)據(jù)集是引文網(wǎng)絡(luò)，涉及9大領(lǐng)域，其中有標(biāo)注的文獻(xiàn)30 144篇，引用關(guān)系714 266條，分別提取了Information Retrieval、Data Structure、Network、Programming、Database、Machine Learning共6個領(lǐng)域的文獻(xiàn)及其引文關(guān)系，并剔除內(nèi)容屬性為空或重復(fù)的節(jié)點及其引用關(guān)系，構(gòu)成最終的數(shù)據(jù)集。

Wiki數(shù)據(jù)集包括2009年10月7日至21日期間出現(xiàn)在屬性列表中的維基百科中的文檔，這些文檔涉及19個類別，文檔之間的超鏈接構(gòu)成了網(wǎng)絡(luò)的連邊。

CiteSeer數(shù)據(jù)集是計算科學(xué)領(lǐng)域的引文網(wǎng)絡(luò)，與Cora相同，節(jié)點表示文獻(xiàn)，文獻(xiàn)涉及6個子領(lǐng)域。該數(shù)據(jù)集具有438個獨立的連通子圖，節(jié)點的平均度為2.78，明顯有別于常見引文網(wǎng)絡(luò)。

上述數(shù)據(jù)集的基本統(tǒng)計信息如表3所示。

實驗預(yù)處理階段，對節(jié)點的文本內(nèi)容進(jìn)行LDA主題建模，為便于處理，將所有的數(shù)據(jù)集的主題數(shù)均設(shè)為30。

5.2 膨脹因子的取值分析

與MCL聚類算法相同，simInfLPA中膨脹因子的取值越大，算法收斂的速度越快，但是膨脹因子越大，形成社區(qū)的規(guī)模越小。為了驗證膨脹因子的取值對社區(qū)的模塊度和純度的影響，本文選用了Cora中的Information Retrieval、Data Structure以及Web-KB中的Texas數(shù)據(jù)集對膨脹因子的取值進(jìn)行分析。實驗中，膨脹因子共取了12個值，包括1到10，考慮到膨脹因子在區(qū)間[1,2]中的取值敏感性，本實驗增加膨脹因子取1.2和1.5的驗證，實驗結(jié)果如圖3所示。

Table 3 Statistical information of datasets表3 各數(shù)據(jù)集統(tǒng)計信息

從圖3中可以看出，針對社區(qū)結(jié)構(gòu)比較明顯的網(wǎng)絡(luò)結(jié)構(gòu)，像引文網(wǎng)絡(luò)Information Retrieval和Data Structure，如圖3（a）和圖3（c）所示，膨脹因子在1附近取值，社區(qū)模塊度即可達(dá)到最優(yōu)值，社區(qū)模塊度則隨膨脹因子增加呈逐漸下降的趨勢。而對Texas這樣類似星型網(wǎng)絡(luò)結(jié)構(gòu)，當(dāng)膨脹因子取值較小時，sim-InfLPA算法檢測出來的社區(qū)結(jié)構(gòu)并不明顯，增加膨脹因子可提升社區(qū)模塊度，如圖3（e）所示；當(dāng)膨脹因子小于4時，檢測出來的社區(qū)模塊度小于0.3，社區(qū)特征不明顯；當(dāng)膨脹因子大于4時，社區(qū)模塊度則隨膨脹因子的增加而緩慢增加。

在實際應(yīng)用中，膨脹因子的取值影響了社區(qū)模塊度的大小，需根據(jù)不同的網(wǎng)絡(luò)結(jié)構(gòu)選擇合適的膨脹因子。但從實驗結(jié)果分析來看，膨脹因子的取值對社區(qū)純度的影響甚微，如圖3（b）、（d）和（f）所示。膨脹因子小于2時，檢測出的社區(qū)純度有所波動；當(dāng)膨脹因子大于2以后，任意網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)純度都緩慢增加趨于穩(wěn)定；當(dāng)膨脹因子大于4以后，社區(qū)純度對膨脹因子的取值不敏感，算法在膨脹因子的參數(shù)取值上具有魯棒性。綜合算法性能和膨脹因子對社區(qū)質(zhì)量的影響，在實驗中，統(tǒng)一將膨脹因子取值為4。

Fig.3 Results of 3 datasets with varying inflation factor圖3 3個數(shù)據(jù)集中膨脹因子取值分析

5.3 不同標(biāo)簽傳播策略的分析

LabelRank是以觀測到鄰居節(jié)點的概率進(jìn)行標(biāo)簽傳播，simLPA是以節(jié)點對之間的內(nèi)容相似程度為概率進(jìn)行標(biāo)簽傳播，simInfLPA是以節(jié)點對之間的傳播強度為概率進(jìn)行標(biāo)簽傳播。本組選取了Cora中6個領(lǐng)域的數(shù)據(jù)集和Wiki數(shù)據(jù)集，驗證了不同的標(biāo)簽傳播方式對在語義社區(qū)度量指標(biāo)上的區(qū)別。在實驗中，膨脹因子In取4，q取0.6，r取0.1，實驗結(jié)果如圖4和圖5所示。

Fig.4 Comparison of modularity for different label propagation strategies圖4 不同標(biāo)簽傳播策略檢測出社區(qū)的模塊度比較

Fig.5 Comparison of purity for different label propagation strategies圖5 不同標(biāo)簽傳播策略檢測出社區(qū)的純度比較

從圖4所示的實驗結(jié)果可以看出，在社區(qū)結(jié)構(gòu)緊密度上，LabelRank算法檢測出來的社區(qū)在模塊度的度量指標(biāo)上整體要優(yōu)于simLPA和simInfLPA，而simLPA檢測出的社區(qū)模塊度最低。因增加了傳播影響力，simInfLPA則在simLPA的基礎(chǔ)上提升了模塊度，接近LabelRank的社區(qū)檢測效果。在一些網(wǎng)絡(luò)結(jié)構(gòu)上，如Information Retrieval和Machine Learning數(shù)據(jù)集，社區(qū)模塊度的質(zhì)量甚至優(yōu)于LabelRank的檢測效果。

從圖5的實驗結(jié)果可以看出，在社區(qū)語義一致性上，simLPA算法檢測出來的社區(qū)在純度的度量指標(biāo)上性能最好，LabelRank性能最差，simInfLPA的性能則均優(yōu)于LabelRank方法，普遍接近simLPA的檢測效果。在一些網(wǎng)絡(luò)結(jié)構(gòu)上，如Network和Machine Learning數(shù)據(jù)集，社區(qū)純度的質(zhì)量甚至優(yōu)于simLPA的檢測效果。

綜合圖4和圖5所示的實驗結(jié)果可以看出，在標(biāo)簽傳播過程中，僅考慮節(jié)點的鏈接屬性，發(fā)現(xiàn)的社區(qū)在語義一致性上性能較差；僅考慮節(jié)點對內(nèi)容相似性，易打散網(wǎng)絡(luò)結(jié)構(gòu)，形成的社區(qū)較為松散；綜合節(jié)點的內(nèi)容相似性和傳播影響力，即考慮傳播強度，有助于平衡社區(qū)的緊密性和語義一致性，具有好的語義社區(qū)的檢測效果。

5.4 算法性能分析

本實驗選取了Wisconsin、Data Structure和Machine Learning數(shù)據(jù)集進(jìn)行測試，通過比較simInfLPA和LabelRank算法的迭代運行時間來分析simInfLPA算法是否因標(biāo)簽傳播過程中增加了節(jié)點的語義相似度和傳播影響力而增加了標(biāo)簽算法的運行復(fù)雜度。

因LabelRank算法的運行效率和膨脹因子In的取值有關(guān)，針對每個數(shù)據(jù)集，測試了膨脹因子In在區(qū)間[1,10]中取不同值時LabelRank和simInfLPA的迭代收斂時間，具體的實驗結(jié)果如圖6所示。

Fig.6 Running time with variation of inflation factor圖6 不同膨脹因子取值時算法運行時間比較

從實驗結(jié)果來看，相對LabelRank而言，simInf-LPA引入的節(jié)點的傳播強度，沒有增加算法運行的復(fù)雜度，在多數(shù)情況下還加速了算法的收斂，且算法迭代收斂時間趨于穩(wěn)定，受膨脹因子的影響較小，具有魯棒性。

5.5 信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的經(jīng)典算法比較分析

本實驗在表2所示的全體數(shù)據(jù)集上，選取了標(biāo)簽傳播算法LPA[9]、馬爾科夫隨機游走算法WalkTrap[10]、基于模塊度最大化的快速貪心算法[2]、穩(wěn)定標(biāo)簽傳播算法LabelRank[20]、文本聚類K-Means算法與simInfLPA算法進(jìn)行對比，分析語義社區(qū)的劃分質(zhì)量。實驗中，LPA算法運行10次，社區(qū)質(zhì)量的度量指標(biāo)取10次運行結(jié)果的平均值。WalkTrap中步長設(shè)置為4。KMeans聚類算法中的K值分別設(shè)置為每組數(shù)據(jù)集中真實的類別個數(shù)，如Data Structure數(shù)據(jù)集中K設(shè)為9。K-Means算法因不適于模塊度的度量，本實驗中僅進(jìn)行社區(qū)純度度量。在LabelRank和simInfLPA算法中，r取0.1，In取4，q取0.6。

從表4和表5中可以看出，simInfLPA在模塊度的指標(biāo)上，性能略差于基于拓?fù)浣Y(jié)構(gòu)的社區(qū)發(fā)現(xiàn)方法，但依然保證了語義社區(qū)鏈接緊密的結(jié)構(gòu)特性。在純度的指標(biāo)上，除CiteSeer數(shù)據(jù)集，simInfLPA算法的性能都優(yōu)于單純的基于拓?fù)浣Y(jié)構(gòu)和單純基于內(nèi)容的社區(qū)發(fā)現(xiàn)算法。而在CiteSeer數(shù)據(jù)集上性能較差，因為該數(shù)據(jù)集缺失鏈嚴(yán)重，而simInfLPA中的傳播強度采用乘性模型無法有效處理缺失鏈較多的網(wǎng)絡(luò)。

Table 4 Comparison of different community detection algorithms on modularity metric表4 不同算法在社區(qū)模塊度上的比較結(jié)果

Table 5 Comparison of different community detection algorithms in purity metric表5 不同算法在社區(qū)純度上的比較結(jié)果

5.6 實驗總結(jié)

從上述四方面實驗分析，得到如下結(jié)論：

（1）simInfLPA算法中，膨脹因子的取值對社區(qū)模塊度有影響，對社區(qū)純度影響甚微，考慮語義社區(qū)的特征，膨脹因子可設(shè)置為4。

（2）simLPA用節(jié)點對的內(nèi)容相似度指導(dǎo)標(biāo)簽傳播，可以極大地提高社區(qū)的純度，卻降低了社區(qū)的模塊度指標(biāo)。

（3）simInfLPA兼顧了社區(qū)模塊度和純度兩個指標(biāo)，更適合語義社區(qū)的發(fā)現(xiàn)。

（4）在面向信息網(wǎng)絡(luò)進(jìn)行語義社區(qū)發(fā)現(xiàn)時，sim-InfLPA相對于經(jīng)典的基于拓?fù)浣Y(jié)構(gòu)和基于內(nèi)容的方法更有效。

（5）simInfLPA在標(biāo)簽傳播過程增加了節(jié)點對的內(nèi)容相似度和傳播影響力的因素，并沒有增加原始標(biāo)簽傳播算法的復(fù)雜度。

（6）對各類型的信息網(wǎng)絡(luò)，除缺失鏈接較多的情況外，simInfLPA具有普適性。

6 結(jié)束語

在大規(guī)模信息網(wǎng)絡(luò)的語義社區(qū)發(fā)現(xiàn)研究中，為解決節(jié)點內(nèi)容屬性維數(shù)災(zāi)難和融合節(jié)點內(nèi)容屬性增加算法復(fù)雜度兩個挑戰(zhàn)，采用LDA主題模型表示節(jié)點屬性內(nèi)容可以有效地降低節(jié)點的內(nèi)容屬性維數(shù)，利用線性時間的標(biāo)簽傳播算法可以有效地控制算法的整體復(fù)雜度。本文在穩(wěn)定的標(biāo)簽傳播算法Label-Rank的基礎(chǔ)上，用LDA主題模型表示節(jié)點的內(nèi)容屬性，融合節(jié)點的內(nèi)容相似度和節(jié)點在網(wǎng)絡(luò)中的影響力，改進(jìn)了節(jié)點標(biāo)簽的傳播策略，引入了標(biāo)簽的傳播強度，有效地融合了節(jié)點的內(nèi)容屬性特征和節(jié)點之間的鏈接結(jié)構(gòu)特征，可以發(fā)現(xiàn)結(jié)構(gòu)緊密且內(nèi)容一致的語義社區(qū)。同時與原始LabelRank算法相比，標(biāo)簽傳播強度的引入，并沒有增加算法復(fù)雜度，算法迭代只和節(jié)點的局部信息有關(guān)，可采用并行計算，適用于大規(guī)模的網(wǎng)絡(luò)。

但標(biāo)簽傳播需要依據(jù)網(wǎng)絡(luò)原始的拓?fù)浣Y(jié)構(gòu)，傳播的前提是節(jié)點之間有鏈接，本文利用乘法模型計算標(biāo)簽傳播強度并沒有很好處理節(jié)點之間鏈接缺失的情況，采用加法模型可避免缺失鏈帶來的噪聲，但如何設(shè)置調(diào)節(jié)加權(quán)參數(shù)是今后進(jìn)一步研究的方向。

[1]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69 (2):026113.

[2]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6): 066133.

[3]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.

[4]Newman M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582.

[5]Massen C P,Doye J P K.Identifying communities within energy landscapes[J].Physical Review E,2005,71(4):046101.

[6]Donetti L.Detecting network communities:a new systematic and efficient algorithm[J].Journal of Statistical Mechanics: Theory and Experiment,2004,10:P10012.

[7]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 Jose,USA,Aug 12-15,2007.New York:ACM,2007:824-833.

[8]Zhang Peng,Wang Jinliang,Li Xiaojia,et al.Clustering coefficient and community structure of bipartite networks[J]. Physical A:Statistical Mechanics and its Applications, 2008,387(27):6869-6875.

[9]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.

[10]Pons P,Latapy M.Computing communities in large networks using random walks[J].Physical Review Letters, 2004,92(11):118701.

[11]Hastings M B.Community detection as an inference problem[J].Physical Review E,2006,74(3):035102.

[12]Karrer B,Newman M E J.Stochastic blockmodels and community structure in networks[J].Physical Review E,2011, 83(1):016107.

[13]Newman M E J.Detecting community structure in networks [J].The European Physical Journal B-Condensed Matterand Complex Systems,2004,38(2):321-330.

[14]Nguyen T,Phung D,Adams B,et al.Hyper-community detection in the blogosphere[C]//Proceedings of the 2nd ACM SIGMM Workshop on Social Media,Firenze,Italy,Oct 25-29,2010.New York:ACM,2010:21-26.

[15]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.

[16]Xin Yu,Yang Jing,Xie Zhiqiang.A semantic overlapping community detecting algorithm in social networks based on random walk[J].Journal of Computer Research and Development,2015,52(2):499-511.

[17]Yang Tianbao,Jin Rong,Chi Yun,et al.Combining link and content for community detection:a discriminative approach [C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Pairs,Jun 28-Jul 1,2009.New York:ACM,2009:927-936.

[18]Blei D M,Ng A Y,Jordan M I.Latent Dirichlet allocation[J]. Journal of Machine Learning Research,2003,3:993-1022.

[19]Galligan M C,Saldova R,Campbell M P,et al.Greedy feature selection for glycan chromatography data with the generalized Dirichlet distribution[J].BMC Bioinformatics,2013, 14(1):155.

[20]Xie Jierui,Szymanski B K.LabelRank:a stabilized label propagation algorithm for community detection in networks [C]//Proceedings of the 2nd IEEE International Workshop on Network Science,New York,Apr 31-May 1，2013.Piscataway,USA:IEEE,2013:138-143.

[21]Sabidussi G.The centrality index of a graph[J].Psychometrika,1966,31(4):581-603.

[22]Strehl A,Ghosh J,Mooney R.Impact of similarity measures on Web-page clustering[C]//Proceedings of the 17th National Conference on Artificial Intelligence,Austin,USA,Jul 30-Aug 3,2000.Menlo Park,USA:AAAI,2000:58-64.

[23]Cora research paper classification[EB/OL].(2015-04-13) [2016-01-07].http://www.datatang.com/data/28850.

[24]LINQS[EB/OL].(2015-10-12)[2016-01-07].http://linqs. umiacs.umd.edu/projects/projects/lbc/index.html.

附中文參考文獻(xiàn)：

[16]辛宇,楊靜,謝志強.基于隨機游走的語義重疊社區(qū)發(fā)現(xiàn)算法[J].計算機研究與發(fā)展,2015,52(2):499-511.

SHEN Guilan was born in 1979.She is a Ph.D.candidate at Renmin University,associate professor at Beijing Union University,and the member of CCF.Her research interests include semantic community detection and Web text mining,etc.

沈桂蘭（1979—），女，河南信陽人，中國人民大學(xué)信息學(xué)院博士研究生，北京聯(lián)合大學(xué)副教授，CCF會員，主要研究領(lǐng)域為語義社區(qū)發(fā)現(xiàn)，Web文本挖掘等。

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

賈彩燕（1976—），女，湖南人，2004年于中國科學(xué)院計算技術(shù)研究所獲得博士學(xué)位，現(xiàn)為北京交通大學(xué)副教授、博士生導(dǎo)師，主要研究領(lǐng)域數(shù)據(jù)挖掘，復(fù)雜網(wǎng)絡(luò)分析，生物信息學(xué)等。

YU Jian was born in 1969.He received the Ph.D.degree from Peking University in 2000.Now he is a professor and Ph.D.supervisor at Beijing Jiaotong University.His research interests include machine learning,computational intelligence and data mining,etc.

于劍（1969—），男，山東人，2000年于北京大學(xué)獲得博士學(xué)位，現(xiàn)為北京交通大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域為機器學(xué)習(xí)，計算智能，數(shù)據(jù)挖掘等。

YANG Xiaoping was born in 1956.He received the Ph.D.degree from Renmin University in 2003.Now he is a professor and Ph.D.supervisor at Renmin University.His research interests include Web text mining,E-government and information system engineering,etc.

楊小平（1956—），男，福建福州人，2003年于中國人民大學(xué)獲得博士學(xué)位，現(xiàn)為中國人民大學(xué)信息學(xué)院教授、博士生導(dǎo)師，主要研究領(lǐng)域為Web文本挖掘，電子政務(wù)，信息系統(tǒng)工程等。

Semantic Community DetectionAlgorithm for Large Scale Information Network*

SHEN Guilan1,2+,JIACaiyan3,YU Jian3,YANG Xiaoping2
1.Business School,Beijing Union University,Beijing 100025,China
2.School of Information,Remin University,Beijing 100087,China
3.School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China
+Corresponding author:E-mail:s_gl@163.com

Information network is a kind of complex network with semantic information.The semantic community detection of information network is a new research direction.The complexity of community detection algorithm is increased by considering the node content.Therefore this paper proposes a label propagation algorithm which is suitable for dealing with large scale information network in linear time.Firstly,the latent Dirichlet allocation topic model is used to represent the node content.Secondly,the multiplicative model of content similarity and propagation influence is taken as the label propagation strategy.And the content and the network topology are combined naturally in the normalization.Thirdly,the algorithm updates the node label while the node and the vast majority of neighbors are not the same.Extensive experiments on 12 real-world datasets with varying sizes and characteristics validate the proposed method outperforms other baseline algorithms in quality.

semantic community detection;latent Dirichlet allocation topic model;content similarity;label propa-gation strategy;influence propagation

10.3778/j.issn.1673-9418.1603050

A

TP181；TP391.1

*The National Natural Science Foundation of China under Grant Nos.71572015,71271209(國家自然科學(xué)基金);the New Start Project of Beijing Union University under Grant No.Zk10201506(北京聯(lián)合大學(xué)新起點項目).

Received 2016-02,Accepted 2016-04.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-04-28,http://www.cnki.net/kcms/detail/11.5602.TP.20160428.0914.004.html

SHEN Guilan,JIA Caiyan,YU Jian,et al.Semantic community detection algorithm for large scale information network.Journal of Frontiers of Computer Science and Technology,2017,11(4)：565-576.