結(jié)合用戶(hù)生成內(nèi)容與鏈接關(guān)系的社區(qū)發(fā)現(xiàn)算法*

張恩德，高克寧，張　昱，李　封

東北大學(xué) 計(jì)算中心，沈陽(yáng) 110819

結(jié)合用戶(hù)生成內(nèi)容與鏈接關(guān)系的社區(qū)發(fā)現(xiàn)算法*

張恩德+，高克寧，張昱，李封

東北大學(xué) 計(jì)算中心，沈陽(yáng) 110819

ZHANG Ende,GAO Kening,ZHANG Yu,et al.Community discovery algorithm based on combination of users generated contents and link relationships.Journal of Frontiers of Computer Science and Technology,2016,10 (2)：194-200.

社區(qū)發(fā)現(xiàn)一直是社會(huì)網(wǎng)絡(luò)研究中的熱點(diǎn)內(nèi)容。但是當(dāng)前社區(qū)發(fā)現(xiàn)算法更加關(guān)注用戶(hù)與用戶(hù)之間的鏈接關(guān)系，而對(duì)社會(huì)網(wǎng)絡(luò)中用戶(hù)生成內(nèi)容（user generated contents,UGC）大數(shù)據(jù)研究較少。用戶(hù)生成內(nèi)容是Web2.0的特點(diǎn)，也是社會(huì)網(wǎng)絡(luò)平臺(tái)吸引用戶(hù)的重要原因之一，對(duì)社區(qū)的形成起著重要作用。提出了一種新的社區(qū)發(fā)現(xiàn)算法，能夠綜合利用用戶(hù)與用戶(hù)之間的鏈接關(guān)系以及用戶(hù)生成內(nèi)容來(lái)確定用戶(hù)的社區(qū)劃分。該算法用LDA（latent Dirichlet allocation）算法分析用戶(hù)生成內(nèi)容中主要的內(nèi)容形式——文本信息，同時(shí)通過(guò)譜分析方法分析用戶(hù)與用戶(hù)之間的鏈接關(guān)系，并有機(jī)結(jié)合以發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。通過(guò)分析科學(xué)網(wǎng)的真實(shí)數(shù)據(jù)，證明了所提算法能夠有效綜合利用用戶(hù)生成內(nèi)容與用戶(hù)鏈接關(guān)系，使社區(qū)發(fā)現(xiàn)的結(jié)果更加客觀準(zhǔn)確。

社區(qū)發(fā)現(xiàn)；用戶(hù)生成內(nèi)容；用戶(hù)鏈接關(guān)系；社會(huì)網(wǎng)絡(luò)

1　引言

Web2.0的發(fā)展以及眾多社會(huì)網(wǎng)絡(luò)平臺(tái)的出現(xiàn)，使用戶(hù)體驗(yàn)到了網(wǎng)上社交的樂(lè)趣。在社會(huì)網(wǎng)絡(luò)平臺(tái)上，包括博客、微博、即時(shí)通訊、交友網(wǎng)絡(luò)，人們通過(guò)這些平臺(tái)提供的各種應(yīng)用，通過(guò)好友互動(dòng)、互粉、留言等活動(dòng)，建立了各種各樣的互動(dòng)聚集現(xiàn)象，并形成了一個(gè)個(gè)“群集”（cluster），群集的建立有的是基于生活中的好友關(guān)系，有的是基于用戶(hù)興趣，這些群集無(wú)論對(duì)于商品推薦還是廣告營(yíng)銷(xiāo)等，都有極強(qiáng)的研究意義。這些群集又被稱(chēng)為社區(qū)，對(duì)于這些群集的發(fā)現(xiàn)稱(chēng)為社區(qū)發(fā)現(xiàn)。

對(duì)于社區(qū)發(fā)現(xiàn)的研究，科研人員已經(jīng)取得了豐碩的成果。但是，當(dāng)前社區(qū)發(fā)現(xiàn)算法更關(guān)注于通過(guò)社會(huì)網(wǎng)絡(luò)鏈接結(jié)構(gòu)進(jìn)行，即通過(guò)分析用戶(hù)與用戶(hù)之間的鏈接關(guān)系以發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。可是在實(shí)際場(chǎng)景中，社會(huì)網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)為用戶(hù)生成內(nèi)容，網(wǎng)絡(luò)上的內(nèi)容主要由用戶(hù)生成，每一個(gè)用戶(hù)都可以生成自己的內(nèi)容，互聯(lián)網(wǎng)上的所有內(nèi)容由用戶(hù)創(chuàng)造，用戶(hù)加入到某個(gè)社區(qū)也主要是由社區(qū)內(nèi)容所吸引。社區(qū)的形成和特定的目的有關(guān)，在不同的社區(qū)內(nèi)部，人們關(guān)注不同的內(nèi)容。例如，在一個(gè)博客平臺(tái)中，某用戶(hù)甲瀏覽了用戶(hù)乙的博文，但是如果用戶(hù)甲并不是用戶(hù)乙的好友，用戶(hù)甲也沒(méi)有直接在用戶(hù)乙的博文下面進(jìn)行回復(fù)，而是有感而發(fā)寫(xiě)了一篇新的關(guān)于相同話(huà)題的博文，但是沒(méi)有直接引用這篇博文。那么在網(wǎng)絡(luò)結(jié)構(gòu)上看，用戶(hù)甲和用戶(hù)乙并沒(méi)有直接鏈接，他們很難歸為一個(gè)社區(qū)中，但是如果考慮話(huà)題結(jié)構(gòu)，他們應(yīng)該在一個(gè)共同的話(huà)題社區(qū)內(nèi)，如果在社區(qū)發(fā)現(xiàn)中加入關(guān)于社區(qū)話(huà)題的更多信息內(nèi)容，可以讓社區(qū)發(fā)現(xiàn)結(jié)果更加精確。本文提出了一種結(jié)合用戶(hù)與用戶(hù)之間的鏈接關(guān)系以及用戶(hù)生成內(nèi)容的算法進(jìn)行用戶(hù)社區(qū)發(fā)現(xiàn)，其中用戶(hù)之間的鏈接關(guān)系可以為用戶(hù)好友關(guān)系（如Facebook中的好友關(guān)系），用戶(hù)關(guān)注與被關(guān)注關(guān)系（如Twitter中的follower-followee關(guān)系），用戶(hù)生成內(nèi)容為所有內(nèi)容中的主要形式——文本內(nèi)容。本文通過(guò)LDA（latent Dirichlet allocation）算法分析用戶(hù)文本內(nèi)容，并利用譜分析方法結(jié)合用戶(hù)鏈接關(guān)系與用戶(hù)生成內(nèi)容進(jìn)行社區(qū)發(fā)現(xiàn)。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文方法能夠有效利用用戶(hù)鏈接關(guān)系與用戶(hù)生成內(nèi)容，社區(qū)發(fā)現(xiàn)的結(jié)果更加客觀準(zhǔn)確。

本文組織結(jié)構(gòu)如下：第2章介紹相關(guān)的工作；第3章對(duì)本文算法進(jìn)行詳細(xì)討論；第4章介紹實(shí)驗(yàn)結(jié)果；最后對(duì)本文工作進(jìn)行總結(jié)。

2　相關(guān)工作

社區(qū)發(fā)現(xiàn)（community discovery），又稱(chēng)社區(qū)檢測(cè)（community detection）、社區(qū)識(shí)別（community identification）、社區(qū)提取（community extraction）。社區(qū)發(fā)現(xiàn)研究主要分為兩類(lèi)：一類(lèi)是非重疊社區(qū)發(fā)現(xiàn)，即一個(gè)節(jié)點(diǎn)只能屬于一個(gè)社區(qū)；一類(lèi)是重疊社區(qū)發(fā)現(xiàn)。對(duì)這兩類(lèi)，研究人員均進(jìn)行了大量工作。針對(duì)非重疊社區(qū)發(fā)現(xiàn)，主要有基于模塊度的優(yōu)化算法、基于譜分析的方法、基于信息論的方法以及基于標(biāo)簽傳播的方法。Newman在2004年提出了模塊度的概念[1]，模塊度通過(guò)比較真實(shí)網(wǎng)絡(luò)中各社團(tuán)的邊密度和隨機(jī)網(wǎng)絡(luò)圖中對(duì)應(yīng)子圖的邊密度之間的差異來(lái)度量社團(tuán)結(jié)構(gòu)的顯著性。這一概念的提出引發(fā)了社區(qū)發(fā)現(xiàn)的一個(gè)熱潮，陸續(xù)有研究人員通過(guò)優(yōu)化模塊度目標(biāo)函數(shù)來(lái)進(jìn)行社區(qū)發(fā)現(xiàn)。文獻(xiàn)[2]指出模塊度優(yōu)化問(wèn)題是一個(gè)NP難問(wèn)題。文獻(xiàn)[3]提出了CNM社區(qū)發(fā)現(xiàn)算法，該算法采用堆數(shù)據(jù)結(jié)構(gòu)來(lái)計(jì)算和更新網(wǎng)絡(luò)的模塊度，大大提高了計(jì)算速度。文獻(xiàn)[4]在社區(qū)發(fā)現(xiàn)迭代過(guò)程中引入多步擴(kuò)展，優(yōu)化了結(jié)果。基于譜分析方法主要的研究工作有文獻(xiàn)[5-7]，這些算法基于矩陣的譜性質(zhì)進(jìn)行社區(qū)發(fā)現(xiàn)。基于信息論的社區(qū)發(fā)現(xiàn)方法思想是將網(wǎng)絡(luò)的模塊化描述看作對(duì)網(wǎng)絡(luò)拓?fù)涞囊环N有損壓縮，從而將社區(qū)發(fā)現(xiàn)問(wèn)題轉(zhuǎn)化為信息論中的一個(gè)問(wèn)題，即尋找拓?fù)浣Y(jié)構(gòu)的有效壓縮方式，這方面的研究有文獻(xiàn)[8-10]。基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)方法[11-12]首先將每個(gè)節(jié)點(diǎn)指定唯一標(biāo)號(hào)，然后每步迭代按照一定規(guī)則更新鄰居標(biāo)簽，經(jīng)過(guò)若干次迭代后將標(biāo)簽相同的歸為同一社區(qū)。文獻(xiàn)[13]在基于模塊度函數(shù)的基礎(chǔ)上，提出相關(guān)分析（correlation analysis）方法，對(duì)模塊函數(shù)進(jìn)行精巧的修改，能夠提高這類(lèi)方法的應(yīng)用范圍。文獻(xiàn)[14]提出了一種熱核方法（heat kernel）進(jìn)行社區(qū)發(fā)現(xiàn)，該方法通過(guò)選取種子節(jié)點(diǎn)，使用圖擴(kuò)散方法來(lái)發(fā)現(xiàn)社區(qū)。文獻(xiàn)[15]提出了一種能夠消除不相關(guān)子圖的穩(wěn)健社區(qū)發(fā)現(xiàn)算法。重疊社區(qū)發(fā)現(xiàn)認(rèn)為一個(gè)網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)可能屬于不同的社區(qū)，相當(dāng)于圖的一個(gè)“軟分割”。文獻(xiàn)[16]可以看作是重疊社區(qū)發(fā)現(xiàn)的開(kāi)山之作，它指出了社區(qū)有重疊這一現(xiàn)象，并提出了一種基于團(tuán)滲流（clique percolation）的重疊社區(qū)發(fā)現(xiàn)算法。對(duì)于重疊社區(qū)發(fā)現(xiàn)的算法還很多，由于本文主要針對(duì)非重疊社區(qū)發(fā)現(xiàn)，這里不再進(jìn)行介紹。文獻(xiàn)[17]針對(duì)傳統(tǒng)社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)只通過(guò)節(jié)點(diǎn)鄰接關(guān)系劃分社區(qū)，使劃分出的社區(qū)結(jié)構(gòu)只代表一維關(guān)系結(jié)構(gòu)，無(wú)法反映具有語(yǔ)義關(guān)聯(lián)的語(yǔ)義社區(qū)結(jié)構(gòu)問(wèn)題，提出了FA-SA算法解決多元語(yǔ)義社會(huì)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問(wèn)題，并對(duì)語(yǔ)義社會(huì)網(wǎng)絡(luò)分析進(jìn)行了深入研究。

由上面的綜述可見(jiàn)，雖然在社區(qū)發(fā)現(xiàn)方面已經(jīng)有了豐碩的研究成果，科研人員也用不同的理論方法來(lái)解決社區(qū)發(fā)現(xiàn)問(wèn)題，但是當(dāng)前的研究還是以對(duì)社會(huì)網(wǎng)絡(luò)圖結(jié)構(gòu)的分析為基礎(chǔ)，沒(méi)有充分利用社會(huì)網(wǎng)絡(luò)中豐富的用戶(hù)生成內(nèi)容。

3　結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)與文本內(nèi)容的社區(qū)發(fā)現(xiàn)算法

本文充分利用社區(qū)網(wǎng)絡(luò)中的大數(shù)據(jù)，包括用戶(hù)之間的好友關(guān)系以及用戶(hù)生成內(nèi)容（用戶(hù)發(fā)表文本內(nèi)容信息），提出了一種結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)與文本內(nèi)容的社區(qū)發(fā)現(xiàn)算法。

3.1基于網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)

本節(jié)介紹基于網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法。網(wǎng)絡(luò)結(jié)構(gòu)是社區(qū)發(fā)現(xiàn)的基礎(chǔ)，本文擬直接采取當(dāng)前研究中比較成熟的基于結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法——譜分析社區(qū)發(fā)現(xiàn)算法[6]。譜分析又稱(chēng)譜聚類(lèi)，首先將一個(gè)圖結(jié)構(gòu)轉(zhuǎn)化為對(duì)應(yīng)的拉普拉斯矩陣，給定社會(huì)網(wǎng)絡(luò)圖結(jié)構(gòu)G，G的拉普拉斯矩陣的特征值中0特征值出現(xiàn)的次數(shù)等于圖中不連通區(qū)域的個(gè)數(shù)。對(duì)于每一個(gè)非連通圖，可以對(duì)每個(gè)連通子圖建立拉普拉斯矩陣。事實(shí)上，在真實(shí)的社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)中，不同社區(qū)幾乎不可能完全不相連。如果圖為連通圖，拉普拉斯矩陣只有一個(gè)特征值為0。如果整個(gè)社會(huì)網(wǎng)絡(luò)圖結(jié)構(gòu)由幾個(gè)不連通的子圖構(gòu)成，那么G對(duì)應(yīng)的拉普拉斯矩陣為0的特征值等于子圖的個(gè)數(shù)。因此可以利用拉普拉斯矩陣的前幾個(gè)最小的特征值進(jìn)行聚類(lèi)，聚類(lèi)結(jié)果中的每一個(gè)簇（cluster）就相當(dāng)于一個(gè)社區(qū)。算法1是標(biāo)準(zhǔn)譜聚類(lèi)算法的一般步驟。

算法1基于網(wǎng)絡(luò)結(jié)構(gòu)信息社區(qū)發(fā)現(xiàn)算法

輸入：社會(huì)網(wǎng)絡(luò)圖G=(V,E)。

輸出：社會(huì)網(wǎng)絡(luò)的k個(gè)聚類(lèi)（社區(qū)）。

（1）根據(jù)社會(huì)網(wǎng)絡(luò)圖結(jié)構(gòu)，構(gòu)建拉普拉斯矩陣；

（2）計(jì)算拉普拉斯矩陣的特征值和特征向量；

（3）利用前k個(gè)特征值對(duì)應(yīng)的特征向量來(lái)對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行聚類(lèi)；

（4）返回社會(huì)網(wǎng)絡(luò)的聚類(lèi)結(jié)果（社區(qū)）。

3.2結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)與文本內(nèi)容的社區(qū)發(fā)現(xiàn)算法

3.1節(jié)介紹了基于結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)可以通過(guò)用戶(hù)節(jié)點(diǎn)與用戶(hù)節(jié)點(diǎn)之間的鏈接關(guān)系發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。但是結(jié)構(gòu)信息只是部分地利用了社會(huì)網(wǎng)絡(luò)上的數(shù)據(jù)。本文提出了綜合利用結(jié)構(gòu)信息與用戶(hù)生成內(nèi)容進(jìn)行社區(qū)發(fā)現(xiàn)。這類(lèi)的結(jié)構(gòu)信息指用戶(hù)與用戶(hù)之間的鏈接關(guān)系，用戶(hù)生成內(nèi)容為用戶(hù)發(fā)表文本信息。利用文本信息進(jìn)行社區(qū)發(fā)現(xiàn)能夠從話(huà)題層次上分析節(jié)點(diǎn)的屬性，從而能在話(huà)題意義上發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，并且能有效識(shí)別出鏈接的“噪聲”，能計(jì)算成員在各個(gè)話(huà)題中的“關(guān)系”結(jié)構(gòu)。因此，本節(jié)提出了一種能夠同時(shí)結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)與用戶(hù)話(huà)題的算法進(jìn)行社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)。

假設(shè)用戶(hù)發(fā)表的內(nèi)容以文檔形式存在（如用戶(hù)發(fā)表的一篇博客就相當(dāng)于一個(gè)文檔），利用LDA算法進(jìn)行話(huà)題發(fā)現(xiàn)的思想[18]，假設(shè)D個(gè)文檔中存在T個(gè)話(huà)題，則對(duì)于文檔集中的任一篇文檔di，都可以看作是T個(gè)話(huà)題的多項(xiàng)式分布，而其中每個(gè)話(huà)題Tk又都可以看作是在文檔中i個(gè)詞匯上的多項(xiàng)式分布。即假設(shè)有T個(gè)話(huà)題，則所給文本中的第i個(gè)詞匯wi可以表示如下：

其中，zi是隱變量，表明第i個(gè)詞（即為wi）取自該話(huà)題；p(wi|zi=k)是wi屬于話(huà)題k的概率；p(zi=k)給出話(huà)題k屬于當(dāng)前文本的概率。假定T個(gè)話(huà)題形成D個(gè)文檔，并以W個(gè)詞表示，記表示對(duì)于話(huà)題k，W個(gè)詞上的多項(xiàng)式分布，其中w是W個(gè)詞匯表中的一個(gè)詞；另表示對(duì)于文本d，T個(gè)話(huà)題上的多項(xiàng)式分布，那么文本d中詞匯w的概率如式（2）：

式（2）可以進(jìn)一步表示為：

在計(jì)算得到各個(gè)文檔的話(huà)題相關(guān)度后，假設(shè)每篇文檔僅有一個(gè)作者用戶(hù)（這個(gè)假設(shè)符合絕大部分的社會(huì)網(wǎng)絡(luò)真實(shí)情況），因此，對(duì)該作者所發(fā)表的文檔在話(huà)題空間上求和，即可得到該作者在話(huà)題空間上的潛在分布，即：

根據(jù)式（4），即可計(jì)算作者用戶(hù)節(jié)點(diǎn)在話(huà)題空間上的概率分布，根據(jù)不同用戶(hù)的p(z|u)進(jìn)一步由式（5）計(jì)算不同用戶(hù)之間在話(huà)題空間上的相關(guān)性：

式（5）中，l(uij)表示用戶(hù)ui與用戶(hù)uj之間原有的鏈接關(guān)系。

根據(jù)用戶(hù)與用戶(hù)之間的相關(guān)性Cor(uij)，可以得到帶有權(quán)重的拉普拉斯矩陣，在此矩陣上使用譜方法進(jìn)行社區(qū)發(fā)現(xiàn)，則同時(shí)利用了社會(huì)網(wǎng)絡(luò)上的話(huà)題信息以及結(jié)構(gòu)信息，能夠更加準(zhǔn)確地進(jìn)行社區(qū)發(fā)現(xiàn)。因此，本文提出的綜合利用網(wǎng)絡(luò)結(jié)構(gòu)與用戶(hù)內(nèi)容的社區(qū)發(fā)現(xiàn)算法如算法2所示。

算法2結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)與話(huà)題信息社區(qū)發(fā)現(xiàn)算法

輸入：社會(huì)網(wǎng)絡(luò)圖G=(V,E)，用戶(hù)發(fā)表文檔集合D以及用戶(hù)與文檔之間的關(guān)系。

輸出：社會(huì)網(wǎng)絡(luò)的k個(gè)聚類(lèi)（社區(qū)）。

（1）基于LDA話(huà)題發(fā)現(xiàn)方法及圖結(jié)構(gòu)信息，計(jì)算用戶(hù)與用戶(hù)之間的相關(guān)性Cor(uij)；

（2）根據(jù)Cor(uij)信息構(gòu)建拉普拉斯矩陣；

（3）計(jì)算拉普拉斯矩陣的特征值和特征向量；

（4）利用前k個(gè)特征值對(duì)應(yīng)的特征向量來(lái)對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行聚類(lèi)；

（5）返回社會(huì)網(wǎng)絡(luò)的聚類(lèi)結(jié)果（社區(qū)）。

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

4.1數(shù)據(jù)描述

在真實(shí)數(shù)據(jù)集科學(xué)網(wǎng)博客（http://blog.sciencenet. cn/）上進(jìn)行算法驗(yàn)證。實(shí)驗(yàn)數(shù)據(jù)來(lái)自于研究小組自己編寫(xiě)的爬蟲(chóng)程序所爬取的數(shù)據(jù)，包括網(wǎng)站上從2007年11月至2014年7月的部分博主信息及博客內(nèi)容，博主信息包括用戶(hù)ID、姓名、昵稱(chēng)、好友關(guān)系，在數(shù)據(jù)處理過(guò)程中，刪除了從未發(fā)表博客內(nèi)容的用戶(hù)以及博客內(nèi)容過(guò)短的博文。數(shù)據(jù)集包括用戶(hù)發(fā)表博客內(nèi)容，以及用戶(hù)的好友關(guān)系。最后得到了3 529個(gè)用戶(hù)以及23 152篇博文。算法通過(guò)分析該數(shù)據(jù)集得到其中的社區(qū)結(jié)構(gòu)。在數(shù)據(jù)集中，科學(xué)網(wǎng)博客本身已經(jīng)對(duì)博客用戶(hù)進(jìn)行了分類(lèi)，將科學(xué)網(wǎng)博客對(duì)用戶(hù)的分類(lèi)認(rèn)為是正確的社區(qū)發(fā)現(xiàn)結(jié)果。算法進(jìn)行社區(qū)發(fā)現(xiàn)的準(zhǔn)確率與該結(jié)果進(jìn)行比較。按照科學(xué)網(wǎng)博客的分類(lèi)標(biāo)準(zhǔn)，博客用戶(hù)一共分為8個(gè)社區(qū)，這8個(gè)社區(qū)分別為：生命科學(xué)（簡(jiǎn)稱(chēng)life）、醫(yī)學(xué)科學(xué)（簡(jiǎn)稱(chēng)medicine）、化學(xué)科學(xué)（簡(jiǎn)稱(chēng)chemistry）、工程材料（簡(jiǎn)稱(chēng)material）、信息科學(xué)（簡(jiǎn)稱(chēng)information）、地球科學(xué)（簡(jiǎn)稱(chēng)earth）、數(shù)理科學(xué)（簡(jiǎn)稱(chēng)mathematics）、管理綜合（簡(jiǎn)稱(chēng)management）。

實(shí)驗(yàn)運(yùn)行在IBM X3500上，機(jī)器配置為Xeon Quad雙CPU，內(nèi)存為16 GB，操作系統(tǒng)為64位Linux系統(tǒng)CentOS。程序使用R語(yǔ)言編寫(xiě)，中文分詞使用RWordseg包，矩陣的特征值與特征向量計(jì)算使用ARPACK包，LDA計(jì)算使用吉布斯抽樣方法。

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

實(shí)驗(yàn)比較了基于結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)以及基于結(jié)構(gòu)和話(huà)題模型的社區(qū)發(fā)現(xiàn)算法的社區(qū)發(fā)現(xiàn)準(zhǔn)確率。基于結(jié)構(gòu)的算法即基于博客用戶(hù)與博客用戶(hù)之間的好友關(guān)系使用算法1進(jìn)行社區(qū)發(fā)現(xiàn)，以下簡(jiǎn)稱(chēng)CD-ST（community discovery based on structure）；基于結(jié)構(gòu)和話(huà)題模型的社區(qū)發(fā)現(xiàn)算法即通過(guò)分析博客用戶(hù)和博客用戶(hù)之間的好友關(guān)系，以及博客用戶(hù)發(fā)表博文內(nèi)容，使用算法2進(jìn)行社區(qū)發(fā)現(xiàn)，以下簡(jiǎn)稱(chēng)CD-TS（community discovery based on topic&structure）。因?yàn)榭茖W(xué)網(wǎng)博客中已知社區(qū)結(jié)構(gòu)，所以準(zhǔn)確率的公式定義如下：

cd表示使用算法發(fā)現(xiàn)的博客用戶(hù)集合；Total為全部用戶(hù)。

實(shí)驗(yàn)比較兩種社區(qū)發(fā)現(xiàn)算法的準(zhǔn)確率變化，其中α為式（5）中的調(diào)節(jié)系數(shù)，α值表明在算法2中基于話(huà)題與基于結(jié)構(gòu)對(duì)應(yīng)算法結(jié)果的貢獻(xiàn)程度。α越大，表明算法中話(huà)題對(duì)于社區(qū)發(fā)現(xiàn)所占的比重越大；α為0，表示只基于結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)；α為1，表明只基于話(huà)題進(jìn)行社區(qū)發(fā)現(xiàn)。

圖1比較了兩種算法的準(zhǔn)確率，其中CD-ST是基于網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法，這里沒(méi)有調(diào)節(jié)系數(shù)，因此該算法的準(zhǔn)確率不隨α的變化而變化。

在圖1中，CD-TS表示基于話(huà)題和結(jié)構(gòu)社區(qū)發(fā)現(xiàn)算法，可以看出，隨著α值的增大，準(zhǔn)確率并不一定隨之增加。在α=0的時(shí)候，表示只基于網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)，因此兩種社區(qū)發(fā)現(xiàn)算法準(zhǔn)確率相同。在α= 0.6的時(shí)候，社區(qū)發(fā)現(xiàn)的準(zhǔn)確率最高，這是因?yàn)殡S著話(huà)題比重的增加，社區(qū)發(fā)現(xiàn)越來(lái)越依賴(lài)用戶(hù)博客中的話(huà)題內(nèi)容。而實(shí)際上，不同學(xué)科的博客用戶(hù)可能討論的話(huà)題有很多相近之處，比如很多博客用戶(hù)都提到了研究生教育問(wèn)題、科研經(jīng)費(fèi)申請(qǐng)問(wèn)題、論文發(fā)表問(wèn)題、當(dāng)前教育體制弊端等共性問(wèn)題，因此隨著話(huà)題比重在社區(qū)發(fā)現(xiàn)算法中的增加，準(zhǔn)確率不一定提高。同時(shí)也看到了在α=1.0的時(shí)候，CD-ST算法社區(qū)發(fā)現(xiàn)的準(zhǔn)確率不如CD-TS。

圖2記錄了當(dāng)α值變化時(shí)（α=0，α=0.6和α=1.0），各個(gè)社區(qū)發(fā)現(xiàn)結(jié)果的準(zhǔn)確率。其中α=0相當(dāng)于只基于結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)，α=1.0相當(dāng)于只基于話(huà)題進(jìn)行社區(qū)發(fā)現(xiàn)。

Fig.1　Precision of two algorithms on scientific network data set圖1　兩種算法在科學(xué)網(wǎng)數(shù)據(jù)集上的準(zhǔn)確率

Fig.2　Precision of CD-TS algorithm on different communities圖2　CD-TS算法在不同社區(qū)上的準(zhǔn)確率

從圖2中可以看到話(huà)題在社區(qū)發(fā)現(xiàn)結(jié)果中所占的比重，對(duì)于不同社區(qū)發(fā)現(xiàn)結(jié)果的準(zhǔn)確率有一定差別，這是由不同學(xué)科的學(xué)科話(huà)題特點(diǎn)來(lái)決定的。舉例來(lái)說(shuō)，某個(gè)在科學(xué)網(wǎng)博客中被劃分為{管理綜合社區(qū)}的博客用戶(hù)，發(fā)表的博客內(nèi)容中很多是關(guān)于“大數(shù)據(jù)”管理方面的內(nèi)容，而“大數(shù)據(jù)”近幾年一直是計(jì)算機(jī)科學(xué)研究領(lǐng)域（屬于{信息科學(xué)社區(qū)}）的一個(gè)研究熱點(diǎn)。另外，{管理綜合社區(qū)}中的博客用戶(hù)也有研究能源和研究?jī)?yōu)化的，由于管理科學(xué)的特點(diǎn)決定了管理科學(xué)與其他學(xué)科有很多共同的話(huà)題，基于話(huà)題的社區(qū)發(fā)現(xiàn)對(duì)管理科學(xué)并不是特別適用。同樣的，{信息科學(xué)社區(qū)}、{數(shù)理科學(xué)社區(qū)}也有這樣的特點(diǎn)；與之對(duì)應(yīng)的是{地球科學(xué)社區(qū)}，這個(gè)學(xué)科相對(duì)應(yīng)其他學(xué)科來(lái)說(shuō)用語(yǔ)更為專(zhuān)業(yè)，像“地震”、“火山”、“洪水”、“厄爾尼諾”等話(huà)題幾乎不會(huì)在其他學(xué)科中出現(xiàn)，因此基于話(huà)題的社區(qū)發(fā)現(xiàn)對(duì)該社區(qū)的發(fā)現(xiàn)效果更佳。

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

科研人員對(duì)社區(qū)發(fā)現(xiàn)已經(jīng)進(jìn)行了比較深入和徹底的研究，但這些研究基本都是基于社會(huì)網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行的，而針對(duì)用戶(hù)生成內(nèi)容進(jìn)行的社區(qū)發(fā)現(xiàn)很少。事實(shí)上，用戶(hù)加入某個(gè)社區(qū)，更大的可能性是社區(qū)中有興趣相同的其他用戶(hù)。因此，本文提出了結(jié)合用戶(hù)文本內(nèi)容與網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法。根據(jù)用戶(hù)發(fā)表的內(nèi)容，使用LDA話(huà)題發(fā)現(xiàn)技術(shù)，發(fā)現(xiàn)用戶(hù)發(fā)表內(nèi)容隱含的話(huà)題信息，并且利用這些信息，以及用戶(hù)與用戶(hù)之間的鏈接關(guān)系，構(gòu)建含權(quán)的用戶(hù)網(wǎng)絡(luò)，利用權(quán)重體現(xiàn)用戶(hù)的話(huà)題信息與結(jié)構(gòu)信息。在此網(wǎng)絡(luò)上，可以使用多種方法進(jìn)行社區(qū)發(fā)現(xiàn)，本文使用經(jīng)典的譜聚類(lèi)方法進(jìn)行社區(qū)發(fā)現(xiàn)。

在科學(xué)網(wǎng)博客數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，因?yàn)樵摂?shù)據(jù)集本身就已經(jīng)對(duì)用戶(hù)進(jìn)行了社區(qū)分類(lèi)，所以實(shí)驗(yàn)結(jié)果主要考查算法的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明，針對(duì)不同特點(diǎn)的社區(qū)，算法有不同的運(yùn)行結(jié)果，如果有效地利用用戶(hù)發(fā)表的話(huà)題信息，確實(shí)能提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確度。

References:

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

[2]Brandes U,Delling D,Gaertler M,et al.On modularity clustering[J].IEEE Transactions on Knowledge and Data Engineering,2008,30(2):172-188.

[3]Clauset A.Finding local community structure in networks[J]. Physical Review E,2005,72(2):026132.

[4]Schuetz P,Caflisch A.Multistep greedy algorithm identifies community structure in real-world and computer-generated networks[J].Physical Review E,2005,78(2):026112.

[5]Donetti L,Munoz M.Detecting network communities:a new systematic and efficient algorithm[J].Journal of Statistical Mechanics,2004.doi:10.1088/1742-5468/2004/10/ P10012.

[6]Capocci A,Servedio V D P,Caldarelli G,et al.Detecting communities in large networks[J].Physical A:Statistical Mechanics and ItsApplications,2005,352(2/4):669-676.

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

[8]Rosvall M,Bergstrom C T.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences,2008,105(4):1118-1123.

[9]Rosvall M,Bergstrom C T.An information-theoretic framework for resolving community structure in complex networks[J].Proceedings of the National Academy of Sciences, 2007,104(18):7327-7331.

[10]Lancichinetti A,Fortunato S.Community detection algorithms:a comparative analysis[J].Physical Review E, 2009,80(5):056117.

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

[12]Leung I,Hui P,Lio P,et al.Towards real-time community detection in large networks[J].Physical Review E,2009,79 (6):66107.

[13]Palla G,Derenyi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.

[14]Duan Lian,Street W N,Liu Yanchi.Community detection in graphs through correlation[C]//Proceedings of the 20thACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,USA,Aug 24-27, 2014.New York,USA:ACM,2014:1376-1385.

[15]Kloster K,Gleich D F.Heat kernel based community detection[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York,USA,Aug 24-27,2014.New York,USA:ACM, 2014:1386-1395.

[16]Wu Yubao,Jin Ruoming,Li Jing,et al.Robust local community detection:on free rider effect and its elimination[J]. Proceedings of the VLDB Endowment,2015,8(7):798-809.

[17]Yang Jing,Xin Yu,Xie Zhiqiang.Semantics social network community detection algorithm based on topic comprehensive factor analysis[J].Journal of Computer Research and Development,2014,51(3):559-569.

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

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

[17]楊靜,辛宇,謝志強(qiáng).基于話(huà)題綜合因子分析的語(yǔ)義社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)研究與發(fā)展,2014,51(3): 559-569.

張恩德（1980—），男，遼寧海城人，2014年于東北大學(xué)計(jì)算機(jī)科學(xué)專(zhuān)業(yè)獲得博士學(xué)位，現(xiàn)為東北大學(xué)計(jì)算中心教師，CCF會(huì)員,主要研究領(lǐng)域?yàn)樯鐣?huì)網(wǎng)絡(luò)，機(jī)器學(xué)習(xí)等。

高克寧（1963—），女，遼寧沈陽(yáng)人，2006年于東北大學(xué)計(jì)算機(jī)科學(xué)專(zhuān)業(yè)獲得博士學(xué)位，現(xiàn)為東北大學(xué)計(jì)算中心教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)檎Z(yǔ)義網(wǎng)絡(luò)，信息系統(tǒng)等。

ZHANG Yu was born in 1980.He is a Ph.D.candidate and lecturer at Northeastern University.His research interest is data mining in social networks.

張昱（1980—），男，遼寧沈陽(yáng)人，東北大學(xué)博士研究生，東北大學(xué)計(jì)算中心教師，主要研究領(lǐng)域?yàn)樯鐣?huì)網(wǎng)絡(luò)中的數(shù)據(jù)挖掘。

LI Feng was born in 1981.He is a Ph.D.candidate and lecturer at Northeastern University.His research interest is data mining in social networks.

李封（1981—），男，遼寧沈陽(yáng)人，東北大學(xué)博士研究生，東北大學(xué)計(jì)算中心教師，主要研究領(lǐng)域?yàn)樯鐣?huì)網(wǎng)絡(luò)中的數(shù)據(jù)挖掘。

Community Discovery Algorithm Based on Combination of Users Generated Contents and Link Relationships*

ZHANG Ende+,GAO Kening,ZHANG Yu,LI Feng
Computing Center,Northeastern University,Shenyang 110819,China
+Corresponding author:E-mail:zed@cc.neu.edu.cn

Community discovery has been an attractive field in social networks research.However,in current community discovery algorithms,more attention is attracted to the link relationships between users and little attention is paid on big data of user generated contents(UGC).User generated content is a special feature of Web2.0,and also is an important reason to attract users,which plays an important role to form communities.This paper presents a new algorithm to solve the community discovery problem,which comprehensively utilizes the link relationships between users and user generated contents.This algorithm uses latent Dirichlet allocation(LDA)algorithm to analyze text information generated by users,and uses spectral analysis method to analyze the link relationships between users, and combines them to discovery communities.By analyzing real world data—science network site data,the proposed algorithm is proved to effectively utilize the user generated contents and link relationships between users,and the results are more objective and accurate.

community discovery;user generated contents;user link relationships;social networks

2015-04,Accepted 2015-06.

ZHANG Ende was born in 1980.He the Ph.D.degree in computer science from Northeastern University in 2014.Now he is a lecturer at Northeastern University,and the member of CCF.His research interests include social network and machine learning,etc.

GAO Kening was born in 1963.She the Ph.D.degree in computer science from Northeastern University in 2006.Now she is a professor at Northeastern University,and the senior member of CCF.Her research interests include semantic network and Web information system,etc.

10.3778/j.issn.1673-9418.1506046

*The National Natural Science Foundation of China under Grant No.61402093(國(guó)家自然科學(xué)基金青年基金);the MOE-Intel Special Fund of Information Technology under Grant No.MOE-Intel-2012-06(教育部-英特爾信息技術(shù)專(zhuān)項(xiàng)科研基金);the Scientific and Technological Projects of Liaoning Province under Grant No.2013217004-1(遼寧省科技攻關(guān)項(xiàng)目).

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-06-29,http://www.cnki.net/kcms/detail/11.5602.TP.20150629.1544.002.html

A

TP311