邢東東 王秀文

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

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

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

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

0引言

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

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

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

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

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

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

1.2W-H算法[3]

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

1.3GN算法[5]

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

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

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

1.4CNM算法

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

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

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

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

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

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

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

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

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

2.1 算法步驟及流程

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

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

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

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

實(shí)驗(yàn)步驟流程如圖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)系。每個(gè)微博用戶都存在一個(gè)關(guān)注列表，根據(jù)每個(gè)用戶的關(guān)注列表，則可以構(gòu)造用戶間的關(guān)注網(wǎng)絡(luò)。但卻需考慮到這只是用戶間的簡(jiǎn)單關(guān)注網(wǎng)絡(luò)，并不能完全反映用戶的興趣，例如，用戶關(guān)注“李開復(fù)”，但是若用戶卻從未轉(zhuǎn)發(fā)“李開復(fù)”的微博，或者“李開復(fù)”也從未轉(zhuǎn)發(fā)該粉絲的微博，則可認(rèn)定二者只有簡(jiǎn)單的關(guān)注關(guān)系，這是一種弱關(guān)系，并不能反映用戶的興趣。

綜上所述，即可選擇交互性來衡量二者之間是否存在關(guān)系。如果用戶A與用戶B存在著交互關(guān)系（A轉(zhuǎn)發(fā)B的微博，或者B轉(zhuǎn)發(fā)A的微博），就能夠認(rèn)定為二者具有強(qiáng)關(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ù)超過一定的閾值，即認(rèn)定A有一條指向B的邊。閾值可以設(shè)定為3、5、10等不同的數(shù)值，文中則選取3作為閾值。

2.3用戶興趣的確定

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

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

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

2.3.2用戶興趣詞的修正

微博用戶的個(gè)人注冊(cè)信息，可能不全。例如，一些用戶沒有自定義標(biāo)簽或者并未填寫背景信息等，就會(huì)導(dǎo)致用戶的標(biāo)簽向量為空。還有一種可能是用戶自定義的標(biāo)簽不準(zhǔn)確，例如很多用戶的標(biāo)簽為“80后”，“音樂”等，并不能充分反映用戶的興趣。針對(duì)上述問題，本文采用了一種基于標(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個(gè)出現(xiàn)頻率最高的詞作為用戶1的標(biāo)簽。對(duì)網(wǎng)絡(luò)中的每一個(gè)點(diǎn)迭代計(jì)算，直到每個(gè)用戶的標(biāo)簽不再變化為止。修正標(biāo)簽結(jié)束。

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

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

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

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

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

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

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

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

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

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

2.4.1用戶相似度計(jì)算方法

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

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

2.4.2聚類

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

算法流程：

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

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

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

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

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

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

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

利用微博網(wǎng)絡(luò)爬蟲，隨機(jī)選擇一批種子節(jié)點(diǎn)，爬取了1 500個(gè)人物的基本信息，稱為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實(shí)驗(yàn)

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

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

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

3.3效果評(píng)價(jià)

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

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

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

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

參考文獻(xiàn)：

[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ù)的研究與實(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]. 鐵路計(jì)算機(jī)應(yīng)用， 2010 （10）： 10-14.

[7]汪小帆. 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(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.