基于節(jié)點(diǎn)聚集系數(shù)的分布式標(biāo)簽傳播算法

張素智 孫嘉彬 王 威

基于節(jié)點(diǎn)聚集系數(shù)的分布式標(biāo)簽傳播算法

張素智 孫嘉彬 王 威

(鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院 河南 鄭州 450002)

隨著互聯(lián)網(wǎng)的發(fā)展和普及，越來(lái)越多的用戶加入到社交網(wǎng)絡(luò)，逐漸形成了大規(guī)模、多樣化的社區(qū)。對(duì)于新浪微博等社交服務(wù)來(lái)說(shuō)，這些社區(qū)的發(fā)現(xiàn)可以為用戶和商家提供有價(jià)值的信息。在社區(qū)發(fā)現(xiàn)算法中，標(biāo)簽傳播算法(LPA算法)具有算法思想簡(jiǎn)單、復(fù)雜度低、無(wú)需初始化社區(qū)數(shù)量等優(yōu)點(diǎn)，但準(zhǔn)確率較低，同時(shí)在大數(shù)據(jù)環(huán)境下，效率還不夠高。將節(jié)點(diǎn)聚類系數(shù)引入LPA的標(biāo)簽更新過(guò)程中，提出一種結(jié)合MapReduce分布式計(jì)算框架的社區(qū)發(fā)現(xiàn)算法——DisLPA算法。實(shí)驗(yàn)表明，該算法不僅提高了準(zhǔn)確率，同時(shí)有效改善了計(jì)算瓶頸問(wèn)題。

社區(qū)發(fā)現(xiàn) 標(biāo)簽傳播 聚集系數(shù) MapReduce

0 引 言

近年來(lái)，隨著Web2.0的逐漸興起，社交網(wǎng)絡(luò)(SNS)的使用變得越來(lái)越普遍，越來(lái)越多的人利用SNS擴(kuò)展個(gè)人交際圈，同時(shí)發(fā)布、查找和共享信息，吸引更多的人去關(guān)注熱點(diǎn)信息。新浪發(fā)布的2012年第三季度財(cái)報(bào)顯示，截止到2012年12月底，新浪微博注冊(cè)用戶數(shù)已超5億，平均每天活躍用戶達(dá)到4620萬(wàn)。這些用戶發(fā)布文字、圖片、視頻，轉(zhuǎn)發(fā)微博，搜索信息，關(guān)注其他人等等都會(huì)產(chǎn)生大量的數(shù)據(jù)，這對(duì)數(shù)據(jù)分析帶來(lái)了巨大的挑戰(zhàn)，這個(gè)挑戰(zhàn)[1]不僅是數(shù)據(jù)量膨脹的問(wèn)題，而且涉及到數(shù)據(jù)深度分析需求的增長(zhǎng)。

對(duì)SNS社區(qū)進(jìn)行挖掘，可以發(fā)現(xiàn)網(wǎng)絡(luò)社區(qū)中的潛在的社區(qū)結(jié)構(gòu)，從而對(duì)用戶角色進(jìn)行評(píng)估，擴(kuò)展社交圈，以實(shí)現(xiàn)高效準(zhǔn)確的個(gè)性化推薦，同時(shí)能夠提供精準(zhǔn)的商業(yè)定位，為商家?guī)?lái)更大的商機(jī)。但是在線網(wǎng)絡(luò)社區(qū)數(shù)據(jù)具有龐大性、稀疏性、流動(dòng)性，這些特性使得社交網(wǎng)絡(luò)尤為復(fù)雜。目前，不同領(lǐng)域的眾多研究者對(duì)復(fù)雜網(wǎng)絡(luò)的基本統(tǒng)計(jì)特性做了很多研究，如小世界效應(yīng)[2](具有短路徑長(zhǎng)度和高聚類系數(shù)特點(diǎn))，無(wú)標(biāo)度特性[3](節(jié)點(diǎn)度服從冪函數(shù)分布)，聚類特性[4](同社區(qū)內(nèi)節(jié)點(diǎn)連接較為緊密)。

目前的社區(qū)挖掘大致分為基于優(yōu)化的方法和基于啟發(fā)式的方法[5]兩種。局部搜索方法和譜方法是基于優(yōu)化的方法中兩類最主要的方法。在基于優(yōu)化的方法中，典型的有譜平分算法，GA(Guimera-Amaral)算法，F(xiàn)N(Fast Newman)算法等，它們都是將復(fù)雜網(wǎng)絡(luò)的問(wèn)題轉(zhuǎn)化為優(yōu)化目標(biāo)函數(shù)來(lái)計(jì)算復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)?；趩l(fā)式方法的共同特點(diǎn)是：在優(yōu)化目標(biāo)不明確的前提下，設(shè)計(jì)和運(yùn)用合理的啟發(fā)式規(guī)則來(lái)識(shí)別網(wǎng)絡(luò)社區(qū)，如GN(Girvan-Newman)算法、MFC算法、HITS算法、CPM算法等。

為了改善社區(qū)發(fā)現(xiàn)算法復(fù)雜度高的問(wèn)題，Raghavan等人提出了一種啟發(fā)式的，基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法(LPA)[6]，具有近似線性的時(shí)間復(fù)雜度，目前在眾多的社區(qū)發(fā)現(xiàn)算法中效率最高。

很多學(xué)者對(duì)標(biāo)簽傳播算法進(jìn)行了改進(jìn)和優(yōu)化。利用特征空間嵌入實(shí)現(xiàn)數(shù)據(jù)點(diǎn)的稀疏重構(gòu)能反映數(shù)據(jù)點(diǎn)與特征空間嵌入間的本質(zhì)相似性結(jié)構(gòu)的特點(diǎn)，陶劍文等人[7]提出了一種稀疏近似最近特征空間嵌入標(biāo)簽傳播的方法，使得預(yù)測(cè)的數(shù)據(jù)標(biāo)簽具有平滑性和魯棒性。王庚等人[8]提出了一種基于標(biāo)簽傳播的穩(wěn)定重疊社區(qū)挖掘算法(soCLP)，該方法引入平衡因子對(duì)算法的穩(wěn)定性進(jìn)行控制，以解決重疊社區(qū)挖掘中效率與穩(wěn)定性的沖突。

但是由于現(xiàn)如今激增的SNS用戶和這些用戶產(chǎn)生的大數(shù)據(jù)，傳統(tǒng)的LPA算法來(lái)分析那些具有龐大節(jié)點(diǎn)數(shù)的社區(qū)效率較低，只靠單一的計(jì)算結(jié)點(diǎn)無(wú)法滿足這樣的計(jì)算需求，此時(shí)就需要多個(gè)并行的結(jié)點(diǎn)來(lái)進(jìn)行處理。

為了解決因節(jié)點(diǎn)數(shù)增加等問(wèn)題引起的挖掘算法效率低下的問(wèn)題，趙雅端等人[9]將傳統(tǒng)Newman算法并行化，并應(yīng)用在GPU并行計(jì)算中，使得傳統(tǒng)的社區(qū)挖掘算法在不失準(zhǔn)確性的前提下運(yùn)行效率有了提高。宋玨等人[10]提出了一種基于日志聚類的郵件網(wǎng)絡(luò)社區(qū)挖掘算法LENCM，該算法在維持執(zhí)行效率的基礎(chǔ)下提高了挖掘社區(qū)的質(zhì)量。

本文提出了一種基于MapReduce的分布式LPA社區(qū)發(fā)現(xiàn)算法——DisLPA，在提高準(zhǔn)確率的基礎(chǔ)上，有效改善了計(jì)算瓶頸問(wèn)題。

1 相關(guān)工作

1.1 LPA算法

標(biāo)簽傳播算法(LPA)的思想是根據(jù)已標(biāo)記節(jié)點(diǎn)的標(biāo)簽信息去預(yù)測(cè)未標(biāo)記節(jié)點(diǎn)的標(biāo)簽。它是由Zhu等人[11]率先提出的一種基于圖的半監(jiān)督學(xué)習(xí)方法。2007年Raghavan等人[6]根據(jù)標(biāo)簽傳播的思想，提出了基于標(biāo)簽傳播思想的社區(qū)發(fā)現(xiàn)算法。算法基本思想：一個(gè)節(jié)點(diǎn)x，它的k個(gè)鄰居節(jié)點(diǎn)分別為x1,x2,…,xk，每個(gè)鄰居節(jié)點(diǎn)對(duì)應(yīng)的label為l1,l2,…,lk，這些鄰居節(jié)點(diǎn)共同決定了x所在的社區(qū)。該算法流程為：

(1) 首先初始化節(jié)點(diǎn)label，將每個(gè)節(jié)點(diǎn)賦予一個(gè)唯一的label，此label代表社區(qū)標(biāo)識(shí)，即初始化之后每個(gè)節(jié)點(diǎn)自身為一個(gè)社區(qū)。

(2) 以迭代的方式更新圖中所有的節(jié)點(diǎn)。迭代規(guī)則為：節(jié)點(diǎn)x的所有鄰居節(jié)點(diǎn)x1,x2,…,xk中，對(duì)應(yīng)的label為l1,l2,…,lk出現(xiàn)次數(shù)最多的那個(gè)label傳遞給節(jié)點(diǎn)x。當(dāng)出現(xiàn)num[max(l1,l2,…,lk)]≥2的情況時(shí)，將任意一個(gè)節(jié)點(diǎn)的label作為x的label。

(3) 反復(fù)執(zhí)行步驟(2)，直到每個(gè)節(jié)點(diǎn)的label都不再變化或者達(dá)到最大迭代次數(shù)為止。

(4) 若兩個(gè)節(jié)點(diǎn)具有相同的label，那么認(rèn)為這兩個(gè)節(jié)點(diǎn)在同一個(gè)社區(qū)。

節(jié)點(diǎn)標(biāo)簽值更新步驟如圖1所示。

圖1 節(jié)點(diǎn)label更新步驟

如圖1所示，節(jié)點(diǎn)label的傳遞是一個(gè)迭代的過(guò)程，每一次迭代，節(jié)點(diǎn)的label就會(huì)根據(jù)其鄰居節(jié)點(diǎn)的label進(jìn)行更新。這個(gè)更新的過(guò)程分為同步更新和異步更新兩種。

在同步更新中，節(jié)點(diǎn)x在第t次迭代的label值lx取決于其鄰居節(jié)點(diǎn)在第t-1次迭代使所得的label，即：

lx(t)=f(lx1(t-1),…,lxk(t-1))

其中，lx(t)表示節(jié)點(diǎn)x在第t次迭代時(shí)label，f函數(shù)的返回值是在x的鄰居節(jié)點(diǎn)的label里出現(xiàn)次數(shù)最高的那個(gè)label。然而在同步更新過(guò)程中可能會(huì)出現(xiàn)圖2中的無(wú)限迭代的情形，從而無(wú)法得到社區(qū)結(jié)構(gòu)。

圖2 同步更新震蕩情況

在異步更新中，節(jié)點(diǎn)在第t次迭代時(shí)的label不僅僅取決于第t次迭代更新過(guò)的label，同時(shí)和剩下未進(jìn)入t次迭代的鄰居節(jié)點(diǎn)在t-1次迭代的label有關(guān)，即lx(t)=f(lxi1(t),…,lxin(t),lxi(n+1)(t-1),…,lxk(t-1))其中xi1,…,xin表示在t次(本次)迭代中更新過(guò)label的節(jié)點(diǎn)，xi(n+1),…,xik表示在本次迭代中還沒(méi)有更新的節(jié)點(diǎn)，f同上。

近年來(lái)，有研究人員不斷地對(duì)LPA社區(qū)挖掘算法進(jìn)行了改進(jìn)和優(yōu)化。Leung等人[12]使用LPA算法來(lái)分析大規(guī)模在線網(wǎng)絡(luò)，其實(shí)驗(yàn)預(yù)示了標(biāo)簽傳播算法是一種快速有效的社區(qū)發(fā)現(xiàn)算法，在處理超大規(guī)模復(fù)雜網(wǎng)絡(luò)方面潛力巨大。Barber等人[13]為了避免所有的節(jié)點(diǎn)都分配到一個(gè)社區(qū)，設(shè)計(jì)了一個(gè)帶約束條件的標(biāo)簽傳播算法LPAm，將社區(qū)發(fā)現(xiàn)算法轉(zhuǎn)化為目標(biāo)函數(shù)優(yōu)化的問(wèn)題，但是該算法會(huì)有陷入局部最大值的趨勢(shì)，這會(huì)導(dǎo)致社區(qū)發(fā)現(xiàn)不準(zhǔn)確。針對(duì)這個(gè)問(wèn)題，Liu等人[14]將LPAm與多步層次貪婪算法MSG(Multi-step Greedy Agglomerative Algorithm)相結(jié)合，提出了一個(gè)模塊化，分層化的標(biāo)簽傳播算法LPAm+，使LPA類算法的性能得到進(jìn)一步改善。

1.2 MapReduce計(jì)算模型

MapReduce是由Google公司最早提出的，它是一種用于海量數(shù)據(jù)計(jì)算(大于1T)的并行運(yùn)算模型，最初被Google應(yīng)用于Google搜索引擎的服務(wù)器集群中[15]，實(shí)時(shí)進(jìn)行龐大的搜索數(shù)據(jù)計(jì)算。Map和Reduce兩個(gè)程序構(gòu)成了MapReduce的整體架構(gòu)，其中Map程序?qū)nput的數(shù)據(jù)切分成各類型的小塊，并分配給大量的服務(wù)器處理；Reduce程序?qū)ap處理后的結(jié)果匯總整理后輸出給客戶端[16]。MapReduce的執(zhí)行流程如圖3所示。

在編程的時(shí)候，需要編寫Map和Reduce這兩個(gè)主要函數(shù)[17]。

Map:→list

Reduce:>→list

圖3 MapReduce執(zhí)行流程

MapReduce可以充分發(fā)揮普通計(jì)算機(jī)集群的計(jì)算能力，以解決單一普通計(jì)算機(jī)由于處理器以及存儲(chǔ)資源的限制而無(wú)法高效處理海量數(shù)據(jù)計(jì)算的問(wèn)題。

2 基于LPA的分布式社區(qū)發(fā)現(xiàn)算法

2.1 基本思想

本文采用MapReduce分布式編程模型來(lái)設(shè)計(jì)分布式LPA算法——DisLPA，從而解決計(jì)算的瓶頸問(wèn)題。

該算法編程模型分為三個(gè)階段[18]：

(1) 從輸入文件讀取的元數(shù)據(jù)轉(zhuǎn)化成鍵值對(duì)(map階段)。Map功能可以創(chuàng)建并輸出一個(gè)任意數(shù)量的key/value鍵值對(duì)[(l1,w1),…,(lr,wr)]。

(2) 所有輸入數(shù)據(jù)的鍵值對(duì)根據(jù)他們的key值排序(combiner階段)。

(3) 其中每個(gè)key和他所有關(guān)聯(lián)的value值[u1,…,us]傳遞給reduce函數(shù)(某一Hadoop節(jié)點(diǎn)上的)調(diào)用，用來(lái)創(chuàng)建一個(gè)輸出的key-value鍵值對(duì)[(m1,x1),…,(mt,xt)](reduce階段，見(jiàn)(2))。整個(gè)過(guò)程中，輸出的key值不需要匹配輸入的key，它們不必是相同的。

2.2 算法步驟

在標(biāo)簽傳播算法中，通常將網(wǎng)絡(luò)抽象為一個(gè)簡(jiǎn)單的無(wú)向圖G(V,E)，其中V表示節(jié)點(diǎn)(或頂點(diǎn)Vertex)的集合，E表示邊(Edge)的集合，同時(shí)，集合中的每一條邊都與集合V中的一對(duì)節(jié)點(diǎn)相對(duì)應(yīng)。|V|表示圖的階，即節(jié)點(diǎn)集合中節(jié)點(diǎn)的個(gè)數(shù)，|E|表示圖的邊數(shù)，即邊集合中邊的條數(shù)。節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合Ni(j)可以表示為：

Ni(j)={j:j∈V,(i,j)∈E}

第一次更新節(jié)點(diǎn)label時(shí)，每個(gè)label都是唯一的，更新的原則是在鄰居節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)進(jìn)行更新，在第一次更新后，大約90%的節(jié)點(diǎn)會(huì)劃分到最終所屬的社區(qū)。因此，第一次節(jié)點(diǎn)label更新時(shí)的選擇會(huì)直接影響最終的社區(qū)劃分結(jié)果。這極大地降低了算法的魯棒性，同時(shí)影響了社區(qū)劃分的準(zhǔn)確性。

為了解決這一問(wèn)題，本文對(duì)每個(gè)label增加權(quán)值，用節(jié)點(diǎn)聚集系數(shù):

(1)

來(lái)衡量節(jié)點(diǎn)的影響力，n表示在節(jié)點(diǎn)i的所有k個(gè)鄰居間的邊數(shù)。將加入了節(jié)點(diǎn)聚集系數(shù)的標(biāo)簽傳播算法記為CLPA算法。

LPA算法的每一次迭代，要執(zhí)行更新頂點(diǎn)label的操作。對(duì)于每個(gè)分區(qū)，我們需要運(yùn)行幾個(gè)帶來(lái)大開(kāi)銷的map-reduce進(jìn)程，因此我們將所有的分區(qū)并行計(jì)算，來(lái)取代將整體進(jìn)行計(jì)算的方式。

算法DisLPA的具體步驟如下：

(1) 首先，初始化。DisLPA為每個(gè)頂點(diǎn)i分配一個(gè)唯一的label，將label初始化為頂點(diǎn)的id，即初始化不同的label，即li=i，此處，i表示節(jié)點(diǎn)i的id。將迭代次數(shù)初始化為p=1。

(2) Map進(jìn)程：將節(jié)點(diǎn)id賦值給map進(jìn)程的key，將二元組(lj,j)傳遞給map進(jìn)程的value，其中l(wèi)j表示節(jié)點(diǎn)j的標(biāo)簽值，j表示對(duì)應(yīng)id節(jié)點(diǎn)的鄰居節(jié)點(diǎn)和其標(biāo)簽值。輸出list(l,n)，n是對(duì)應(yīng)標(biāo)簽值l的所有鄰居的數(shù)量。

(3) Reduce進(jìn)程：輸入list(l,n)，得到n值最大對(duì)應(yīng)的label，根據(jù)(1)中節(jié)點(diǎn)聚集系數(shù)Ci，由式(2)更新每個(gè)頂點(diǎn)i的label，并賦給節(jié)點(diǎn)i：

(2)

其中，δ是克羅內(nèi)克符號(hào)，滿足：

(4) 上一步Reduce輸出的結(jié)果作為下一個(gè)Map的輸入。重復(fù)步驟(2)-(3)，直到所有的節(jié)點(diǎn)不再發(fā)生變化為止。

DisLPA算法的偽代碼如下：

Input:G(V,E),p=1,Ci=1,li=i;

If all vertex not change do

{ p=p+1;

Map(key1,value1)

{

key1←all vertex id;

value1←(lj,j);

//j∈Ni(j),l∈L;

for(each nerghborID in N of i)do

(lj,1);

key2←lj;

value2←Cj·l;

Output(key2,value2);

}

Reduce(key2,value2)

{

key3←nerghborID m of vertex I;

value3←(lm,m);

Output(key3,value3);

}

else

end

}

該算法不僅改進(jìn)了傳統(tǒng)LPA算法不穩(wěn)定的特點(diǎn)，同時(shí)極大地提高了算法執(zhí)行的效率。

3 實(shí)驗(yàn)及分析

該實(shí)驗(yàn)分別選取基準(zhǔn)數(shù)據(jù)和實(shí)際數(shù)據(jù)進(jìn)行對(duì)比分析。基準(zhǔn)數(shù)據(jù)采用單機(jī)模式進(jìn)行實(shí)驗(yàn)分析算法的準(zhǔn)確性，實(shí)際數(shù)據(jù)采用集群模式分析算法的高效性。

3.1 實(shí)驗(yàn)環(huán)境

在Linux下建立Hadoop集群環(huán)境，該集群中配備了4個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的處理器為Alienware Auroa ALX(ALWAD-02)、6 GB、硬盤1500 GB。其中1個(gè)節(jié)點(diǎn)作為Namenode和Jobtracker，其余3個(gè)節(jié)點(diǎn)負(fù)責(zé)具體的計(jì)算任務(wù)。

3.2 基準(zhǔn)網(wǎng)絡(luò)

實(shí)驗(yàn)選取兩個(gè)經(jīng)典的基準(zhǔn)數(shù)據(jù)，分別為Zachary’s karate club數(shù)據(jù)集[19]和Dolphin社會(huì)關(guān)系網(wǎng)[20]，使用基于節(jié)點(diǎn)聚集系數(shù)的LPA算法(CLPA)來(lái)分析。

對(duì)比表1結(jié)果可以看出，CLPA準(zhǔn)確率高于LPA，證明了其可行性。

表1 LPA和CLPA準(zhǔn)確率對(duì)比

3.3 實(shí)際網(wǎng)絡(luò)

本文通過(guò)調(diào)用新浪微博官方的API來(lái)獲取微博數(shù)據(jù)，用來(lái)比較DisPLA算法和單機(jī)分析的CLPA算法以及傳統(tǒng)LPA算法的性能。

社區(qū)質(zhì)量的評(píng)價(jià)采用量化指標(biāo)模塊化度量，是由Newman和Girvan提出[21]的，至今為止比較權(quán)威的衡量指標(biāo)。定義為：

其中，M為網(wǎng)絡(luò)社區(qū)數(shù)目；表示邊兩端都在社區(qū)s中的邊數(shù)；Os表示邊一端在社區(qū)s中的邊數(shù)；E表示網(wǎng)絡(luò)中邊總數(shù)。

算法由于牽涉到多次迭代，在處理小規(guī)模數(shù)據(jù)的時(shí)候，其運(yùn)行時(shí)間是可以接受的，但是面對(duì)較大規(guī)模的數(shù)據(jù)，算法的處理能力明顯下降，幸運(yùn)地是，算法的并行化版本減緩了這一下降趨勢(shì)，使得算法能夠在有限的時(shí)間內(nèi)處理大規(guī)模數(shù)據(jù)。

LPA，CLPA，DisLPA算法模塊度和運(yùn)行時(shí)間對(duì)比結(jié)果如表2所示。

表2 微博數(shù)據(jù)實(shí)驗(yàn)結(jié)果

從表1、表2和圖4的對(duì)比結(jié)果可以看出，與傳統(tǒng)的LPA算法相比，CLPA算法能夠較準(zhǔn)確地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，同時(shí)，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加，CLPA算法的擴(kuò)展——DisLPA算法減少了時(shí)間上的開(kāi)銷，提高了發(fā)現(xiàn)社區(qū)的效率。

圖4 執(zhí)行時(shí)間隨節(jié)點(diǎn)數(shù)的變化情況

4 結(jié) 語(yǔ)

本文在節(jié)點(diǎn)聚集系數(shù)的概念基礎(chǔ)上，提出了一種改進(jìn)的標(biāo)簽傳播算法CLPA，同時(shí)對(duì)CLPA算法并行化處理得到了DisLPA算法，并在Hadoop集群中運(yùn)行，實(shí)驗(yàn)結(jié)果證明了，CLPA算法不僅繼承了LPA算法優(yōu)點(diǎn)，而且提高了LPA算法的精度，但時(shí)間消耗上略大于傳統(tǒng)LPA算法。而DisLPA算法不僅提高了準(zhǔn)確率，同時(shí)有效地減少了運(yùn)行時(shí)間，提高了效率。

但是我們提出的CLPA和DisLPA算法未考慮社區(qū)重疊的問(wèn)題，在未來(lái)的研究中將考慮社區(qū)的重疊性，并對(duì)現(xiàn)有算法進(jìn)行相應(yīng)的改進(jìn)和應(yīng)用。

[1] 覃雄派,王會(huì)舉,杜小勇,等. 大數(shù)據(jù)分析——RDBMS與MapReduce的競(jìng)爭(zhēng)與共生[J]. 軟件學(xué)報(bào),2012,23(1):32-45.

[2] Watts D J,Strogatz S H. Collective dynamics of ‘small-world’networks[J]. nature,1998,393(6684):440-442.

[3] Adamic L A,Huberman B A. Power-law distribution of the world wide web[J]. Science,2000,287(5461):2115-2115.

[4] Girvan M,Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.

[5] 劉大有,金弟,何東曉,等. 復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘綜述[J]. 計(jì)算機(jī)研究與發(fā)展,2013,50(10):2140-2154.

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

[7] 陶劍文,FLC,王士同,等. 稀疏近似最近特征空間嵌入標(biāo)簽傳播[J]. 軟件學(xué)報(bào),2014,25(6):1239-1254.

[8] 王庚,宋傳超,盛玉曉,等. 基于標(biāo)簽傳播的穩(wěn)定重疊社區(qū)挖掘算法研究[J]. 山東科學(xué),2013,26(5):61-68.

[9] 趙雅端，盧罡,趙瑩，等. 基于GPU的復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘算法并行計(jì)算[J]. 計(jì)算機(jī)應(yīng)用研究,2013,30(8):2426-2428.

[10] 宋鈺,何小利. 一種基于日志聚類郵件網(wǎng)絡(luò)社區(qū)劃分挖掘算法[J]. 科技通報(bào),2014,30(2):96-98.

[11] Zhu X,Ghahramani Z. Learning from labeled and unlabeled data with label propagation[R]. Technical Report CMU-CALD-02-107,Carnegie Mellon University，2002.

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

[13] Barber M J,Clark J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E,2009,80(2):026129.

[14] Liu X,Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A: Statistical Mechanics and its Applications,2010,389(7):1493-1500.

[15] Dean J,Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM,2008,51(1):107-113.

[16] 楊文志. 云計(jì)算技術(shù)指南: 應(yīng)用,平臺(tái)與架構(gòu)[M]. 北京: 化學(xué)工業(yè)出版社，2010.

[17] 劉鵬. 云計(jì)算[M].2版. 北京:電子工業(yè)出版社，2011.

[18] 曾大聃,周傲英. Hadoop 權(quán)威指南中文版[M]. 北京: 清華大學(xué)出版社，2010.

[19] Zachary W. An Information Flow Modelfor Conflict and Fission in Small Groups1[J]. Journal of anthropological research,1977,33(4):452-473.

[20] Lusseau D,Schneider K,Boisseau O J,et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology,2003,54(4):396-405.

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

DISTRIBUTED LABEL PROPAGATION ALGORITHM BASED ON NODES CLUSTERING COEFFICIENT

Zhang Suzhi Sun Jiabin Wang Wei

(SchoolofComputerandCommunicationEngineering,ZhengzhouUniversityofLightMdustry,Zhengzhou450002,Henan,China)

Along with the development and popularity of Internet,more and more users join in social networks,and this gradually forms the large-scale and diverse communities. For social networking services such as Sina microblogging,the detection of these communicates can offer valuable information to users and merchants. Among numerous community detection algorithms,the label propagation algorithm (LPA) has the advantages of simple algorithm idea,low complexity,and no need in initialising the numbers of community,etc. However,its accuracy is rather lower,and meanwhile its efficiency is not high enough in the environment of big data. We proposed a community detection algorithm,which combines MapReduce distributed computation framework,by introducing nodes clustering coefficient into the process of LPA label update,we call it DisLPA. Experiment showed that the algorithm not only improved the accuracy,but also effectively solved the bottleneck problem of calculation.

Community detection Label propagation Clustering coefficient MapReduce

2014-09-10。國(guó)家自然科學(xué)基金項(xiàng)目(61201447)。張素智，教授，主研領(lǐng)域：Web數(shù)據(jù)庫(kù)，分布式計(jì)算和異構(gòu)系統(tǒng)集成。孫嘉彬，碩士生。王威，碩士生。

TP301.6

A

10.3969/j.issn.1000-386x.2016.04.030