結合用戶生成內容與鏈接關系的社區發現算法*

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

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

結合用戶生成內容與鏈接關系的社區發現算法*

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

東北大學 計算中心，沈陽 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.

社區發現一直是社會網絡研究中的熱點內容。但是當前社區發現算法更加關注用戶與用戶之間的鏈接關系，而對社會網絡中用戶生成內容（user generated contents,UGC）大數據研究較少。用戶生成內容是Web2.0的特點，也是社會網絡平臺吸引用戶的重要原因之一，對社區的形成起著重要作用。提出了一種新的社區發現算法，能夠綜合利用用戶與用戶之間的鏈接關系以及用戶生成內容來確定用戶的社區劃分。該算法用LDA（latent Dirichlet allocation）算法分析用戶生成內容中主要的內容形式——文本信息，同時通過譜分析方法分析用戶與用戶之間的鏈接關系，并有機結合以發現網絡的社區結構。通過分析科學網的真實數據，證明了所提算法能夠有效綜合利用用戶生成內容與用戶鏈接關系，使社區發現的結果更加客觀準確。

社區發現；用戶生成內容；用戶鏈接關系；社會網絡

1　引言

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

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

本文組織結構如下：第2章介紹相關的工作；第3章對本文算法進行詳細討論；第4章介紹實驗結果；最后對本文工作進行總結。

2　相關工作

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

由上面的綜述可見，雖然在社區發現方面已經有了豐碩的研究成果，科研人員也用不同的理論方法來解決社區發現問題，但是當前的研究還是以對社會網絡圖結構的分析為基礎，沒有充分利用社會網絡中豐富的用戶生成內容。

3　結合網絡結構與文本內容的社區發現算法

本文充分利用社區網絡中的大數據，包括用戶之間的好友關系以及用戶生成內容（用戶發表文本內容信息），提出了一種結合網絡結構與文本內容的社區發現算法。

3.1基于網絡結構的社區發現

本節介紹基于網絡結構的社區發現算法。網絡結構是社區發現的基礎，本文擬直接采取當前研究中比較成熟的基于結構的社區發現算法——譜分析社區發現算法[6]。譜分析又稱譜聚類，首先將一個圖結構轉化為對應的拉普拉斯矩陣，給定社會網絡圖結構G，G的拉普拉斯矩陣的特征值中0特征值出現的次數等于圖中不連通區域的個數。對于每一個非連通圖，可以對每個連通子圖建立拉普拉斯矩陣。事實上，在真實的社會網絡結構中，不同社區幾乎不可能完全不相連。如果圖為連通圖，拉普拉斯矩陣只有一個特征值為0。如果整個社會網絡圖結構由幾個不連通的子圖構成，那么G對應的拉普拉斯矩陣為0的特征值等于子圖的個數。因此可以利用拉普拉斯矩陣的前幾個最小的特征值進行聚類，聚類結果中的每一個簇（cluster）就相當于一個社區。算法1是標準譜聚類算法的一般步驟。

算法1基于網絡結構信息社區發現算法

輸入：社會網絡圖G=(V,E)。

輸出：社會網絡的k個聚類（社區）。

（1）根據社會網絡圖結構，構建拉普拉斯矩陣；

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

（3）利用前k個特征值對應的特征向量來對社會網絡進行聚類；

（4）返回社會網絡的聚類結果（社區）。

3.2結合網絡結構與文本內容的社區發現算法

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

假設用戶發表的內容以文檔形式存在（如用戶發表的一篇博客就相當于一個文檔），利用LDA算法進行話題發現的思想[18]，假設D個文檔中存在T個話題，則對于文檔集中的任一篇文檔di，都可以看作是T個話題的多項式分布，而其中每個話題Tk又都可以看作是在文檔中i個詞匯上的多項式分布。即假設有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）可以進一步表示為：

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

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

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

根據用戶與用戶之間的相關性Cor(uij)，可以得到帶有權重的拉普拉斯矩陣，在此矩陣上使用譜方法進行社區發現，則同時利用了社會網絡上的話題信息以及結構信息，能夠更加準確地進行社區發現。因此，本文提出的綜合利用網絡結構與用戶內容的社區發現算法如算法2所示。

算法2結合網絡結構與話題信息社區發現算法

輸入：社會網絡圖G=(V,E)，用戶發表文檔集合D以及用戶與文檔之間的關系。

輸出：社會網絡的k個聚類（社區）。

（1）基于LDA話題發現方法及圖結構信息，計算用戶與用戶之間的相關性Cor(uij)；

（2）根據Cor(uij)信息構建拉普拉斯矩陣；

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

（4）利用前k個特征值對應的特征向量來對社會網絡進行聚類；

（5）返回社會網絡的聚類結果（社區）。

4　實驗分析

4.1數據描述

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

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

4.2實驗結果

實驗比較了基于結構的社區發現以及基于結構和話題模型的社區發現算法的社區發現準確率。基于結構的算法即基于博客用戶與博客用戶之間的好友關系使用算法1進行社區發現，以下簡稱CD-ST（community discovery based on structure）；基于結構和話題模型的社區發現算法即通過分析博客用戶和博客用戶之間的好友關系，以及博客用戶發表博文內容，使用算法2進行社區發現，以下簡稱CD-TS（community discovery based on topic&structure）。因為科學網博客中已知社區結構，所以準確率的公式定義如下：

cd表示使用算法發現的博客用戶集合；Total為全部用戶。

實驗比較兩種社區發現算法的準確率變化，其中α為式（5）中的調節系數，α值表明在算法2中基于話題與基于結構對應算法結果的貢獻程度。α越大，表明算法中話題對于社區發現所占的比重越大；α為0，表示只基于結構進行社區發現；α為1，表明只基于話題進行社區發現。

圖1比較了兩種算法的準確率，其中CD-ST是基于網絡結構的社區發現算法，這里沒有調節系數，因此該算法的準確率不隨α的變化而變化。

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

圖2記錄了當α值變化時（α=0，α=0.6和α=1.0），各個社區發現結果的準確率。其中α=0相當于只基于結構進行社區發現，α=1.0相當于只基于話題進行社區發現。

Fig.1　Precision of two algorithms on scientific network data set圖1　兩種算法在科學網數據集上的準確率

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

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

5　結束語

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

在科學網博客數據集上進行了實驗，因為該數據集本身就已經對用戶進行了社區分類，所以實驗結果主要考查算法的準確度。實驗結果表明，針對不同特點的社區，算法有不同的運行結果，如果有效地利用用戶發表的話題信息，確實能提高社區發現的準確度。

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]楊靜,辛宇,謝志強.基于話題綜合因子分析的語義社會網絡社區發現算法[J].計算機研究與發展,2014,51(3): 559-569.

張恩德（1980—），男，遼寧海城人，2014年于東北大學計算機科學專業獲得博士學位，現為東北大學計算中心教師，CCF會員,主要研究領域為社會網絡，機器學習等。

高克寧（1963—），女，遼寧沈陽人，2006年于東北大學計算機科學專業獲得博士學位，現為東北大學計算中心教授，CCF高級會員，主要研究領域為語義網絡，信息系統等。

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—），男，遼寧沈陽人，東北大學博士研究生，東北大學計算中心教師，主要研究領域為社會網絡中的數據挖掘。

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—），男，遼寧沈陽人，東北大學博士研究生，東北大學計算中心教師，主要研究領域為社會網絡中的數據挖掘。

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(教育部-英特爾信息技術專項科研基金);the Scientific and Technological Projects of Liaoning Province under Grant No.2013217004-1(遼寧省科技攻關項目).

CNKI網絡優先出版：2015-06-29,http://www.cnki.net/kcms/detail/11.5602.TP.20150629.1544.002.html

A

TP311