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

東北大學 計算中心，沈陽 110819

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

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

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

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

1　引言

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

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

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

2　相關(guān)工作

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

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

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

本文充分利用社區(qū)網(wǎng)絡(luò)中的大數(shù)據(jù)，包括用戶之間的好友關(guān)系以及用戶生成內(nèi)容（用戶發(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ǔ)，本文擬直接采取當前研究中比較成熟的基于結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法——譜分析社區(qū)發(fā)現(xiàn)算法[6]。譜分析又稱譜聚類，首先將一個圖結(jié)構(gòu)轉(zhuǎn)化為對應的拉普拉斯矩陣，給定社會網(wǎng)絡(luò)圖結(jié)構(gòu)G，G的拉普拉斯矩陣的特征值中0特征值出現(xiàn)的次數(shù)等于圖中不連通區(qū)域的個數(shù)。對于每一個非連通圖，可以對每個連通子圖建立拉普拉斯矩陣。事實上，在真實的社會網(wǎng)絡(luò)結(jié)構(gòu)中，不同社區(qū)幾乎不可能完全不相連。如果圖為連通圖，拉普拉斯矩陣只有一個特征值為0。如果整個社會網(wǎng)絡(luò)圖結(jié)構(gòu)由幾個不連通的子圖構(gòu)成，那么G對應的拉普拉斯矩陣為0的特征值等于子圖的個數(shù)。因此可以利用拉普拉斯矩陣的前幾個最小的特征值進行聚類，聚類結(jié)果中的每一個簇（cluster）就相當于一個社區(qū)。算法1是標準譜聚類算法的一般步驟。

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

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

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

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

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

（3）利用前k個特征值對應的特征向量來對社會網(wǎng)絡(luò)進行聚類；

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

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

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

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

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

式（2）可以進一步表示為：

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

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

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

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

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

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

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

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

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

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

（4）利用前k個特征值對應的特征向量來對社會網(wǎng)絡(luò)進行聚類；

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

4　實驗分析

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

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

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

4.2實驗結(jié)果

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

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

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

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

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

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

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

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

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

5　結(jié)束語

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

在科學網(wǎng)博客數(shù)據(jù)集上進行了實驗，因為該數(shù)據(jù)集本身就已經(jīng)對用戶進行了社區(qū)分類，所以實驗結(jié)果主要考查算法的準確度。實驗結(jié)果表明，針對不同特點的社區(qū)，算法有不同的運行結(jié)果，如果有效地利用用戶發(fā)表的話題信息，確實能提高社區(qū)發(fā)現(xià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.

附中文參考文獻：

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

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

高克寧（1963—），女，遼寧沈陽人，2006年于東北大學計算機科學專業(yè)獲得博士學位，現(xiàn)為東北大學計算中心教授，CCF高級會員，主要研究領(lǐng)域為語義網(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—），男，遼寧沈陽人，東北大學博士研究生，東北大學計算中心教師，主要研究領(lǐng)域為社會網(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—），男，遼寧沈陽人，東北大學博士研究生，東北大學計算中心教師，主要研究領(lǐng)域為社會網(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(國家自然科學基金青年基金);the MOE-Intel Special Fund of Information Technology under Grant No.MOE-Intel-2012-06(教育部-英特爾信息技術(shù)專項科研基金);the Scientific and Technological Projects of Liaoning Province under Grant No.2013217004-1(遼寧省科技攻關(guān)項目).

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

A

TP311