王李冬,張　赟

(1. 杭州師范大學(xué)錢江學(xué)院, 浙江 杭州 310036；2. 浙江傳媒學(xué)院,浙江 杭州 310018)

大規(guī)模社交網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)技術(shù)綜述

王李冬1,張赟2

(1. 杭州師范大學(xué)錢江學(xué)院, 浙江 杭州 310036；2. 浙江傳媒學(xué)院,浙江 杭州 310018)

摘要：隨著社交網(wǎng)站的發(fā)展,大規(guī)模、結(jié)構(gòu)復(fù)雜的社交網(wǎng)絡(luò)應(yīng)運(yùn)而生,發(fā)現(xiàn)大規(guī)模社交網(wǎng)絡(luò)的潛在結(jié)構(gòu)是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的研究難點(diǎn).針對(duì)近幾年出現(xiàn)的4種重疊式社區(qū)挖掘算法(SLPA,TopGC,SVINET,UEOC),詳細(xì)分析各方法的設(shè)計(jì)原理,概括出各算法的特點(diǎn)和應(yīng)用范疇.并將各算法應(yīng)用于具備先驗(yàn)社區(qū)知識(shí)的多種大規(guī)模社交網(wǎng)絡(luò),通過(guò)多種性能評(píng)價(jià)指標(biāo)進(jìn)行定量對(duì)比分析.結(jié)果表明,SLPA和TopGC分別在性能和效率上取得最優(yōu),但所有算法無(wú)法同時(shí)在效率和性能上取得理想效果.

關(guān)鍵詞：社交網(wǎng)絡(luò)；重疊社區(qū)挖掘；SLPA；TopGC

0概述

隨著當(dāng)前互聯(lián)網(wǎng)載體下人類互動(dòng)和溝通需求的擴(kuò)展,社交網(wǎng)絡(luò)已經(jīng)逐漸影響人們的生活.社交網(wǎng)絡(luò)的基本載體為用戶,如何對(duì)這些大規(guī)模用戶數(shù)據(jù)進(jìn)行分析并發(fā)現(xiàn)一些動(dòng)向,從而作為營(yíng)銷時(shí)代價(jià)值創(chuàng)造的前提分析工具,是當(dāng)前研究的熱點(diǎn)之一.網(wǎng)絡(luò)社區(qū)挖掘方法為解決此問(wèn)題提供了一些策略.

社交網(wǎng)絡(luò)具備六度分割理論,屬于“小世界”網(wǎng)絡(luò).借助復(fù)雜網(wǎng)絡(luò)原理,對(duì)社交網(wǎng)絡(luò)的社區(qū)分析一般借助于當(dāng)前復(fù)雜網(wǎng)絡(luò)的社區(qū)挖掘方法,如基于最優(yōu)化的方法、基于啟發(fā)式規(guī)則方法等.傳統(tǒng)社區(qū)挖掘算法將網(wǎng)絡(luò)劃分為若干個(gè)互不連接的簇,每個(gè)節(jié)點(diǎn)都隸屬于唯一的社區(qū).目前多數(shù)現(xiàn)實(shí)世界網(wǎng)絡(luò)都具備重疊社區(qū),同時(shí)包含權(quán)重邊.也就是說(shuō),在社交網(wǎng)絡(luò)中,每個(gè)用戶往往會(huì)依據(jù)不同的劃分規(guī)則隸屬于不同的社區(qū),如學(xué)校、家人以及朋友等.可見(jiàn),挖掘社交網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)更具有現(xiàn)實(shí)意義.當(dāng)前重疊社區(qū)挖掘已經(jīng)具備一定的研究基礎(chǔ),但在實(shí)際應(yīng)用中社交網(wǎng)絡(luò)一般包含上千至上百萬(wàn)用戶節(jié)點(diǎn),網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜,使得大規(guī)模社交網(wǎng)絡(luò)的社區(qū)挖掘變成一個(gè)難題,普通的社區(qū)挖掘算法無(wú)法取得滿意的效果.此外,很多研究者認(rèn)為社區(qū)代表緊密連接的節(jié)點(diǎn)群,而且群與群之間屬于稀疏連接,目前存在多種社區(qū)定義都符合該特性,但一直缺乏能被研究者廣泛接受的正式定義[1],這一點(diǎn)更是加大了社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的難度.現(xiàn)有研究不能滿足大規(guī)模網(wǎng)絡(luò)潛在模式發(fā)現(xiàn)的需求,還需要研究者借鑒已有的技術(shù)和模型,為大規(guī)模社交網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)發(fā)現(xiàn)問(wèn)題設(shè)計(jì)更好的模型和算法.

本文對(duì)當(dāng)前最新的重疊社區(qū)挖掘主流算法進(jìn)行了梳理,詳細(xì)分析這些主流算法的設(shè)計(jì)動(dòng)機(jī)和原理,并利用已經(jīng)具備先驗(yàn)社區(qū)結(jié)構(gòu)的社交網(wǎng)絡(luò)數(shù)據(jù)集,針對(duì)不同方法的特點(diǎn)和性能進(jìn)行定性和定量的對(duì)比分析,為該領(lǐng)域的研究者利用和改進(jìn)這些技術(shù)提供幫助.

1相關(guān)工作

近幾年已有相關(guān)學(xué)者針對(duì)社區(qū)挖掘算法進(jìn)行綜述性研究,但主要針對(duì)獨(dú)立社區(qū)挖掘.Fortunato[1]和Coscia等[2]針對(duì)獨(dú)立和重疊社區(qū)挖掘算法作出了詳盡的對(duì)比.Fortunato根據(jù)方法的原理進(jìn)行分類描述,Coscia等則根據(jù)社區(qū)的不同定義進(jìn)行分類描述.Malliaros等[3]針對(duì)有向網(wǎng)絡(luò)圖將方法進(jìn)行歸類,并提出基于方法學(xué)(methodology-based)的社區(qū)挖掘算法分類系統(tǒng).除了理論方面的整理與分析,也有部分研究者將多種社區(qū)挖掘算法進(jìn)行性能評(píng)價(jià).Orman等[4]將8種非重疊社區(qū)挖掘算法應(yīng)用于多種合成網(wǎng)絡(luò)圖,并將取得的實(shí)驗(yàn)結(jié)果和識(shí)別的社區(qū)結(jié)構(gòu)特性進(jìn)行整理與分析.柴變芳等[5]對(duì)基于概率模型的大規(guī)模網(wǎng)絡(luò)社區(qū)挖掘算法按照模型參數(shù)求解策略進(jìn)行歸類,并應(yīng)用于多種社交網(wǎng)絡(luò),最后利用實(shí)驗(yàn)結(jié)果對(duì)各種方法進(jìn)行定量的對(duì)比和分析.Xie等[6]提煉出14種重疊社區(qū)挖掘算法,并將算法分成5類,分別為團(tuán)過(guò)濾方法(Clique Percolation Method),邊分割(Line Partitioning),基于代理和動(dòng)態(tài)算法(Agent-based and Dynamic Algorithms)[7],局部擴(kuò)展與優(yōu)化(Local Expansion and Optimization)[8]以及模糊檢測(cè)(Fuzzy Detection)[9],最終面向人工合成網(wǎng)絡(luò)以及真實(shí)社交網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)分析.

可見(jiàn),現(xiàn)有的重疊社區(qū)挖掘算法主要面向人工合成網(wǎng)絡(luò)以及部分社交網(wǎng)絡(luò)進(jìn)行設(shè)計(jì)與實(shí)驗(yàn),而這些社交網(wǎng)絡(luò)都不具備先驗(yàn)社區(qū)知識(shí),無(wú)法驗(yàn)證這些算法的真正性能.本文針對(duì)多種最新重疊社區(qū)挖掘算法(發(fā)表于2010年后)進(jìn)行詳細(xì)的算法原理分析并面向多種大規(guī)模社交網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn).與其它綜述性研究不同的是,本文涉及的大規(guī)模社交網(wǎng)絡(luò)具備先驗(yàn)社區(qū)知識(shí),而且部分算法間的比較分析并未出現(xiàn)在其它綜述文獻(xiàn)中.

2算法概述

團(tuán)過(guò)濾算法(Clique Percolation Method, CPM)作為經(jīng)典的重疊社區(qū)挖掘算法之一,通過(guò)找到網(wǎng)絡(luò)中的最大團(tuán),并利用共享節(jié)點(diǎn)將團(tuán)進(jìn)行合并,最壞情況需要指數(shù)級(jí)運(yùn)行時(shí)間.本文利用CPM算法中的CFinder作為基準(zhǔn)算法,與SLPA,TopGC,SVINET,UEOC等方法進(jìn)行比較分析.

2.1SLPA

SLPA(Speaker-listener Label Propagation Algorithm)[10]作為標(biāo)簽傳播算法(Label Propagation Algorithm, LPA)的擴(kuò)展,主要應(yīng)用于重疊型社區(qū)挖掘,通過(guò)傳播代表社區(qū)類別歸屬的標(biāo)簽以達(dá)到社區(qū)發(fā)現(xiàn)的目的.首先,為所有節(jié)點(diǎn)指定一個(gè)唯一的標(biāo)簽,即在初始化狀態(tài),所有節(jié)點(diǎn)屬于不同的社區(qū).然后,選擇一個(gè)節(jié)點(diǎn)作為listener,標(biāo)簽從listener傳播到周圍的speaker(鄰居節(jié)點(diǎn)).LPA和SLPA算法的最大區(qū)別在于標(biāo)簽的更新方式不同.在LPA中,對(duì)當(dāng)前節(jié)點(diǎn)以出現(xiàn)次數(shù)最多的標(biāo)簽進(jìn)行更新.在SLPA中,記錄每一個(gè)節(jié)點(diǎn)在每次迭代過(guò)程中的歷史標(biāo)簽序列(例如迭代T次,則每個(gè)節(jié)點(diǎn)將保存一個(gè)長(zhǎng)度為T的序列).當(dāng)?shù)Ｖ购?對(duì)每一個(gè)節(jié)點(diǎn)歷史標(biāo)簽序列中各(互異)標(biāo)簽出現(xiàn)的頻率進(jìn)行統(tǒng)計(jì),按照某一給定的閥值r∈[0,1]過(guò)濾掉那些出現(xiàn)頻率小的標(biāo)簽,剩下的即為該節(jié)點(diǎn)的標(biāo)簽.文獻(xiàn)[7]證實(shí)當(dāng)T>20時(shí),最后的結(jié)果將趨于穩(wěn)定.最終,具備相同標(biāo)簽的節(jié)點(diǎn)被劃分為同個(gè)社區(qū).如果一個(gè)節(jié)點(diǎn)具備多個(gè)標(biāo)簽,那么該節(jié)點(diǎn)隸屬于多個(gè)社區(qū).可見(jiàn),閾值r越小,最終被發(fā)現(xiàn)的重疊社區(qū)個(gè)數(shù)越多.若r≥0.5,那么該算法就回歸為非重疊社區(qū)挖掘.

2.2TopGC

TopGC (Top Graph Clusters)算法[11]屬于基于概率聚類的社區(qū)挖掘算法，其主要思想是找到鄰居節(jié)點(diǎn)中高度重疊的節(jié)點(diǎn)集合,并將這些節(jié)點(diǎn)組成社區(qū)結(jié)構(gòu).該算法通過(guò)MinHash技術(shù)實(shí)現(xiàn).MinHash技術(shù)主要用于快速估算兩個(gè)集合的相似度,也可應(yīng)用于大規(guī)模聚類.為了簡(jiǎn)化計(jì)算,最初需要剪枝階段(pruning phase)用于判定哪些節(jié)點(diǎn)屬于最強(qiáng)蔟(社區(qū)).該算法中蔟的強(qiáng)度定義為

(1)

其中,wij表示節(jié)點(diǎn)vi和vj之間邊的權(quán)重,|C|表示蔟C的節(jié)點(diǎn)個(gè)數(shù).

首先,該算法為網(wǎng)絡(luò)中的所有節(jié)點(diǎn)選取m種排列,記為π1,…,πm；其次,為每個(gè)節(jié)點(diǎn)生成Minhash值,記為mh1,…,mhm,其中mhi代表其鄰居節(jié)點(diǎn)集合Nj中在πi排序末尾的節(jié)點(diǎn)；再次,產(chǎn)生l個(gè)隨機(jī)數(shù),l∈[1,…，m],每個(gè)節(jié)點(diǎn)的Minhash簽名由一系列mhl1,…,mhll構(gòu)成；最后計(jì)算兩個(gè)節(jié)點(diǎn)具備相同Minhash的概率,記為(|Ni∩Nj|/|Ni∪Nj|)l,具備相同Minhash的節(jié)點(diǎn)被認(rèn)定為同個(gè)社區(qū).

2.3SVINET

SVINET[12]利用混合隸屬度隨機(jī)塊模型(Mixed-membership Stochastic Block Model,MMSB)進(jìn)行重疊社區(qū)挖掘,屬于概率模型方法.MMSB為SBM(Stochastic Block Model)模型[13]的變型.SBM模型是由社會(huì)科學(xué)家提出的一種可更好擬合實(shí)際網(wǎng)絡(luò)的隨機(jī)圖模型,能識(shí)別體現(xiàn)網(wǎng)絡(luò)中觀結(jié)構(gòu)的類間鏈接模式,且一個(gè)節(jié)點(diǎn)可存在于多個(gè)社區(qū).

在MMSB模型中,每個(gè)節(jié)點(diǎn)被分配長(zhǎng)度為K的社區(qū)成員向量θ,K代表網(wǎng)絡(luò)中的社區(qū)個(gè)數(shù).給定一個(gè)可觀察網(wǎng)絡(luò),該網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)可以通過(guò)計(jì)算后驗(yàn)概率進(jìn)行估計(jì),即p(θ,z|y),z表示社區(qū)標(biāo)識(shí)向量,y表示可觀察網(wǎng)絡(luò).由于該后驗(yàn)概率無(wú)法直接計(jì)算,用mean-field變分簇q(θ,z)近似后驗(yàn)分布,并采用隨機(jī)變分進(jìn)行參數(shù)估計(jì),具體過(guò)程如下:

1)從節(jié)點(diǎn)對(duì)集合中抽樣邊集合S；

2)根據(jù)每對(duì)節(jié)點(diǎn)(i,j)∈S,計(jì)算S中每對(duì)節(jié)點(diǎn)的最優(yōu)局部變分參數(shù)φi→j和φj→i；φi→j和φj→i為z變分參數(shù).

3)根據(jù)局部變分參數(shù)更新γ.γ為θ變分參數(shù),描述每個(gè)節(jié)點(diǎn)的社區(qū)成員向量θ的后驗(yàn)分布.

2.4UEOC

UEOC算法[7]分成UC(Unfolding Community)和EC(Extracting Community)兩個(gè)階段.在UC階段,利用隨機(jī)游走原理,首先選取目的節(jié)點(diǎn),并針對(duì)每個(gè)節(jié)點(diǎn)計(jì)算初始節(jié)點(diǎn)到目的節(jié)點(diǎn)的l-step轉(zhuǎn)移概率值.假設(shè)T代表轉(zhuǎn)移矩陣,Ti→j代表從結(jié)點(diǎn)i出發(fā)游走到鄰居節(jié)點(diǎn)j的概率值,則l-step概率值按照下式進(jìn)行迭代計(jì)算:

(2)

然后,針對(duì)每個(gè)節(jié)點(diǎn)到目的結(jié)點(diǎn)的轉(zhuǎn)移概率值從大到小進(jìn)行排序,得到排序好的節(jié)點(diǎn)序列.

在EC階段,根據(jù)UC階段獲得的排序好的節(jié)點(diǎn)序列L,為該序列設(shè)置特定的切割位置(cut position)就可獲得社區(qū)結(jié)構(gòu).切割位置需要根據(jù)電導(dǎo)值計(jì)算獲取,某一社區(qū)結(jié)構(gòu)的電導(dǎo)值表示為社區(qū)內(nèi)節(jié)點(diǎn)的度的總和與該社區(qū)的外連接邊的個(gè)數(shù)的比值.首先,針對(duì)節(jié)點(diǎn)序列中的每個(gè)節(jié)點(diǎn)計(jì)算電導(dǎo)值,而切割點(diǎn)則對(duì)應(yīng)于最小電導(dǎo)值.然后,將切割點(diǎn)之前的所有節(jié)點(diǎn)序列構(gòu)成一個(gè)社區(qū).如此反復(fù),直到序列L中的所有節(jié)點(diǎn)都已經(jīng)劃分到特定社區(qū)中.

為了給上述算法作定性比較和分析,本文梳理了各算法的設(shè)計(jì)原理、復(fù)雜度以及應(yīng)用范疇等記錄于表1中.其中,SLPA,TopGC以及UEOC算法可以同時(shí)用于重疊社區(qū)挖掘和非重疊社區(qū)挖掘.

表1　重疊社區(qū)挖掘算法

3實(shí)驗(yàn)比較與分析

3.1實(shí)驗(yàn)數(shù)據(jù)集

本文采用SNAP(http://snap.stanford.edu/data)提供的已知先驗(yàn)社區(qū)結(jié)構(gòu)的大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).

Facebook:節(jié)點(diǎn)代表用戶,節(jié)點(diǎn)之間的邊表示兩個(gè)用戶具備相互關(guān)注的關(guān)系.社區(qū)結(jié)構(gòu)定義為用戶的社交圈(Social Circles).

LiveJournal, Orkut, Youtube:節(jié)點(diǎn)代表用戶,邊代表用戶之間的好友關(guān)系.社區(qū)結(jié)構(gòu)通過(guò)用戶創(chuàng)建的組進(jìn)行定義.

真實(shí)社交網(wǎng)絡(luò)往往不具備好的社區(qū)結(jié)構(gòu)(除了Facebook網(wǎng)絡(luò)外),因此需要對(duì)上述網(wǎng)絡(luò)進(jìn)行預(yù)處理.好的社區(qū)結(jié)構(gòu)具備較高的內(nèi)部稠密度(internal density),本文根據(jù)該值選取前5 000個(gè)社區(qū)進(jìn)行實(shí)驗(yàn),移除其余社區(qū)中的節(jié)點(diǎn),同時(shí)移除不屬于任何社區(qū)結(jié)構(gòu)的節(jié)點(diǎn).最終的實(shí)驗(yàn)數(shù)據(jù)中,Facebook網(wǎng)絡(luò)包含4 039個(gè)節(jié)點(diǎn),88 234條邊；Youtube網(wǎng)絡(luò)包含12 091個(gè)節(jié)點(diǎn),29 775條邊；LiveJournal網(wǎng)絡(luò)包含44 093個(gè)節(jié)點(diǎn),871 409條邊；Orkut包含297 691個(gè)節(jié)點(diǎn),7 747 026條邊.

3.2實(shí)驗(yàn)結(jié)果與討論

下面將上述算法應(yīng)用到真實(shí)社交網(wǎng)絡(luò)上驗(yàn)證其性能與運(yùn)行效率.實(shí)驗(yàn)環(huán)境為:處理器 Intel i5-4430 3.0 GHz,內(nèi)存16 G,操作系統(tǒng)為L(zhǎng)inux.

圖1　重疊社區(qū)挖掘算法性能比較Fig. 1　Performance metrics for overlapping community detection

圖1給出了各算法在不同數(shù)據(jù)集上的運(yùn)行效果,利用Recall、Precision、F-measure和NMI 4種性能指標(biāo)進(jìn)行衡量,每種算法在各數(shù)據(jù)集上運(yùn)行5次.需要注意的是,如果部分算法在特定數(shù)據(jù)集上無(wú)法于規(guī)定時(shí)間內(nèi)(4 h)完成,則程序終止,實(shí)驗(yàn)結(jié)果不作記錄.從圖中數(shù)據(jù)可得,TopGC相比其它算法在Recall、F-measure和 NMI上都處于劣勢(shì).根據(jù)TopGC算法中的評(píng)分(scoring)函數(shù),該算法僅識(shí)別Top社區(qū),造成很多節(jié)點(diǎn)并不處于任何社區(qū)結(jié)構(gòu)中,使得識(shí)別結(jié)果中存在很多的假陰性(false negative),導(dǎo)致最終獲得較低的Recall值和F-measure值.相比各算法,SLPA獲得的結(jié)果最好,這與文獻(xiàn)[4]中的效果相符合.

為了進(jìn)一步比較各算法的社區(qū)挖掘效果,將每個(gè)算法發(fā)現(xiàn)的社區(qū)和先驗(yàn)社區(qū)結(jié)構(gòu)進(jìn)行相似度計(jì)算.假定兩個(gè)算法A和B,則這兩種算法的社區(qū)挖掘結(jié)果的相似度計(jì)算如下[3]:

(3)

上式中,SA(c)代表算法A的挖掘結(jié)果中屬于社區(qū)c的節(jié)點(diǎn)集合.表2給出了相似度比較的實(shí)驗(yàn)結(jié)果.由表中數(shù)據(jù)可得,大多數(shù)算法面向Youtube網(wǎng)絡(luò)的挖掘結(jié)果都與先驗(yàn)社區(qū)結(jié)構(gòu)相差較大,說(shuō)明該網(wǎng)絡(luò)本身不具備很好的社區(qū)結(jié)構(gòu).TopGC針對(duì)多數(shù)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)結(jié)果與其相應(yīng)的先驗(yàn)社區(qū)結(jié)構(gòu)差別較大,可見(jiàn)該算法的挖掘效果并不理想.這主要是由于TopGC算法的出發(fā)點(diǎn)是發(fā)現(xiàn)具備緊密連接的社區(qū),使得最終發(fā)現(xiàn)的社區(qū)數(shù)目往往小于真實(shí)社區(qū)數(shù)目.

表2　各算法社區(qū)發(fā)現(xiàn)結(jié)果與先驗(yàn)社區(qū)結(jié)構(gòu)的相似度

此外,本文測(cè)試了上述算法在大規(guī)模社交網(wǎng)絡(luò)上的運(yùn)行效率.鑒于Facebook網(wǎng)絡(luò)規(guī)模較小,在時(shí)間運(yùn)算中不作為實(shí)驗(yàn)數(shù)據(jù).本文用這些算法本身提供的源碼進(jìn)行計(jì)算,不考慮編譯環(huán)境對(duì)最終運(yùn)行結(jié)果造成的影響.將每種算法運(yùn)行5次,最后將均值記錄于表3中.由表3數(shù)據(jù)可得,TopGC的運(yùn)行速度最快,CFinder和SVINET算法在LiveJournal和Orkut數(shù)據(jù)集上無(wú)法于4 h內(nèi)完成.可見(jiàn),CFinder和SVINET并不適合大規(guī)模尺度的社交網(wǎng)絡(luò)社區(qū)挖掘.SLPA雖然能取得較好的性能(表2),但面對(duì)規(guī)模較大的社交網(wǎng)絡(luò)需要花費(fèi)較長(zhǎng)的時(shí)間.

表3　各算法運(yùn)行時(shí)間比較

4總結(jié)與討論

當(dāng)前社交網(wǎng)絡(luò)發(fā)展迅速,對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行社區(qū)挖掘可為多領(lǐng)域帶來(lái)較高的經(jīng)濟(jì)效益.本文對(duì)近幾年出現(xiàn)的大規(guī)模重疊社區(qū)挖掘算法(SLPA,TopGC,SVINET,UEOC)從理論上進(jìn)行分析,并應(yīng)用于多種具備先驗(yàn)社區(qū)結(jié)構(gòu)的社交網(wǎng)絡(luò)(Facebook,Youtube,LiveJournal,Orkut).實(shí)驗(yàn)結(jié)果表明:SLPA算法具備較好的挖掘性能,TopGC算法效率最優(yōu).針對(duì)大規(guī)模社交網(wǎng)絡(luò),目前缺乏能同時(shí)在算法性能和算法效率上都較為理想的重疊社區(qū)發(fā)現(xiàn)算法.未來(lái)可以著重在以下幾方面展開(kāi)研究:

1)針對(duì)性能較優(yōu)的算法,融合大數(shù)據(jù)處理技術(shù)提高方法的運(yùn)行效率，如基于云計(jì)算平臺(tái)的算法改進(jìn)等；

2)社交網(wǎng)絡(luò)往往缺乏先驗(yàn)社區(qū)知識(shí),未來(lái)的算法應(yīng)著重面向社區(qū)個(gè)數(shù)未知的網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)任務(wù)；

3)將網(wǎng)絡(luò)的鏈接信息融合進(jìn)社區(qū)挖掘算法中；

4)現(xiàn)有的大規(guī)模社交網(wǎng)絡(luò)挖掘方法研究還停留在初步階段,如何將這些方法和社交媒體的服務(wù)相結(jié)合,利用用戶的反饋進(jìn)行模型優(yōu)劣的評(píng)價(jià),是亟待解決的問(wèn)題.

參考文獻(xiàn):

[1] FORTUNATO S. Community detection in graphs[J]. Physics Reports,2010,486(3/4/5):75-174.

[2] COSCIA M, GIANNOTTI F, PEDRESCHI D. A classification for community discovery methods in complex networks[J]. Statistical Analysis and Data Mining,2011,4(5):512-546.

[3] MALLIAROS F D, VAZIRGIANNIS M. Clustering and community detection in directed networks: a survey[J]. Physics Reports,2013,533(4):95-142.

[4] ORMAN G K, LABATUT V, CHERIFI H. Comparative evaluation of community detection algorithms: a topological approach[J]. J Stat Mech Theor Exp,2012,2012(8):P08001.

[5] 柴變芳,賈彩燕,于劍.基于概率模型的大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)方法[J].軟件學(xué)報(bào),2014,25(12):2753-2766.

[6] XIE J R, KELLEY S, SZYMANSKI B K. Overlapping community detection in networks: the state-of-the-art and comparative study[J]. ACM Computing Surveys,2013,45(4):43.

[7] JIN D, YANG B, BAQUERO C, et al. A markov random walk under constraint for discovering overlapping communities in complex networks[J]. J Stat Mech Thero Exp,2011,2011(5):P05031.

[8] HAVEMANN F, HEINZ M, STRUCK A, et al. Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels[J]. J Stat Mech Theor Exp,2011,2011(1):P01023.

[9] LATOUCHE P, BIRMELE E, AMBROISE C. Overlapping stochastic block models with application to the french political blogosphere[J]. The Annals of Applied Statistics,2011,5(1):309-336.

[10] XIE J, SZYMANSKI B K. Towards linear time overlapping community detection in social networks[M]//TAN P N, CHAWLA S, HO C K,et al. Advances in Knowledge Discovery and Data Mining. Berlin:Springer,2012:25-36.

[11] MACROPOL K, SINGH A. Scalable discovery of best clusters on large graphs[J]. Proceedings of the VLDB Endowment,2010,3(1/2):693-702.

[12] GOPALAN P K, BLEI D M. Efficient discovery of overlapping communities in massive networks[J]. Proc Nati Acad Sci,2013,110(36):14534-14539.

[13] CHAI B F, YU J, JIA C Y, et al. Combining a popularity-productivity stochastic block model with a discriminative-content model for general structure detection[J]. Physical Review E. Statistical, Nonlinear, and Soft Matter Physics,2013,88(1):012807.

Overlapping Community Detection in Large-scale Social Networks

WANG Lidong1, ZHANG Yun2

(1. Qianjiang College, Hangzhou Normal University, Hangzhou 310036, China； 2. Zhejiang University of Media and Communications,Hangzhou 310018, China)

Abstract:The growth of the online social websites brings up the development of massive social networks with the characteristics of large-scale and complex structure. Identifying the latent structure in large-scale networks is a difficult task in data detection domain. This review analyzes the design principles of four algorithms (SLPA, TopGC, SVINET, UEOC) that are recently published, and summarized their characteristics and fields of application. Finally, these methods are evaluated on large-scale social networks with known ground-truth communities. The results show that SLPA and TopGC obtain the best results on effectiveness and efficiency respectively, but all methods cannot achieve ideal results on both effectiveness and efficiency.

Key words:social network； overlapping community detection； SLPA； TopGC

收稿日期：2015-10-27

基金項(xiàng)目：浙江省自然科學(xué)基金項(xiàng)目(LQ14F020008,LY14F020050).

通信作者：王李冬(1982—),女,副教授,博士，主要從事數(shù)據(jù)挖掘、信息檢索研究.E-mail:violet_wld@163.com

doi:10.3969/j.issn.1674-232X.2016.03.020

中圖分類號(hào):TP391

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1674-232X(2016)03-0331-06