基于微博媒體的社區(qū)發(fā)現(xiàn)技術(shù)研究

邢東東 王秀文

第3卷第6期2013年12月智 能 計 算 機 與 應(yīng) 用INTELLIGENT COMPUTER AND APPLICATIONSVol.3 No.6Dec.2013

摘要：微博社交網(wǎng)絡(luò)是由節(jié)點構(gòu)成的，每個節(jié)點代表一個微博用戶。節(jié)點與節(jié)點間存在著關(guān)系，因此連接緊密的節(jié)點形成了社區(qū)。如何從微博社交網(wǎng)絡(luò)中挖掘出社區(qū)，已成為Web2.0的團體挖掘研究熱點。詳細介紹了傳統(tǒng)的網(wǎng)絡(luò)團體挖掘算法，并提出了一種新的社區(qū)發(fā)現(xiàn)的算法，稱為基于用戶興趣的社區(qū)發(fā)現(xiàn)算法。該算法不論在計算效率還是社區(qū)發(fā)現(xiàn)效果上比傳統(tǒng)算法都具有明顯的提升，取得了不錯的實驗效果。

關(guān)鍵詞：社區(qū)發(fā)現(xiàn)； 團體挖掘； 用戶興趣； 微博網(wǎng)絡(luò)

中圖分類號：TP3934 文獻標(biāo)識碼：A文章編號：2095-2163（2013）06-0074-04

0引言

微博作為一種新興的社交媒體，其作為媒體平臺的影響力已經(jīng)遠超傳統(tǒng)的網(wǎng)頁、博客等媒體的作用力。例如：全球最大的社交網(wǎng)站Facebook的用戶數(shù)已經(jīng)超過10億，Twitter的用戶數(shù)也已經(jīng)超過5億。中國最大的社交網(wǎng)站平臺新浪微博注冊用戶數(shù)也已超5億，日活躍用戶數(shù)可達4 900多萬，用戶日發(fā)微博則已超過1億條。隨著Web2.0的迅猛發(fā)展，用戶之間存在了交互，有的用戶之間連接緊密、有的用戶之間連接稀疏，這就形成了虛擬社區(qū)。因此在復(fù)雜網(wǎng)絡(luò)中，挖掘團體（圈子）已經(jīng)成為時下的研究熱點。

本文先對傳統(tǒng)社區(qū)發(fā)現(xiàn)算法進行了介紹，針對微博媒體的特點，提出了一種結(jié)合用戶興趣的社區(qū)發(fā)現(xiàn)算法，同時對算法進行了詳細介紹，其后通過實驗證實了算法的有效性。

1社區(qū)發(fā)現(xiàn)的相關(guān)研究

1.1譜平分法（Spectral Bisection）[1-2]

譜平分法是一種基于圖分割（Graph Partitioning）的社區(qū)劃分算法，其基本原理是求解基于圖的Laplace矩陣的特征向量。該算法在理論上已經(jīng)得到證明，非零特征值所對應(yīng)的特征向量中，被劃分到同一社區(qū)中的節(jié)點是近似相等的。并且在已知社區(qū)為兩個社區(qū)結(jié)構(gòu)時，也取得了不錯的效果。

但是，在微博社交網(wǎng)絡(luò)中，卻也存在著明顯的不足。微博關(guān)系網(wǎng)絡(luò)不可能只存在兩個社區(qū)結(jié)構(gòu)，因此，譜平分法并不能很好地解決微博社交網(wǎng)絡(luò)的社區(qū)劃分問題。

1.2W-H算法[3]

相對于譜平分法這一類傳統(tǒng)的圖分割算法，即只能將一個網(wǎng)絡(luò)結(jié)構(gòu)劃分為兩個社區(qū)的問題，Wu和Huberman提出了一種快速譜平分法[3]，稱之為W-H算法[4]。W-H算法解決了譜平分法只能將社區(qū)結(jié)構(gòu)劃分為兩個團體的問題，該算法在不考慮整個網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的情況下，可以求解一個已知節(jié)點所在的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，而無需計算所有社區(qū)。但如果W-H算法并不知道網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的部分信息，則很難應(yīng)用該算法進行社區(qū)結(jié)構(gòu)的劃分。

1.3GN算法[5]

GN算法是由Girvan和Newman于2001年提出的社區(qū)劃分算法，該算法現(xiàn)已成為經(jīng)典的社區(qū)劃分算法。對微博社交網(wǎng)絡(luò)來說，最基本的要求就是自然分割，而無需預(yù)先確定網(wǎng)絡(luò)社區(qū)的個數(shù)以及社區(qū)的大小。這是基于一種分裂思想的社區(qū)劃分算法。其基本原理就是不斷地從網(wǎng)絡(luò)中移除介數(shù)（Betweenness）最大的邊。邊介數(shù)則定義為網(wǎng)絡(luò)中經(jīng)過每條邊的最短路徑的數(shù)目[6]。GN算法的優(yōu)點表現(xiàn)在，可以將網(wǎng)絡(luò)分裂成任意數(shù)量的社區(qū)，還可以從算法的樹狀圖查看網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)形成的動態(tài)過程，如圖1所示。

GN算法由網(wǎng)絡(luò)整體的全局結(jié)構(gòu)出發(fā)進行社區(qū)識別[7]，避免了傳統(tǒng)算法的眾多缺點，業(yè)已成為目前實現(xiàn)網(wǎng)絡(luò)社區(qū)分

析的標(biāo)準算法，因而得到了廣泛的應(yīng)用。但GN算法也存在著兩個不足，首先，該算法不能確定最后要分解的社區(qū)數(shù)目。其次，算法的計算效率不佳，最差的時間復(fù)雜度為O（m2*n）[7]，其中m，n分別為網(wǎng)絡(luò)中的邊及節(jié)點的數(shù)目。

1.4CNM算法

CNM社區(qū)發(fā)現(xiàn)算法[8]作為一種凝聚思想的團體挖掘算法，由Clauset、Newman等人所提出。該算法以模塊度為度量標(biāo)準，每次都沿著模塊度更新最大的方向進行合并。這是一種基于貪心策略的算法，在時間復(fù)雜度方面相當(dāng)于線性時間的復(fù)雜度，并已經(jīng)廣泛應(yīng)用在大型網(wǎng)絡(luò)的計算中[6]。

本文的實驗部分即利用CNM算法與本文提出的基于用戶興趣的社區(qū)發(fā)現(xiàn)算法[3]進行了對比。

1.5其他社區(qū)發(fā)現(xiàn)的算法

在最近的社會網(wǎng)絡(luò)研究中，還有學(xué)者提出了一些新的算法。

例如，Radicchi[7]等人給出了邊聚類系數(shù)（Edge Clustering Co-Efficient）的定義，并以此為基礎(chǔ)給出了快速的Radicchi算法[9]。該算法與GN算法的效果相當(dāng)，但是速度卻有了較大提升。

在很多情況下，社區(qū)很難實現(xiàn)獨立劃分，為解決這種相互重疊的社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)問題，Palla等提出了一種派系過濾算法（Clique Percolation Method，CPM）[10]。

總之，目前的社區(qū)網(wǎng)絡(luò)挖掘算法都是基于分裂或者凝聚的理念，而沒能有效利用Web2.0網(wǎng)絡(luò)自身獨具的一些特點來進行團體挖掘，為此，本文提出了一種基于用戶興趣的團體挖掘算法。

2基于用戶興趣的社區(qū)發(fā)現(xiàn)算法

上一節(jié)中介紹的傳統(tǒng)網(wǎng)絡(luò)挖掘算法已經(jīng)涵蓋了目前網(wǎng)絡(luò)研究中的通用算法，這些方法無論是計算效率、或是挖掘效果均已獲得了良好表現(xiàn)，然而對于微博網(wǎng)絡(luò)這種新媒體，因其具有一些自身特性，就使得已有算法需要進行一定的改進或研發(fā)相應(yīng)的新算法。微博的獨特之處則在于微博社交網(wǎng)絡(luò)中不僅包括關(guān)系信息，還包括用戶自身產(chǎn)生的信息。每個微博用戶具有個人簡介、自定義的標(biāo)簽屬性、教育信息、以及每天產(chǎn)生的微博文本信息。在此將這些區(qū)別于傳統(tǒng)網(wǎng)絡(luò)的額外信息稱為用戶的興趣。現(xiàn)實社會中也可以發(fā)現(xiàn)，興趣和社會關(guān)系在社區(qū)共享和交流方面起著至關(guān)重要的關(guān)鍵作用，興趣一致的用戶更容易形成社區(qū)，并通過社會關(guān)系，興趣相投的朋友還可以推薦其他朋友加入社區(qū)，這是符合現(xiàn)實社會客觀實況的。本節(jié)對該算法進行詳細介紹。

2.1 算法步驟及流程

基于用戶興趣和網(wǎng)絡(luò)拓撲的社區(qū)發(fā)現(xiàn)算法，主要分為三個部分。第一部分為構(gòu)建用戶間的拓撲關(guān)系網(wǎng)絡(luò)；第二部分是基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)，確定用戶的興趣；第三部分，采用聚類算法，根據(jù)用戶的興趣發(fā)現(xiàn)社區(qū)。

第一部分（見2.2節(jié)）——用戶間的拓撲關(guān)系網(wǎng)絡(luò)的構(gòu)建。微博社交網(wǎng)絡(luò)中每個用戶都存在著關(guān)注關(guān)系，根據(jù)關(guān)注關(guān)系可以形成用戶間的關(guān)系圖譜。另外，微博用戶A與微博用戶B之間存在轉(zhuǎn)發(fā)，@以及評論行為。這些內(nèi)容使得兩者之間產(chǎn)生了交互，因此微博用戶與用戶之間存在交互關(guān)系。

第二部分（見2.3節(jié)）——用戶興趣的確定。首先每個用戶擁有初始的興趣標(biāo)簽，然后根據(jù)用戶的關(guān)系網(wǎng)絡(luò)對興趣標(biāo)簽進行修正，以此完善用戶的標(biāo)簽。

第三部分（見2.4節(jié)）——聚類、發(fā)現(xiàn)社區(qū)。根據(jù)第二部分的用戶興趣標(biāo)簽，采用聚類算法發(fā)現(xiàn)社區(qū)。

實驗步驟流程如圖2所示。

2.2用戶間關(guān)系網(wǎng)絡(luò)的構(gòu)建

本小節(jié)在于說明如何構(gòu)建微博用戶之間的關(guān)系網(wǎng)絡(luò)。構(gòu)建網(wǎng)絡(luò)的最直接方式就是用戶間的關(guān)注關(guān)系。每個微博用戶都存在一個關(guān)注列表，根據(jù)每個用戶的關(guān)注列表，則可以構(gòu)造用戶間的關(guān)注網(wǎng)絡(luò)。但卻需考慮到這只是用戶間的簡單關(guān)注網(wǎng)絡(luò)，并不能完全反映用戶的興趣，例如，用戶關(guān)注“李開復(fù)”，但是若用戶卻從未轉(zhuǎn)發(fā)“李開復(fù)”的微博，或者“李開復(fù)”也從未轉(zhuǎn)發(fā)該粉絲的微博，則可認定二者只有簡單的關(guān)注關(guān)系，這是一種弱關(guān)系，并不能反映用戶的興趣。

綜上所述，即可選擇交互性來衡量二者之間是否存在關(guān)系。如果用戶A與用戶B存在著交互關(guān)系（A轉(zhuǎn)發(fā)B的微博，或者B轉(zhuǎn)發(fā)A的微博），就能夠認定為二者具有強關(guān)系。

首先，提取用戶A所發(fā)的全部微博的文本信息，提取其中的@，找到用戶A與其交互的人物列表。例如：Interact（A）={u1，u2，u2，u3，u3，u4…}. 表示A與u1交互1次，與u2、u3、交互2次，與u4用戶交互一次。

在此，根據(jù)用戶A與用戶B的交互次數(shù)定義A與B直接是否存在邊，如果用戶A與用戶B的交互次數(shù)超過一定的閾值，即認定A有一條指向B的邊。閾值可以設(shè)定為3、5、10等不同的數(shù)值，文中則選取3作為閾值。

2.3用戶興趣的確定

算法需要根據(jù)用戶的興趣來確定社區(qū)，因此如何定義用戶的興趣即成為本文的關(guān)鍵。文中定義用戶的興趣是關(guān)鍵詞，也就是利用關(guān)鍵詞反映用戶的興趣。每個用戶都對應(yīng)著一個標(biāo)簽向量表示其興趣。

2.3.1用戶興趣詞的構(gòu)建

每個微博用戶都有自定義的標(biāo)簽信息、簡介信息、工作信息、教育信息以及認證信息，在此將用戶的自定義的標(biāo)簽（Tag）、用戶的簡介信息（Description）、工作信息（Work）、教育信息（Education）以及認證信息（Vertify），組成文本，再通過分詞提取用戶的興趣關(guān)鍵詞，組成用戶的標(biāo)簽向量。例如，T（A）={w1，w2，…，wn}。文中即使用{w1，w2，…，wn}刻畫用戶A的興趣。

2.3.2用戶興趣詞的修正

微博用戶的個人注冊信息，可能不全。例如，一些用戶沒有自定義標(biāo)簽或者并未填寫背景信息等，就會導(dǎo)致用戶的標(biāo)簽向量為空。還有一種可能是用戶自定義的標(biāo)簽不準確，例如很多用戶的標(biāo)簽為“80后”，“音樂”等，并不能充分反映用戶的興趣。針對上述問題，本文采用了一種基于標(biāo)簽傳播思想的算法解決了這一問題，具體如圖3所示。

由圖3可見，用戶1與用戶2， 3 ，4 ，5， 6存在交互，文中的方法是通過用戶2， 3， 4， 5， 6的標(biāo)簽去修正用戶1的標(biāo)簽。修正方法是提取用戶2， 3， 4， 5， 6出現(xiàn)的所有標(biāo)簽，按詞頻從大到小排序，并提取Top K個出現(xiàn)頻率最高的詞作為用戶1的標(biāo)簽。對網(wǎng)絡(luò)中的每一個點迭代計算，直到每個用戶的標(biāo)簽不再變化為止。修正標(biāo)簽結(jié)束。

現(xiàn)給出算法流程如下：

Step1：找到與節(jié)點A有邊聯(lián)系的鄰居節(jié)點，形成鄰居節(jié)點集合S，S中的這些節(jié)點代表了與用戶A有過互動行為的用戶集合，同時將A也放入集合S中；

Step2：統(tǒng)計集合S所有用戶中出現(xiàn)過的不同標(biāo)簽的頻次，用戶A本身初始的標(biāo)簽按照頻次f參與計數(shù)，即給用戶本身的標(biāo)簽設(shè)定一個較大的初始頻次；

Step3：將step2獲得的標(biāo)簽按照其頻次和標(biāo)簽的IDF值使用IF.IDF的計算方式確定其權(quán)重，并按照權(quán)重得分高低相應(yīng)排序，取Top K標(biāo)簽作為節(jié)點A的新標(biāo)簽集合；

Step4：直到標(biāo)簽不再變化或者達到迭代次數(shù)為止。

算法的優(yōu)點是：

（1）通過引入TF.IDF影響因子，濾去了很多共有的標(biāo)簽，例如“音樂”，“電影”，“80后”等，強化了節(jié)點的特有屬性。

（2）結(jié)合了交互網(wǎng)絡(luò)圖譜，使其自身的標(biāo)簽屬性得到了修正，解決了一些用戶沒有自定義標(biāo)簽或者自定義的標(biāo)簽不足的問題。

2.4聚類及社區(qū)發(fā)現(xiàn)

根據(jù)2.3節(jié)的標(biāo)簽傳播算法，每個網(wǎng)絡(luò)節(jié)點都有一個標(biāo)簽向量。本節(jié)根據(jù)用戶的標(biāo)簽向量來計算用戶之間的相似度，而后采用K-Means聚類[11]，對社區(qū)進行劃分。

2.4.1用戶相似度計算方法

如果微博用戶A有n個標(biāo)簽，則用戶A的標(biāo)簽向量為T（A）={w1，w2，…，wn}，網(wǎng)絡(luò)中的每一個用戶均用向量表示，則兩個用戶之間相似度定義為兩個標(biāo)簽向量Jaccard系數(shù)：

其中，I1，I2分別表示兩個微博用戶，I1∩I2表示兩個用戶共有的標(biāo)簽，I1∪I2表示兩個用戶總共的不同標(biāo)簽數(shù)。

2.4.2聚類

通過2.4.1計算每個用戶之間的相似度，組成了一個相似性矩陣，根據(jù)相似性矩陣，可以采用K-Means聚類的方法對節(jié)點進行聚類。

算法流程：

（1）先隨機選擇K個節(jié)點當(dāng)做中心，為初始社區(qū)。

（2）將網(wǎng)絡(luò)中的每一個節(jié)點劃分到與其相似度最大的那個中心，即形成初步的社區(qū)。

（3）重新計算社區(qū)的中心。社區(qū)的中心為社區(qū)內(nèi)的其他點到其均方誤差最小的那一點。

（4）重復(fù)（2）、（3），直到每個社區(qū)內(nèi)的點不再變化為止。

3社區(qū)發(fā)現(xiàn)算法效果評價

本節(jié)將對文中提出的算法和傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法（CNM算法）進行對比，無論在算法性能還是社區(qū)發(fā)現(xiàn)效果上均獲得了很大提高。

3.1數(shù)據(jù)集描述

利用微博網(wǎng)絡(luò)爬蟲，隨機選擇一批種子節(jié)點，爬取了1 500個人物的基本信息，稱為User。其中，包括人物的ID，昵稱（Screenname）、自定義標(biāo)簽（Tag）、描述信息（Description）、工作信息（Work）、教育信息（Education），以及人物的關(guān)系數(shù)據(jù)（微博上的關(guān)注列表）。另外，還有微博文本信息，將其稱為Status， 其中，包括微博mid、微博文本（Text）、原創(chuàng)微博的mid，以及原創(chuàng)微博的文本（Text）。

3.2實驗

在此，基于3.1節(jié)描述的數(shù)據(jù)集，在其上進行算法試驗，利用本文提出的算法和CNM算法進行對比實驗。

對微博文本進行預(yù)處理，提取@關(guān)系，形成用戶間的交互網(wǎng)絡(luò)，如果用戶之間@的次數(shù)超過M次，則定義之間存在邊。M取值的不同，構(gòu)建了不同交互強度的網(wǎng)絡(luò)拓撲。文中規(guī)定當(dāng)M=0時，定義網(wǎng)絡(luò)為關(guān)注網(wǎng)絡(luò)，而不是交互網(wǎng)絡(luò)。因為本算法采用了K-Means聚類的思想，則可依據(jù)CNM算法所劃分的團體個數(shù)設(shè)定K的取值，也就是說，兩個算法所劃分的團體的個數(shù)相同，社區(qū)內(nèi)的節(jié)點卻各有不同。

其中，當(dāng)M=0時，網(wǎng)絡(luò)中存在95 020條關(guān)系；M=3時，網(wǎng)絡(luò)中存在25 259條關(guān)系；M=5時，網(wǎng)絡(luò)中存在15 453條關(guān)系。在三個網(wǎng)絡(luò)中分別使用CNM算法和本算法進行實驗對比。

3.3效果評價

通過實驗，將本文提出的基于用戶興趣的社區(qū)發(fā)現(xiàn)算法與CNM算法在計算效率和算法效果上進行對比。其中，計算效率是指算法的運行時間。社區(qū)劃分的效果，則采用每個劃分的圈子中，用戶的平均交互次數(shù)作為評價標(biāo)準。因此，算法的運行時間越短、每個社區(qū)內(nèi)的用戶的交互越頻繁，就表明社區(qū)劃分效果越好。實驗結(jié)果如表1和表2所示。

通過實驗對比發(fā)現(xiàn)，本文所采用的基于用戶興趣的社區(qū)發(fā)現(xiàn)算法，在計算效率方面比傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法高，其算法的計算復(fù)雜度為線性時間復(fù)雜度，因而適合大規(guī)模的網(wǎng)絡(luò)計算。在算法效果方面，其劃分的社區(qū)內(nèi)用戶的交互比傳統(tǒng)算法劃分的社區(qū)交互更為頻繁，因此，整體效果要優(yōu)于傳統(tǒng)算法。

4結(jié)束語

在Web2.0媒體的社交網(wǎng)絡(luò)中，挖掘團體，社區(qū)發(fā)現(xiàn)具有重要的價值，而識別團體算法的計算效率以及團體識別的準確率則非常重要。本文所采用的數(shù)據(jù)集只是一個局部數(shù)據(jù)集，如果在大規(guī)模數(shù)據(jù)集上進行運算，必然能對用戶興趣模型進行更為優(yōu)異的刻畫，而大規(guī)模計算技術(shù)則可以采用目前流行的Hadoop（Map/Reduce）[12]框架，而這也是今后研究發(fā)展的重點和熱點。

參考文獻：

[1]FIEDLER M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal， 1973， 23（2）： 298-305.

[2]POTHEN A， SIMON H D， LIOU K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on Matrix Analysis and Applications， 1990， 11（3）： 430-452.

[3]薄輝. 社區(qū)發(fā)現(xiàn)技術(shù)的研究與實現(xiàn) [D]. 北京： 北京交通大學(xué)， 2009.

[4]WU F， HUBERMAN B A. Finding communities in linear time： a physics approach[J]. The European Physical Journal B-Condensed Matter and Complex Systems， 2004， 38（2）： 331-338.

[5]GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences， 2002， 99（12）： 7821-7826.

[6]韓瑞凱， 孟嗣儀， 劉云， 等. 基于興趣相似度的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法研究[J]. 鐵路計算機應(yīng)用， 2010 （10）： 10-14.

[7]汪小帆. 復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)分析算法研究綜述[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2005 （3）： 1-12.

[8]CLAUSET A， NEWMAN M E J， MOORE C. Finding community structure in very large networks. Phys. Rev. E，2004，70：66-111.

[9]PALLA G， DERNYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature， 2005， 435（7043）： 814-818.

[10]DERNYI I， PALLA G， VICSEK T. Clique percolation in random networks[J]. Physical review letters， 2005， 94（16）： 160-202.

[11]TEKNOMO K. K-Means Clustering Tutorial[J]. Medicine， 2006， 100（4）： 3.

[12]BORTHAKUR D. The hadoop distributed file system： Architecture and design[J]. Hadoop Project Website， 2007， 11： 21.