大規模社交網絡重疊社區發現技術綜述

王李冬,張　赟

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

大規模社交網絡重疊社區發現技術綜述

王李冬1,張赟2

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

摘要：隨著社交網站的發展,大規模、結構復雜的社交網絡應運而生,發現大規模社交網絡的潛在結構是當前數據挖掘領域的研究難點.針對近幾年出現的4種重疊式社區挖掘算法(SLPA,TopGC,SVINET,UEOC),詳細分析各方法的設計原理,概括出各算法的特點和應用范疇.并將各算法應用于具備先驗社區知識的多種大規模社交網絡,通過多種性能評價指標進行定量對比分析.結果表明,SLPA和TopGC分別在性能和效率上取得最優,但所有算法無法同時在效率和性能上取得理想效果.

關鍵詞：社交網絡；重疊社區挖掘；SLPA；TopGC

0概述

隨著當前互聯網載體下人類互動和溝通需求的擴展,社交網絡已經逐漸影響人們的生活.社交網絡的基本載體為用戶,如何對這些大規模用戶數據進行分析并發現一些動向,從而作為營銷時代價值創造的前提分析工具,是當前研究的熱點之一.網絡社區挖掘方法為解決此問題提供了一些策略.

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

本文對當前最新的重疊社區挖掘主流算法進行了梳理,詳細分析這些主流算法的設計動機和原理,并利用已經具備先驗社區結構的社交網絡數據集,針對不同方法的特點和性能進行定性和定量的對比分析,為該領域的研究者利用和改進這些技術提供幫助.

1相關工作

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

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

2算法概述

團過濾算法(Clique Percolation Method, CPM)作為經典的重疊社區挖掘算法之一,通過找到網絡中的最大團,并利用共享節點將團進行合并,最壞情況需要指數級運行時間.本文利用CPM算法中的CFinder作為基準算法,與SLPA,TopGC,SVINET,UEOC等方法進行比較分析.

2.1SLPA

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

2.2TopGC

TopGC (Top Graph Clusters)算法[11]屬于基于概率聚類的社區挖掘算法，其主要思想是找到鄰居節點中高度重疊的節點集合,并將這些節點組成社區結構.該算法通過MinHash技術實現.MinHash技術主要用于快速估算兩個集合的相似度,也可應用于大規模聚類.為了簡化計算,最初需要剪枝階段(pruning phase)用于判定哪些節點屬于最強蔟(社區).該算法中蔟的強度定義為

(1)

其中,wij表示節點vi和vj之間邊的權重,|C|表示蔟C的節點個數.

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

2.3SVINET

SVINET[12]利用混合隸屬度隨機塊模型(Mixed-membership Stochastic Block Model,MMSB)進行重疊社區挖掘,屬于概率模型方法.MMSB為SBM(Stochastic Block Model)模型[13]的變型.SBM模型是由社會科學家提出的一種可更好擬合實際網絡的隨機圖模型,能識別體現網絡中觀結構的類間鏈接模式,且一個節點可存在于多個社區.

在MMSB模型中,每個節點被分配長度為K的社區成員向量θ,K代表網絡中的社區個數.給定一個可觀察網絡,該網絡的社區結構可以通過計算后驗概率進行估計,即p(θ,z|y),z表示社區標識向量,y表示可觀察網絡.由于該后驗概率無法直接計算,用mean-field變分簇q(θ,z)近似后驗分布,并采用隨機變分進行參數估計,具體過程如下:

1)從節點對集合中抽樣邊集合S；

2)根據每對節點(i,j)∈S,計算S中每對節點的最優局部變分參數φi→j和φj→i；φi→j和φj→i為z變分參數.

3)根據局部變分參數更新γ.γ為θ變分參數,描述每個節點的社區成員向量θ的后驗分布.

2.4UEOC

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

(2)

然后,針對每個節點到目的結點的轉移概率值從大到小進行排序,得到排序好的節點序列.

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

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

表1　重疊社區挖掘算法

3實驗比較與分析

3.1實驗數據集

本文采用SNAP(http://snap.stanford.edu/data)提供的已知先驗社區結構的大規模社交網絡數據集進行實驗.

Facebook:節點代表用戶,節點之間的邊表示兩個用戶具備相互關注的關系.社區結構定義為用戶的社交圈(Social Circles).

LiveJournal, Orkut, Youtube:節點代表用戶,邊代表用戶之間的好友關系.社區結構通過用戶創建的組進行定義.

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

3.2實驗結果與討論

下面將上述算法應用到真實社交網絡上驗證其性能與運行效率.實驗環境為:處理器 Intel i5-4430 3.0 GHz,內存16 G,操作系統為Linux.

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

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

為了進一步比較各算法的社區挖掘效果,將每個算法發現的社區和先驗社區結構進行相似度計算.假定兩個算法A和B,則這兩種算法的社區挖掘結果的相似度計算如下[3]:

(3)

上式中,SA(c)代表算法A的挖掘結果中屬于社區c的節點集合.表2給出了相似度比較的實驗結果.由表中數據可得,大多數算法面向Youtube網絡的挖掘結果都與先驗社區結構相差較大,說明該網絡本身不具備很好的社區結構.TopGC針對多數網絡的社區發現結果與其相應的先驗社區結構差別較大,可見該算法的挖掘效果并不理想.這主要是由于TopGC算法的出發點是發現具備緊密連接的社區,使得最終發現的社區數目往往小于真實社區數目.

表2　各算法社區發現結果與先驗社區結構的相似度

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

表3　各算法運行時間比較

4總結與討論

當前社交網絡發展迅速,對網絡數據進行社區挖掘可為多領域帶來較高的經濟效益.本文對近幾年出現的大規模重疊社區挖掘算法(SLPA,TopGC,SVINET,UEOC)從理論上進行分析,并應用于多種具備先驗社區結構的社交網絡(Facebook,Youtube,LiveJournal,Orkut).實驗結果表明:SLPA算法具備較好的挖掘性能,TopGC算法效率最優.針對大規模社交網絡,目前缺乏能同時在算法性能和算法效率上都較為理想的重疊社區發現算法.未來可以著重在以下幾方面展開研究:

1)針對性能較優的算法,融合大數據處理技術提高方法的運行效率，如基于云計算平臺的算法改進等；

2)社交網絡往往缺乏先驗社區知識,未來的算法應著重面向社區個數未知的網絡結構發現任務；

3)將網絡的鏈接信息融合進社區挖掘算法中；

4)現有的大規模社交網絡挖掘方法研究還停留在初步階段,如何將這些方法和社交媒體的服務相結合,利用用戶的反饋進行模型優劣的評價,是亟待解決的問題.

參考文獻:

[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] 柴變芳,賈彩燕,于劍.基于概率模型的大規模網絡結構發現方法[J].軟件學報,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

基金項目：浙江省自然科學基金項目(LQ14F020008,LY14F020050).

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

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

中圖分類號:TP391

文獻標志碼:A

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