劉發(fā)升，劉艷軍，葛海明/

（江西理工大學(xué)信息工程學(xué)院 贛州341000）

1 引言

近年來(lái)，數(shù)據(jù)挖掘一直是科學(xué)研究中非常重要的領(lǐng)域，尤其在這個(gè)海量數(shù)據(jù)時(shí)代。目前，在數(shù)據(jù)挖掘領(lǐng)域，分析復(fù)雜網(wǎng)絡(luò)[1]的結(jié)構(gòu)成為研究的熱點(diǎn)，發(fā)現(xiàn)社區(qū)結(jié)構(gòu)對(duì)于企業(yè)或者科研工作來(lái)說(shuō)都具有重要意義。社交網(wǎng)絡(luò)是一種從現(xiàn)實(shí)社會(huì)中抽象出來(lái)的復(fù)雜網(wǎng)絡(luò)，遵循小世界理論[2]、服從冪律分布[3]并且可以對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社區(qū)劃分。在線用戶社交網(wǎng)絡(luò)改變了用戶間的交流方式，影響了社會(huì)互動(dòng)，微博網(wǎng)絡(luò)是社交網(wǎng)絡(luò)的典型代表。微博（Weibo）是Web 2.0技術(shù)的標(biāo)志性產(chǎn)物，是以用戶間的關(guān)系為橋梁，將用戶創(chuàng)造的數(shù)據(jù)以文本、圖片、視頻等方式對(duì)外傳播來(lái)進(jìn)行交流溝通。微博網(wǎng)絡(luò)具有文本內(nèi)容簡(jiǎn)明扼要、用戶可實(shí)時(shí)交互并且關(guān)系結(jié)構(gòu)稀疏等特點(diǎn)。國(guó)外著名的社交網(wǎng)站Twitter、Facebook以及國(guó)內(nèi)的新浪微博、騰訊微博均擁有龐大的用戶群。根據(jù)2014年7月 《第34次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》可知，我國(guó)網(wǎng)民數(shù)量達(dá)6億多，手機(jī)網(wǎng)民數(shù)量達(dá)5億多，并且微博平臺(tái)的用戶增長(zhǎng)率仍然處于領(lǐng)先地位。以新浪微博為例，截至2014年9月，微博月活躍用戶數(shù)達(dá)1.67億。如今，微博已經(jīng)成為人們網(wǎng)絡(luò)生活中獲取新聞熱點(diǎn)、娛樂生活等必不可少的網(wǎng)絡(luò)媒體。通過(guò)分析微博網(wǎng)絡(luò)中用戶的行為特征和相互關(guān)系，找出興趣相投的用戶社區(qū)，成為社交網(wǎng)絡(luò)在數(shù)據(jù)挖掘領(lǐng)域研究的重點(diǎn)。

社區(qū)是社交網(wǎng)絡(luò)結(jié)構(gòu)中一種重要的屬性，目前對(duì)于社區(qū)并沒有統(tǒng)一的定義，研究學(xué)者普遍認(rèn)為社區(qū)內(nèi)部節(jié)點(diǎn)聯(lián)系較為緊密，外部節(jié)點(diǎn)聯(lián)系較為稀疏[4]。在復(fù)雜網(wǎng)絡(luò)的研究中，網(wǎng)絡(luò)結(jié)構(gòu)通常被抽象為圖模型表示G={V,E}，其中，V={v1,v2,…,vn}表示節(jié)點(diǎn)集合，E={e1,e2,…,em}表示邊的集合。在具體的網(wǎng)絡(luò)中，V表示為網(wǎng)絡(luò)實(shí)體的集合，E表示為實(shí)體之間關(guān)系的集合。例如，在微博網(wǎng)絡(luò)中，V表示微博用戶的集合，E表示不同用戶之間的關(guān)注關(guān)系。

傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法研究中，將微博作為客體對(duì)象較少，近幾年對(duì)于微博網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的研究一般分為3種方法。

（1）基于用戶結(jié)構(gòu)

用戶網(wǎng)絡(luò)結(jié)構(gòu)包括用戶之間的關(guān)注或者好友關(guān)系，此類方法是通過(guò)將用戶結(jié)構(gòu)抽象為圖論等問(wèn)題進(jìn)行社區(qū)發(fā)現(xiàn)。參考文獻(xiàn)[4]通過(guò)采集微博用戶原生指標(biāo)和構(gòu)造指標(biāo)信息，利用派系過(guò)濾算法對(duì)用戶行為相似度進(jìn)行聚類，進(jìn)而發(fā)現(xiàn)用戶社區(qū)。參考文獻(xiàn)[5]通過(guò)用戶關(guān)系緊密度構(gòu)造微博無(wú)向加權(quán)圖，根據(jù)加權(quán)算法發(fā)現(xiàn)微博社區(qū)。該類方法沒有考慮用戶興趣特征，僅通過(guò)用戶間關(guān)系發(fā)現(xiàn)社區(qū)，無(wú)法體現(xiàn)用戶興趣對(duì)社區(qū)的重要性。事實(shí)上，即使沒有直接關(guān)系相連的兩個(gè)用戶，若他們發(fā)布的內(nèi)容相似，這兩個(gè)用戶在很大程度上可能擁有相似的興趣并且應(yīng)該被加入到同一個(gè)社區(qū)中。

（2）基于用戶內(nèi)容

此類方法一般采用提取用戶在網(wǎng)絡(luò)中發(fā)布的微博文本內(nèi)容以及用戶行為等特征屬性，來(lái)比較用戶興趣相似度，通過(guò)相似度計(jì)算公式將用戶進(jìn)行劃分。參考文獻(xiàn)[6]將用戶對(duì)地理位置和社區(qū)的選擇偏好引入到時(shí)空主題模型中發(fā)現(xiàn)用戶社區(qū)。參考文獻(xiàn)[7]采集用戶標(biāo)簽信息，將其使用頻率和稀疏度作為用戶興趣進(jìn)行聚類形成社區(qū)。該類方法沒有考慮到用戶關(guān)系在數(shù)據(jù)傳播中的橋梁作用，顯性的好友關(guān)系對(duì)社區(qū)發(fā)現(xiàn)起到重要的作用。

（3）基于用戶結(jié)構(gòu)和內(nèi)容的綜合方法

此類方法的一般流程是提取基于用戶結(jié)構(gòu)的微博社區(qū)以及基于用戶興趣的微博用戶社區(qū)，然后采用某種聚類算法將兩種社區(qū)進(jìn)行融合。參考文獻(xiàn)[8]分析用戶關(guān)系和微博主題，通過(guò)相似度公式計(jì)算節(jié)點(diǎn)間的傳遞概率，利用標(biāo)簽傳遞算法發(fā)現(xiàn)社區(qū)。參考文獻(xiàn)[9]利用關(guān)注關(guān)系為節(jié)點(diǎn)將用戶和文本內(nèi)容融合來(lái)發(fā)現(xiàn)社區(qū)。

一般來(lái)說(shuō)，朋友之間更有可能分享相同的興趣?；谶@樣的原則，在推薦系統(tǒng)的研究中，較為準(zhǔn)確的推薦往往會(huì)綜合考慮用戶的好友關(guān)系和生成內(nèi)容。同樣，在文檔檢索（Document Retrieval）和文檔分類（Document Classification）中也經(jīng)常運(yùn)用。如此便說(shuō)明這一原則在多關(guān)系網(wǎng)絡(luò)中具有實(shí)際意義，因此，該原則對(duì)于微博網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)也同樣適用。

根據(jù)用戶關(guān)系和內(nèi)容對(duì)發(fā)現(xiàn)社區(qū)的重要性，本文采用適合微博網(wǎng)絡(luò)的主題模型生成用戶興趣特征，利用JS距離（Jensen-Shannon Divergence）公式計(jì)算用戶的興趣相似度，并在CNM算法的基礎(chǔ)上提出一種改進(jìn)的JSCNM算法。該算法將用戶興趣主題和用戶關(guān)系進(jìn)行融合以取代模塊度增量對(duì)微博網(wǎng)絡(luò)的凝聚。最后在真實(shí)數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)用戶社區(qū)。

2 相關(guān)術(shù)語(yǔ)

2.1 微博網(wǎng)絡(luò)結(jié)構(gòu)

國(guó)內(nèi)較為著名的社交網(wǎng)絡(luò)有新浪微博（Sina Weibo）、 騰訊微博 （Tencent Weibo）、 人人網(wǎng)（Renren）、豆瓣（Douban）等。 以新浪微博為例，每一個(gè)微博用戶允許發(fā)表不超過(guò)140字的微博文本，可包含表情、圖片、視頻、話題等內(nèi)容。興趣相投的不同用戶之間可以在不必告知對(duì)方的情況下彼此關(guān)注或者單方面關(guān)注。也就是說(shuō)，一個(gè)用戶可以關(guān)注其他用戶，同時(shí)也可以被其他用戶所關(guān)注。用戶可以轉(zhuǎn)發(fā)其他用戶的微博。圖1為微博的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)。

微博網(wǎng)絡(luò)用圖模型G=（V,E）表示，其中，V表示在微博網(wǎng)絡(luò)中所有節(jié)點(diǎn)類型的集合，E表示在節(jié)點(diǎn)V之間有聯(lián)系的邊的集合。如圖1所示，所有節(jié)點(diǎn)類型集合V可以表示為V={U,C,W,R}={,,,}，其中，Ui（i=1,2,3）表示微博用戶，Cj（j=1,2,3,4）表示用戶發(fā)布的微博內(nèi)容，Wk（k=1,2,3）表示組成用戶發(fā)布的微博內(nèi)容的詞語(yǔ)序列，R1和R2分別表示用戶U2和U3評(píng)論且轉(zhuǎn)發(fā)U1和U2的微博C1和C3的行為。邊集合E={,…,,…,,…}表示用戶—用戶之間、用戶—內(nèi)容之間以及內(nèi)容—詞語(yǔ)之間的聯(lián)系。表示用戶U1被U2關(guān)注，表示用戶U1發(fā)布的微博內(nèi)容C1，表示微博內(nèi)容C1由詞語(yǔ)W1構(gòu)成。在用戶關(guān)系中，存在一個(gè)子圖G′=，其中，Eu={,,}，這說(shuō)明微博網(wǎng)絡(luò)中用戶之間的關(guān)注關(guān)系是有方向的。

2.2 模塊度

模塊度Q（Modularity）[10]是Newman提出的用于識(shí)別社區(qū)劃分結(jié)果好壞的度量標(biāo)準(zhǔn)。模塊度定義為每個(gè)社區(qū)內(nèi)部的連接數(shù)與維持度序列不變的隨機(jī)化網(wǎng)絡(luò)的期望連接數(shù)的差值的累加和。換言之，模塊度較高的網(wǎng)絡(luò)社區(qū)內(nèi)連接比隨機(jī)化網(wǎng)絡(luò)更密集。假設(shè)一個(gè)網(wǎng)絡(luò)劃分成多個(gè)社區(qū)，可以用式（1）判斷它是否為一個(gè)好的劃分。

針對(duì)上述不足之處，模塊度在CNM算法[11]中得到優(yōu)化，有

其中，ki表示節(jié)點(diǎn)i的度大小。

實(shí)驗(yàn)表明，網(wǎng)絡(luò)擁有社區(qū)結(jié)構(gòu)的模塊度值范圍為0.3～0.7。一般來(lái)說(shuō)，當(dāng)模塊度值大于0.3時(shí)，就可以看作是一個(gè)好的社區(qū)劃分。經(jīng)過(guò)實(shí)驗(yàn)證明，模塊度仍然存在一些不足之處，比如存在過(guò)擬合現(xiàn)象以及有限分辨率的現(xiàn)象等。盡管如此，目前尚未存在其他更好的度量方法能夠像模塊度函數(shù)一樣，在發(fā)現(xiàn)社區(qū)結(jié)構(gòu)劃分的同時(shí)確定社區(qū)的數(shù)目。通過(guò)對(duì)模塊度進(jìn)行優(yōu)化來(lái)更加有效地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)仍具有重要的研究意義。

2.3 相似度中心性

用戶興趣相似度是指不同用戶對(duì)某一事物感興趣或者喜好的程度。在微博網(wǎng)絡(luò)中，用戶興趣相似度表示為用戶發(fā)布的微博內(nèi)容之間相關(guān)聯(lián)的程度，因?yàn)橛脩舭l(fā)布的內(nèi)容可以彰顯用戶當(dāng)時(shí)的喜好。用戶相似度中心性是指某一用戶節(jié)點(diǎn)和其所有鄰居節(jié)點(diǎn)相似度的總和。用戶相似度中心性計(jì)算公式為

其中，Sim（i,j）表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的興趣相似度，n表示網(wǎng)絡(luò)中用戶總數(shù)。一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多，它的中心度越大。表示整個(gè)網(wǎng)絡(luò)中所有用戶節(jié)點(diǎn)的中心度總和。

3 相關(guān)算法簡(jiǎn)介

3.1 CNM算法

CNM算法[11]是Newman提出的基于貪婪思想的快速社區(qū)發(fā)現(xiàn)算法，通過(guò)不斷優(yōu)化模塊度函數(shù)進(jìn)行凝聚來(lái)實(shí)現(xiàn)對(duì)社區(qū)的劃分，該算法的思想是通過(guò)迭代發(fā)現(xiàn)由合并每一對(duì)社區(qū)引起的模塊度增量的變化，并利用這個(gè)變換的最大值，來(lái)合并擁有最大變化值的社區(qū)。在算法執(zhí)行過(guò)程中，由于模塊度增量矩陣和對(duì)應(yīng)的社區(qū)編號(hào)都采用高效的最大堆數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，使得最大模塊度增量和對(duì)應(yīng)的社區(qū)信息可以在常數(shù)時(shí)間內(nèi)獲取，其時(shí)間復(fù)雜度接近線性值O（n log2n）。故該算法是第一個(gè)適合較大規(guī)模網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法。雖然目前存在多個(gè)優(yōu)秀的相關(guān)算法，但是CNM算法是唯一一個(gè)從全局角度考慮社區(qū)合并、直接有效地優(yōu)化模塊度的快速算法。

為了運(yùn)算方便，CNM算法定義了兩個(gè)變量，即eij和ai，表達(dá)式分別為

式（4）分別表示社區(qū)i和社區(qū)j內(nèi)部邊的總數(shù)占網(wǎng)絡(luò)中全部邊的總數(shù)的比值以及社區(qū)i內(nèi)部節(jié)點(diǎn)關(guān)聯(lián)的全部邊的總數(shù)占網(wǎng)絡(luò)中全部邊的總數(shù)的比值。

CNM算法定義以下3種類型矩陣：存儲(chǔ)模塊度增量ΔQ的稀疏矩陣；最大堆H；存儲(chǔ)向量ai的常規(guī)矩陣。

算法基本流程如下。

①初始化。將網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)視為一個(gè)社區(qū)，利用公式初始化ΔQ和ai。

在算法剛開始時(shí)，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有邊相連，則eij=1/2m；如果沒有邊相連，則eij=0,ai=ki/2m。模塊度增量的值為

②初始化最大堆H。將ΔQ矩陣每列中的最大值寫入到H中。

③遍歷H中的最大值ΔQij，將社區(qū)i和社區(qū)j根據(jù)合并原則進(jìn)行合并，標(biāo)記為社區(qū)i，并更新ΔQ和H中行和列的值以及輔助向量ai的值。

當(dāng)社區(qū)i和社區(qū)j合并到社區(qū)i時(shí)，需要?jiǎng)h除社區(qū)j對(duì)應(yīng)的行和列的值，合并規(guī)則定義如下

更新后的輔助向量ai的值為ai′=ai+aij，aj=0。記錄更新后的模塊度Q的值為Q=Q+ΔQ。

④重復(fù)步驟②和③，直到所有的節(jié)點(diǎn)歸到一個(gè)社區(qū)，算法結(jié)束。由于模塊度增量矩陣和對(duì)應(yīng)的社區(qū)編號(hào)都用最大堆數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，因此可以在常數(shù)時(shí)間內(nèi)獲取數(shù)據(jù)，更新和刪除操作可以很快地完成。當(dāng)ΔQ全為負(fù)數(shù)時(shí)，模塊度值下降，這個(gè)過(guò)程中會(huì)出現(xiàn)峰值，也就能得到社區(qū)最優(yōu)的劃分。模塊度值大于0.3就可以看作是一個(gè)好的社區(qū)劃分。

3.2 主題模型LDA

主題模型是對(duì)自然語(yǔ)言進(jìn)行主題挖掘并能識(shí)別語(yǔ)義的語(yǔ)言模型。傳統(tǒng)的主題挖掘一般采用向量空間模型（Vector Space Model，VSM），將文本表示為特征項(xiàng)集，利用余弦公式計(jì)算文本間的相似度，聚類結(jié)果往往只能區(qū)分類別，不能進(jìn)行語(yǔ)義識(shí)別。例如，“喬布斯離我們而去了”和“蘋果價(jià)格會(huì)不會(huì)下降”這兩個(gè)句子在文本上沒有相似之處，但是在語(yǔ)義上是相關(guān)的。傳統(tǒng)的計(jì)算文本相似度發(fā)現(xiàn)方法無(wú)法解決文本挖掘中的語(yǔ)義問(wèn)題，但是主題模型能夠識(shí)別。

LDA[12]（Latent Dirichlet Allocation）是眾多主題模型算法中較為經(jīng)典的一個(gè)。LDA是Blei等人提出的能夠識(shí)別大規(guī)模文檔集或語(yǔ)料庫(kù)中潛在的主題信息的算法模型。它使用詞袋（Bag OfWords，BOW）方法，該方法將文檔視為詞語(yǔ)的集合，進(jìn)而構(gòu)成詞頻向量，最后將文本轉(zhuǎn)化成易于建模的數(shù)據(jù)。LDA模型思想是任意一篇文檔都是由若干個(gè)主題混合生成的，并且被表示為主題所構(gòu)成的一個(gè)概率多項(xiàng)分布。其中，每個(gè)主題都是一個(gè)基于文本詞語(yǔ)項(xiàng)的概率多項(xiàng)分布。

LDA是一個(gè)層次貝葉斯概率模型，由文檔（Doc）—主題（Topic）—詞語(yǔ)（Word）3層構(gòu)成，其含義是某一篇文檔中的詞以一定的概率選擇了某一主題，并從這一主題中再以一定的概率選擇某些詞語(yǔ)。生成一篇文檔中每個(gè)詞出現(xiàn)的概率為P(word|doc)=

詞語(yǔ)層：詞語(yǔ)集合W={w1,w2,…,wj}，是文檔集合中經(jīng)過(guò)預(yù)處理后的單詞集合。

主題層：主題集合={z1,z2,…,zk}，是基于詞語(yǔ)集W的概率多項(xiàng)分布，也可以表示為向量φk=（pk1,pk2,…,pkj），其中，pkj表示詞語(yǔ)wj在主題zk上的生成概率。

文檔層：對(duì)于詞語(yǔ)層來(lái)說(shuō)，文檔層使用詞袋方法，將每一個(gè)文檔表示成一個(gè)詞頻向量di=（tfi1,tfi2,…,tfij），其中，tfij表示詞語(yǔ)j在文檔i中出現(xiàn)的次數(shù)。對(duì)于主題層而言，文檔集合可表示成Θ={θ1,θ2,…,θd}，且每一篇文檔由一個(gè)向量 θd=（pd1,pd2,…,pdz）表示，其中，pdz是主題z在文檔d中的生成概率。

在LDA中，α表示文檔—主題多項(xiàng)分布的先驗(yàn)知識(shí)，β表示主題—單詞多項(xiàng)分布的先驗(yàn)知識(shí)，其中，α和β都服從狄利克雷分布。

LDA生成過(guò)程如下所示。

選擇參數(shù) φ～Dir（β）;

選擇參數(shù) θ～Dir（α）;

對(duì)于N個(gè)單詞中每一個(gè)單詞w:

選擇一個(gè)主題z～p（z|θ）;

選擇一個(gè)單詞w～p（w|z,φ）;

主題向量φ表示詞語(yǔ)在主題上的生成概率，服從狄利克雷分布。主題向量θ表示每個(gè)主題在文檔中出現(xiàn)的概率，也服從狄利克雷分布，該向量是非負(fù)歸一化向量。N表示要生成文檔的單詞總數(shù)，w表示第n個(gè)單詞。z表示要選擇的主題，p（z|θ）表示在給定θ的情況下，主題z的多項(xiàng)概率分布。p（w|z,φ）表示在選定一個(gè)主題z的情況下，該主題所對(duì)應(yīng)的單詞的多項(xiàng)概率分布。

由上述過(guò)程可知，LDA聯(lián)合概率分布表達(dá)式為

LDA模型中，θ表示文檔—主題 （doc-topic）的概率分布，φ表示主題—詞語(yǔ)（topic-word）的概率分布。這兩個(gè)參數(shù)是模型最終要得到的值，根據(jù)聯(lián)合概率分布公式，使用吉布斯（Gibbs Sampling）公式對(duì)其采樣并進(jìn)行求解。吉布斯采樣是一種馬爾可夫鏈—蒙特卡羅（MCMC）算法過(guò)程。步驟如下。

①初始化。通過(guò)將文檔中的所有單詞隨機(jī)賦予主題來(lái)構(gòu)造馬爾可夫鏈的初始狀態(tài)。

②求解下一個(gè)狀態(tài)。對(duì)每篇文檔Di的每個(gè)單詞wn進(jìn)行迭代，根據(jù)吉布斯公式計(jì)算當(dāng)前單詞的各個(gè)主題zn的概率p（zn=k|wn），k表示主題數(shù)；通過(guò)概率隨機(jī)采樣確定當(dāng)前的分配主題。

③迭代執(zhí)行步驟②，直到馬爾可夫鏈達(dá)到穩(wěn)定狀態(tài)。

吉布斯采樣表達(dá)式為

其中，zi表示第i個(gè)詞對(duì)應(yīng)的主題，┐i表示去除下標(biāo)為i的詞，表示除去當(dāng)前單詞項(xiàng)在第m篇文檔中單詞項(xiàng)所對(duì)應(yīng)的主題個(gè)數(shù)，表示除去當(dāng)前單詞項(xiàng)在第k個(gè)主題中產(chǎn)生單詞的個(gè)數(shù)。

吉布斯采樣過(guò)程結(jié)束后，文檔—主題（doc-topic）的概率分布θ以及主題—詞語(yǔ)（topic-word）的概率分布φ可由后驗(yàn)概率近似估算出來(lái)。

其中，變量解釋如式（7）所述。m表示文檔數(shù)，k表示主題數(shù)，t表示單詞數(shù)。

3.3 JS距離

JS距離[13]是在KL距離[14]的基礎(chǔ)上改進(jìn)的用于測(cè)量隨機(jī)變量的概率分布的相似度。KL距離是Kullback-Leibler差異（Kullback-Leibler Divergence）的簡(jiǎn)稱，它用于檢測(cè)在同一事件空間里兩個(gè)概率分布的差異情況。在本文中可以用于計(jì)算用戶相似度距離。假設(shè)P、Q表示兩個(gè)隨機(jī)變量的概率分布，用KL距離公式計(jì)算概率P和概率Q之間的距離為DKL（P||Q）。KL距離具有不對(duì)稱性、非負(fù)性的特點(diǎn)，DKL（P||Q）≠DKL（Q||P）≥0。 當(dāng)兩個(gè)概率分布完全相同，即P=Q時(shí)，DKL（P||Q）=0。

針對(duì)KL距離的不對(duì)稱特性，將KL公式改進(jìn)成JS距離公式，首先取兩個(gè)概率分布的平均值，分別利用KL公式計(jì)算兩個(gè)概率分布和其平均值的距離，再對(duì)距離之和求平均值，這樣可以更準(zhǔn)確地計(jì)算兩個(gè)概率分布的相似程度。JS距離和KL距離的計(jì)算公式分別為

其中，P、Q表示兩個(gè)隨機(jī)變量的概率分布，R是隨機(jī)變量P、Q的均值。

根據(jù)主題模型中用戶和主題之間的概率分布，利用JS距離計(jì)算方法，可以求出不同用戶之間的興趣相似度。其中，JS距離值越小，用戶主題之間的相似度越大，當(dāng)兩個(gè)對(duì)象具有相同的概率分布時(shí)，JS距離的值為0。JS距離的倒數(shù)表示用戶之間的相似度，則兩個(gè)用戶u1、u2之間的相似度可以表示為Sim

4 JSCNM算法在微博中的應(yīng)用

4.1 LDA在微博文本中的應(yīng)用

針對(duì)微博網(wǎng)絡(luò)自身的特點(diǎn)，如文本內(nèi)容短、噪聲數(shù)據(jù)多、數(shù)據(jù)稀疏而且數(shù)據(jù)具有多樣性，LDA在微博網(wǎng)絡(luò)中需要做些改進(jìn)以適應(yīng)真實(shí)網(wǎng)絡(luò)的需要。首先由于微博文本短的特點(diǎn)，采取將每個(gè)用戶的所有微博作為一個(gè)文檔集合對(duì)待，再根據(jù)用戶興趣隨著時(shí)間或在當(dāng)下社會(huì)熱點(diǎn)的改變而改變，將用戶內(nèi)容選擇最近時(shí)間的文檔集合。用戶標(biāo)簽是用戶在注冊(cè)時(shí)或在使用過(guò)程中添加的用來(lái)標(biāo)示自己身份或者興趣愛好的短文本數(shù)據(jù)，比如 “90后”、“學(xué)生”、“動(dòng)漫”等?！拔镆灶惥郏艘匀悍帧?，不管是在現(xiàn)實(shí)生活中還是在虛擬的社會(huì)網(wǎng)絡(luò)中，用戶往往更傾向于和自己身份相仿、興趣相似的用戶交流?；谶@種現(xiàn)象，對(duì)標(biāo)簽進(jìn)行處理作為用戶節(jié)點(diǎn)的屬性然后加入到模型中，更能真實(shí)反映用戶的興趣特征。

根據(jù)上文的分析可將LDA在微博中的應(yīng)用表示為 “用戶—微博—主題—詞語(yǔ)”4層貝葉斯模型。因?yàn)闃?biāo)簽數(shù)據(jù)是以短語(yǔ)的形式進(jìn)行存儲(chǔ)，且數(shù)據(jù)準(zhǔn)確性較高，故不用對(duì)其進(jìn)行數(shù)據(jù)預(yù)處理，即可直接保存為用戶的屬性集合，稱為用戶層。以用戶ui的所有微博文本集合Ti={t1,t2,…,tn}為一個(gè)文檔D。所有的文檔集合定義為微博層，在文檔中產(chǎn)生的用戶的興趣主題定義為興趣層。LDA的圖模型如圖3所示。根據(jù)LDA模型，可以求出每個(gè)用戶與不同主題之間的概率分布，生成一篇文檔，每一個(gè)詞語(yǔ)出現(xiàn)的概率為文檔集中所有詞語(yǔ)和主題的聯(lián)合概率分布為

根據(jù)聯(lián)合概率分布公式，采用吉布斯算法對(duì)其進(jìn)行采樣，可以得到用戶和主題的概率分布。

用戶和主題之間的概率分布矩陣為

其中，T為用戶的微博文檔，z為興趣主題，pw表示兩者的生成概率。

4.2 JSCNM算法

CNM算法是通過(guò)對(duì)網(wǎng)絡(luò)中模塊度的增量最大值來(lái)進(jìn)行聚類的，GN算法[15]是通過(guò)反復(fù)刪除網(wǎng)絡(luò)中邊介數(shù)最大的邊，逐步將網(wǎng)絡(luò)劃分層次結(jié)構(gòu)。CNM算法比GN算法擁有更好的執(zhí)行效率，但CNM算法對(duì)于檢測(cè)較大規(guī)模的網(wǎng)絡(luò)，可能存在社區(qū)劃分不平衡的問(wèn)題。本文在CNM算法的優(yōu)點(diǎn)的基礎(chǔ)上，利用用戶相似度距離取代模塊度的增量最大值來(lái)對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，此算法簡(jiǎn)稱為JSCNM算法。

JSCNM算法的思想是通過(guò)用戶節(jié)點(diǎn)之間的相似度融合用戶間關(guān)系即用戶相似度中心性的變化Cs(i)來(lái)替代模塊度增量，根據(jù)合并規(guī)則對(duì)網(wǎng)絡(luò)進(jìn)行聚類劃分，最后形成多個(gè)相似用戶社區(qū)。其中，根據(jù)JS距離公式計(jì)算用戶興趣相似度矩陣，然后逐漸根據(jù)社區(qū)之間相似度的大小來(lái)進(jìn)行合并。

初始化用戶相似度矩陣時(shí)需要按照一定的規(guī)則進(jìn)行相似度合并。例如，需要將i和j社區(qū)合并成新的i社區(qū)，合并之后需要?jiǎng)h除第j列并且更新第i列，本文的合并規(guī)則仍然使用CNM算法的合并規(guī)則。定義變量eij和ai的值分別為

其中，Cs(i)是節(jié)點(diǎn)i的相似度中心性的值，m是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的中心性值的總和。用相似度取代模塊度增量為

其中，α為調(diào)和因子。實(shí)驗(yàn)表明，當(dāng)α=5時(shí)，效果最好。Sim(i,j)是節(jié)點(diǎn)i和j的相似度距離，也是節(jié)點(diǎn)間概率分布的JS距離的倒數(shù)值。

JSCNM算法流程如下。輸入網(wǎng)絡(luò)的鄰接矩陣，輸出社區(qū)個(gè)數(shù)、最大模塊度Q。

①利用LDA模型計(jì)算出用戶—主題之間的概率分布矩陣。

②利用JS距離公式初始化用戶之間的相似度矩陣S，初始化模塊度增量矩陣ΔQ。

③初始化最大堆H，里面存放模塊度增量矩陣ΔQ中每列的最大值。

④選擇最大堆H中的堆頂元素，參考合并規(guī)則公式對(duì)增量矩陣最大值對(duì)應(yīng)的行和列來(lái)進(jìn)行合并，更新增量矩陣和大頂堆。

⑤直到所有的節(jié)點(diǎn)歸于一個(gè)社區(qū)，否則繼續(xù)執(zhí)行步驟④。

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

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

本文實(shí)驗(yàn)采用網(wǎng)絡(luò)爬蟲抓取新浪微博用戶信息及其微博內(nèi)容?？紤]到用戶粉絲數(shù)在某種程度上可以反映用戶的性質(zhì)和重要性，本文隨機(jī)爬取用戶粉絲數(shù)在50～100、100～150、150～200、200～250的4個(gè)用戶作為種子用戶，并進(jìn)一步地爬取與其有關(guān)聯(lián)的微博用戶信息和用戶最新的150條微博內(nèi)容。因?yàn)槲⒉┲写嬖谠S多噪聲數(shù)據(jù)，例如，一些表情符號(hào)、視頻鏈接等。這些噪聲數(shù)據(jù)不但對(duì)分析數(shù)據(jù)沒有幫助，而且會(huì)影響實(shí)驗(yàn)效率，因此需要對(duì)噪聲數(shù)據(jù)進(jìn)行清洗。在數(shù)據(jù)預(yù)處理部分，利用中科院的分詞工具對(duì)微博數(shù)據(jù)進(jìn)行去除停用詞、清洗噪聲數(shù)據(jù)以及對(duì)中文進(jìn)行分詞操作。

對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，篩選出其中4個(gè)用戶集合見表1所列。

表1 4組實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)

5.2 結(jié)果分析

圖4為4個(gè)數(shù)據(jù)集中各個(gè)用戶節(jié)點(diǎn)的度大小分布。由圖4可知，大部分用戶節(jié)點(diǎn)的度是比較少的，極少數(shù)的用戶擁有比較多的關(guān)聯(lián)用戶，且網(wǎng)絡(luò)中用戶度數(shù)服從冪律分布的特征。

表2是4個(gè)數(shù)據(jù)集利用改進(jìn)的LDA主題模型生成的用戶興趣主題的前20個(gè)詞語(yǔ)。從表2可以看出，數(shù)據(jù)集S1中用戶比較關(guān)心的是球賽、政治、新聞和娛樂等話題；數(shù)據(jù)集S2中用戶較為關(guān)心的是寵物、科技、經(jīng)濟(jì)和食品安全等話題；數(shù)據(jù)集S3中用戶比較關(guān)注的有救援、動(dòng)物保護(hù)、春游等話題；數(shù)據(jù)集S4中則關(guān)心大學(xué)生創(chuàng)業(yè)、政治經(jīng)濟(jì)以及和電影有關(guān)的話題。

圖5為4個(gè)數(shù)據(jù)集用戶之間的興趣相似度矩陣圖。圖中點(diǎn)的顏色越深，興趣相似度越高。因?yàn)楸疚臄?shù)據(jù)是基于用戶關(guān)系爬取的微博文本，所以在興趣相似度比較高。而且可以看出，相似度矩陣沿著對(duì)角線有一條明顯的黑線，說(shuō)明用戶的鄰居用戶之間有較高的相似度。

表2 4個(gè)數(shù)據(jù)集中用戶興趣主題的前20個(gè)詞語(yǔ)

表3 3種算法結(jié)果對(duì)比

通過(guò)將本文算法和傳統(tǒng)的CNM算法以及GN算法進(jìn)行對(duì)比，使用模塊度函數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)，具體結(jié)果見表3。從表3可以看出，本文算法的社區(qū)劃分比較明顯而且用戶社區(qū)的個(gè)數(shù)較多，用戶分布更加平衡。

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

本文提出了一種改進(jìn)的JSCNM聚類算法，利用用戶興趣相似度取代模塊度增量對(duì)其改進(jìn)，從而實(shí)現(xiàn)了用戶關(guān)系和用戶內(nèi)容雙內(nèi)聚來(lái)劃分社區(qū)的效果。使用適合微博網(wǎng)絡(luò)的主題模型LDA對(duì)用戶興趣主題進(jìn)行識(shí)別，采用優(yōu)化的KL距離公式計(jì)算用戶之間的相似度，在真實(shí)數(shù)據(jù)集上進(jìn)行凝聚實(shí)現(xiàn)社區(qū)劃分。通過(guò)算法的對(duì)比實(shí)驗(yàn)，證明了該算法流程的科學(xué)性、合理性，且實(shí)驗(yàn)結(jié)果也較為理想。但是因?yàn)閿?shù)據(jù)是大規(guī)模的文本集，在整個(gè)流程中消耗了許多時(shí)間資源，如何利用好的模型算法在準(zhǔn)確劃分社區(qū)的同時(shí)提高實(shí)驗(yàn)效率，將是下一步的研究?jī)?nèi)容。

[1]丁連紅,時(shí)鵬.網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)[M].北京:化學(xué)工業(yè)出版社.2008.

[2]WATTSD J,STROGATZ SH.Collective dynamics of small-world networks[J].Nature,1998,393（6684）:440-442.

[3]BARABASI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286（5439）:509-512.

[4]蔡波斯,陳翔.基于行為相似度的微博社區(qū)發(fā)現(xiàn)研究[J].計(jì)算機(jī)工程,2013,39（8）:55-59.

[5]范超然,黃曙光,李永成.微博社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法研究[J].技術(shù)與方法,2012,（23）:67-70.

[6]段煉,朱欣焰.基于社區(qū)時(shí)空主題模型的微博社區(qū)發(fā)現(xiàn)方法[J].電子科技大學(xué)學(xué)報(bào),2014,43（3）:464-469.

[7]閻春霖,張延園.基于用戶標(biāo)簽的社區(qū)發(fā)現(xiàn)方法研究[J].科學(xué)技術(shù)與工程,2011,11（6）:1237-1240.

[8]閆光輝,舒昕.基于主題和鏈接分析的微博社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30（7）:1593-1597.

[9]周小平,梁循.基于R-C模型的微博用戶社區(qū)發(fā)現(xiàn)[J].軟件學(xué)報(bào).2014,25（12）:2808-2823.

[10]NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69（2）:026113.

[11]NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69（6）:066133.

[12]BLEID M,NG A Y,JORDAN M I.Latent dirichlet allocation[J].Journal of Machine Learning Research,2003,（3）:993-1033.

[13]LIN J.Divergence measures based on the shannon entropy[J].IEEE Transactions on Information Theory,1991,37（1）:145-151.

[14]KULLBACK S.Letter to the editor:the kullback-leibler distance[J].The American Statistician,1987,41（4）:338-341.

[15]GIRVAN M,NEWMANM E J.Community structure in social and biological networks[A].Proceedings of the National Academy of Sciences[C].2002,99（12）:7821-7826.