基于結(jié)構(gòu)相似度的大規(guī)模社交網(wǎng)絡(luò)聚類算法

陳季夢(mèng)陳佳俊劉 杰*黃亞樓王 嫄馮 霞

①(南開大學(xué)計(jì)算機(jī)與控制工程學(xué)院 天津 300071)

②(南開大學(xué)軟件學(xué)院 天津 300071)

③(中國(guó)民航大學(xué)民航信息技術(shù)科研基地 天津 300300)

基于結(jié)構(gòu)相似度的大規(guī)模社交網(wǎng)絡(luò)聚類算法

陳季夢(mèng)①陳佳俊②劉 杰*①黃亞樓②王 嫄①馮 霞③

①(南開大學(xué)計(jì)算機(jī)與控制工程學(xué)院 天津 300071)

②(南開大學(xué)軟件學(xué)院 天津 300071)

③(中國(guó)民航大學(xué)民航信息技術(shù)科研基地 天津 300300)

針對(duì)社交網(wǎng)絡(luò)的有向交互性和大規(guī)模特性，該文提出一種基于結(jié)構(gòu)相似度的有向網(wǎng)絡(luò)聚類算法(DirSCAN)，以及相應(yīng)的分布式并行算法(PDirSCAN)。考慮社交網(wǎng)絡(luò)中節(jié)點(diǎn)間的有向交互性，將行為結(jié)構(gòu)相似的節(jié)點(diǎn)聚集起來(lái)，并進(jìn)行節(jié)點(diǎn)功能分析。針對(duì)社交網(wǎng)絡(luò)規(guī)模巨大的特點(diǎn)，提出MapReduce框架下的分布式并行聚類算法，在確保聚類結(jié)果一致的前提下，提高處理性能。大量真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，DirSCAN比無(wú)向網(wǎng)絡(luò)聚類算法(SCAN)在F1上可提高2.34%的性能，并行算法PDirSCAN比DirSCAN運(yùn)行速度提升1.67倍，能夠有效處理大規(guī)模的有向網(wǎng)絡(luò)聚類問(wèn)題。

社交網(wǎng)絡(luò)；有向網(wǎng)絡(luò)聚類；并行算法；MapReduce

1 引言

隨著博客、微博等社交媒體的興起，以用戶為節(jié)點(diǎn)、以用戶關(guān)系為邊的社交網(wǎng)絡(luò)迅猛增長(zhǎng)。用戶的興趣、行為、功能等關(guān)系使社交網(wǎng)絡(luò)中存在多個(gè)社區(qū)或簇。為了發(fā)現(xiàn)網(wǎng)絡(luò)中隱藏的簇結(jié)構(gòu)，傳統(tǒng)的網(wǎng)絡(luò)聚類方法主要基于鏈接的稠密度(linkdensity)，使得簇內(nèi)節(jié)點(diǎn)距離較近，簇間節(jié)點(diǎn)距離較遠(yuǎn)，如經(jīng)典的Newman快速算法[1]和Kernighan-Lin算法[2]。然而，以上算法忽略了社交網(wǎng)絡(luò)有向交互性和節(jié)點(diǎn)具有不同功能。一方面，社交網(wǎng)絡(luò)中的節(jié)點(diǎn)關(guān)系是有向的，如微博中的關(guān)注關(guān)系，不同方向表明了不同的興趣信息。另一方面，社交網(wǎng)絡(luò)中節(jié)點(diǎn)具有不同功能，如連接多個(gè)簇的樞紐節(jié)點(diǎn)具有跨簇傳播功能；孤立的離群節(jié)點(diǎn)在噪音檢測(cè)、流失客戶檢測(cè)等任務(wù)中有重要作用。這兩個(gè)結(jié)構(gòu)特點(diǎn)對(duì)社交網(wǎng)絡(luò)的理解和功能發(fā)現(xiàn)有重要的意義。

當(dāng)前的社交網(wǎng)絡(luò)聚類方法除了傳統(tǒng)基于鏈接稠密度的方法[1-3]外，還包括考慮節(jié)點(diǎn)功能特性、網(wǎng)絡(luò)的有向性等社交特性的聚類方法。另外，面向大規(guī)模社交網(wǎng)絡(luò)的并行聚類方法也是目前重要研究方向之一。

文獻(xiàn)[4]在鏈接稠密度的基礎(chǔ)上，同時(shí)考慮結(jié)構(gòu)相似度，提出SCAN算法，并分析節(jié)點(diǎn)功能。然而，該算法僅針對(duì)無(wú)向網(wǎng)絡(luò)聚類，未考慮社交網(wǎng)絡(luò)的有向性。考慮社交網(wǎng)絡(luò)中的關(guān)系存在有向性，文獻(xiàn)[5]將有向邊轉(zhuǎn)換為無(wú)向邊，再使用傳統(tǒng)的無(wú)向網(wǎng)絡(luò)聚類方法聚類，然而該無(wú)向化方法損失了社交網(wǎng)絡(luò)的有向結(jié)構(gòu)特性。文獻(xiàn)[6]將有向網(wǎng)絡(luò)聚類問(wèn)題轉(zhuǎn)化成對(duì)有向圖進(jìn)行加權(quán)切割的優(yōu)化問(wèn)題進(jìn)行解決。但是文獻(xiàn)[5,6]算法并未區(qū)分網(wǎng)絡(luò)中的節(jié)點(diǎn)功能。因此，本文基于SCAN提出有向網(wǎng)絡(luò)聚類算法(DirSCAN)。

近年來(lái)，大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的快速增長(zhǎng)促進(jìn)了動(dòng)態(tài)增量和分布式并行聚類算法的研究。文獻(xiàn)[7]提出一種隨機(jī)游走與動(dòng)態(tài)增量相關(guān)節(jié)點(diǎn)結(jié)合的網(wǎng)絡(luò)聚類算法挖掘社區(qū)。文獻(xiàn)[8]在MapReduce系統(tǒng)上設(shè)計(jì)了大數(shù)據(jù)并行聚類算法，采用抽樣來(lái)減小數(shù)據(jù)。文獻(xiàn)[9]提出一種基于社交關(guān)系的模糊聚類算法，輔助數(shù)據(jù)分布式存儲(chǔ)，提升數(shù)據(jù)訪問(wèn)效率。然而，此類方法存在信息丟失，無(wú)法得到與原算法一致的結(jié)果。本文前期工作提出了并行的SCAN算法PSCAN[10]，可得與原算法等價(jià)的結(jié)果，與文獻(xiàn)[11]類似。

本文創(chuàng)新點(diǎn)在于，考慮上述兩方面，在識(shí)別簇與節(jié)點(diǎn)功能的SCAN(Structural Clustering Algorithm for Networks)[4]算法基礎(chǔ)上，設(shè)計(jì)了基于結(jié)構(gòu)相似度的有向網(wǎng)絡(luò)聚類算法DirSCAN (Structural Clustering Algorithm for Directed Networks)。此外，近幾年社交網(wǎng)絡(luò)發(fā)展迅猛，海量節(jié)點(diǎn)及復(fù)雜關(guān)系的分析對(duì)單機(jī)串行方法是一個(gè)巨大的挑戰(zhàn)。針對(duì)這種用戶數(shù)上億、關(guān)系復(fù)雜的大規(guī)模社交網(wǎng)絡(luò)，本文基于MapReduce[12]分布式并行架構(gòu)將DirSCAN并行化，提出PDirSCAN(Parallel DirSCAN)，在聚類結(jié)果一致下提高運(yùn)行速度。

2 有向網(wǎng)絡(luò)聚類算法DirSCAN

在社交網(wǎng)絡(luò)中，由節(jié)點(diǎn)主動(dòng)發(fā)起的關(guān)聯(lián)與節(jié)點(diǎn)本身的興趣、行為直接相關(guān)，而節(jié)點(diǎn)被動(dòng)接收的關(guān)聯(lián)則表明了其他節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)的興趣，而非直接表明節(jié)點(diǎn)本身特性。如微博中用戶A關(guān)注其感興趣的用戶B，而B未關(guān)注A，則A的興趣偏好由B直接體現(xiàn)，而B則無(wú)法用A直接描述。在這種情況下，節(jié)點(diǎn)的出邊較之入邊更能反映節(jié)點(diǎn)信息。因此本文重點(diǎn)考慮節(jié)點(diǎn)的出邊，提出結(jié)構(gòu)相似度假設(shè)：若兩個(gè)節(jié)點(diǎn)所能到達(dá)的節(jié)點(diǎn)越相似，則兩節(jié)點(diǎn)屬于同一簇的可能性越大。

2.1 DirSCAN算法的基本定義

給定一個(gè)有向網(wǎng)絡(luò)G={V,E},V為節(jié)點(diǎn)集合，E為連接節(jié)點(diǎn)的有向邊集合。從節(jié)點(diǎn)v到節(jié)點(diǎn)w的有向邊記為＜v,w＞，其中v,w∈V。節(jié)點(diǎn)v的結(jié)構(gòu)定義為從v出發(fā)一步到達(dá)的節(jié)點(diǎn)集合及其本身，記為Γ(v)。

根據(jù)結(jié)構(gòu)相似度假設(shè)，兩節(jié)點(diǎn)的到達(dá)節(jié)點(diǎn)重合越多則越相似，因此，兩點(diǎn)之間的結(jié)構(gòu)相似度定義為

在社交網(wǎng)絡(luò)中，如果用戶A與用戶B共同關(guān)注了一群相同的人，那么可認(rèn)為A與B興趣相似，我們將網(wǎng)絡(luò)中興趣相似的節(jié)點(diǎn)定義為到達(dá)鄰居，如式(3)所示。

其中，ε是用于劃分鄰居與非鄰居的相似度閾值。若ε=0，則所有到達(dá)節(jié)點(diǎn)均為鄰居節(jié)點(diǎn)。

當(dāng)一個(gè)節(jié)點(diǎn)擁有較多的到達(dá)鄰居節(jié)點(diǎn)，我們認(rèn)為其足夠活躍，將其定義為核節(jié)點(diǎn)，用于擴(kuò)大簇。

定義1 核節(jié)點(diǎn)。若節(jié)點(diǎn)v的到達(dá)鄰居節(jié)點(diǎn)個(gè)數(shù)超過(guò)某一臨界值，則v為核節(jié)點(diǎn)，定義為

其中，μ(μ＞0)是活躍節(jié)點(diǎn)的到達(dá)鄰居臨界參數(shù)，用于判定核節(jié)點(diǎn)。

擴(kuò)大簇的過(guò)程如定義2所示。

定義2 直接結(jié)構(gòu)可達(dá)。若一個(gè)節(jié)點(diǎn)w是一個(gè)核節(jié)點(diǎn)v的到達(dá)鄰居節(jié)點(diǎn)，則w也應(yīng)該與v屬于同一個(gè)簇。我們將這一過(guò)程定義為v直接結(jié)構(gòu)可達(dá)w，即核節(jié)點(diǎn)與其到達(dá)鄰居節(jié)點(diǎn)應(yīng)屬于同一簇，如式(5)所示。

2.2 DirSCAN算法流程

接下來(lái)，介紹DirSCAN算法是如何工作的，包括如何實(shí)現(xiàn)簇的搜索以及如何分析節(jié)點(diǎn)的功能，樞紐和離群。第1步，將所有節(jié)點(diǎn)初始化為未分簇點(diǎn)；第2步，遍歷所有核節(jié)點(diǎn)，并尋找核節(jié)點(diǎn)的直接結(jié)構(gòu)可達(dá)節(jié)點(diǎn)，將它們合并為一個(gè)簇，根據(jù)簇中的核節(jié)點(diǎn)重復(fù)第2步再次擴(kuò)展簇，直到?jīng)]有新節(jié)點(diǎn)加入；第3步，遍歷所有的未分簇節(jié)點(diǎn)，根據(jù)與其相鄰的簇的數(shù)目將其分為樞紐點(diǎn)或離群點(diǎn)，有多個(gè)相鄰簇的是樞紐節(jié)點(diǎn)，至多只有1個(gè)相鄰簇的即為離群節(jié)點(diǎn)。具體算法如表1所示。

需要注意的是，DirSCAN的最終分類結(jié)果對(duì)節(jié)點(diǎn)處理順序不敏感。DirSCAN算法與SCAN算法的不同之處在于兩方面。一方面，DirSCAN的結(jié)構(gòu)相似度考慮了節(jié)點(diǎn)的到達(dá)鄰居，即節(jié)點(diǎn)的出邊這一有向傳播特性；另一方面，由于DirSCAN采用有向邊來(lái)定義直接結(jié)構(gòu)可達(dá)性，因此該特性不可逆。這兩方面的考慮使得本文所計(jì)算的結(jié)構(gòu)相似度更能反映真實(shí)社交網(wǎng)絡(luò)的情況。

表1 有向網(wǎng)絡(luò)聚類算法DirSCAN

2.3 DirSCAN算法的復(fù)雜度分析

DirSCAN算法僅需遍歷有限次節(jié)點(diǎn)和邊，一次遍歷即可獲得節(jié)點(diǎn)的到達(dá)鄰居、判斷核節(jié)點(diǎn)，從而以核節(jié)點(diǎn)進(jìn)行簇?cái)U(kuò)展。因此若網(wǎng)絡(luò)中存在n個(gè)節(jié)點(diǎn)，遍歷節(jié)點(diǎn)的復(fù)雜度為O(n)。在遍歷邊時(shí)，需要計(jì)算節(jié)點(diǎn)的每條出邊是否為到達(dá)鄰居關(guān)系，最差情況為所有節(jié)點(diǎn)都相連，復(fù)雜度為O(n(n-1))。由于實(shí)際社交網(wǎng)絡(luò)通常為稀疏網(wǎng)絡(luò)[4]，遍歷邊的次數(shù)可近似為遍歷節(jié)點(diǎn)的次數(shù)。因此DirSCAN算法的時(shí)間復(fù)雜度近似為O(n)。

3 并行有向網(wǎng)絡(luò)聚類算法PDirSCAN

為了適應(yīng)大規(guī)模社交網(wǎng)絡(luò)的聚類，本節(jié)將在MapReduce并行平臺(tái)上設(shè)計(jì)并行化算法PDirSCAN。

通過(guò)分析發(fā)現(xiàn)，DirSCAN算法對(duì)節(jié)點(diǎn)的操作主要分為兩個(gè)步驟：識(shí)別到達(dá)鄰居與核節(jié)點(diǎn)；擴(kuò)充簇以完成聚類。第1步中，每個(gè)節(jié)點(diǎn)都可以獨(dú)立計(jì)算到達(dá)鄰居和節(jié)點(diǎn)間的結(jié)構(gòu)相似度。第2步中，每個(gè)核節(jié)點(diǎn)可獨(dú)立將其標(biāo)簽傳遞給其到達(dá)鄰居。可見，DirSCAN算法并行化是可行的。

MapReduce的并行數(shù)據(jù)處理過(guò)程可分為兩個(gè)步驟：Map和Reduce。Map將輸入的＜key, value＞對(duì)映射到新的＜key, value＞對(duì)上，用來(lái)將數(shù)據(jù)打散成多組子數(shù)據(jù)。Reduce獨(dú)立并行地處理各組子數(shù)據(jù)。MapReduce自身提供了很好的容錯(cuò)性，使得整個(gè)任務(wù)不會(huì)因?yàn)槟硞€(gè)處理節(jié)點(diǎn)的癱瘓而整體崩潰。

3.1 PDirSCAN中識(shí)別到達(dá)鄰居的并行化

并行識(shí)別節(jié)點(diǎn)到達(dá)鄰居這一步驟由兩個(gè)MapReduce任務(wù)來(lái)實(shí)現(xiàn)。第1個(gè)MapReduce任務(wù)并行計(jì)算每個(gè)節(jié)點(diǎn)與其臨近點(diǎn)之間的到達(dá)鄰居關(guān)系，如圖1(a)～1(d)所示。其中Map函數(shù)將網(wǎng)絡(luò)隨機(jī)切分成若干份，然后復(fù)制多個(gè)副本，將其兩兩合并形成對(duì)，假設(shè)網(wǎng)絡(luò)被分割成4份，則需要6次合并。Reduce函數(shù)在本地計(jì)算每個(gè)節(jié)點(diǎn)的到達(dá)鄰居。第2個(gè)MapReduce任務(wù)對(duì)每個(gè)節(jié)點(diǎn)的所有到達(dá)鄰居進(jìn)行匯總，僅進(jìn)行Reduce步驟，如圖1(e)所示。其中Reduce函數(shù)將所有中間數(shù)據(jù)進(jìn)行排序，排序后可依次將含同一節(jié)點(diǎn)的數(shù)據(jù)聚合。

3.2 PDirSCAN中簇?cái)U(kuò)展的并行化

當(dāng)獲得了所有節(jié)點(diǎn)的到達(dá)鄰居之后，可判斷該節(jié)點(diǎn)是否為核節(jié)點(diǎn)，隨后進(jìn)行簇?cái)U(kuò)展。在這一過(guò)程中，通過(guò)核節(jié)點(diǎn)來(lái)傳播簇標(biāo)簽以獲得最終的結(jié)果，可由兩個(gè)MapReduce任務(wù)完成。第1個(gè)任務(wù)將數(shù)據(jù)隨機(jī)劃分為若干份(如圖1(a)所示，其中粗邊節(jié)點(diǎn)是核節(jié)點(diǎn))，將多個(gè)副本進(jìn)行兩兩合并，擴(kuò)展簇標(biāo)簽(如圖1(b)～1(d)所示，節(jié)點(diǎn)右下角為節(jié)點(diǎn)所屬的簇標(biāo)簽，其中“-1”為處理過(guò)但未分配簇的節(jié)點(diǎn))。第2個(gè)任務(wù)將所有聚類后的簇標(biāo)簽合并，實(shí)現(xiàn)標(biāo)簽的全局傳播及聚類，如圖1(e)～1(f)所示。由于相同簇節(jié)點(diǎn)在不同機(jī)器上聚類的簇標(biāo)簽不一致，如圖1(e)所示，同簇中的節(jié)點(diǎn)曾被聚為2, 4, 6, 8, 10簇，因此本文將簇標(biāo)簽索引列表中的最小標(biāo)簽作為該簇的標(biāo)簽完成標(biāo)簽一致化，如圖1(f)，其中簇標(biāo)簽索引列表記錄相同簇中所有節(jié)點(diǎn)曾標(biāo)記過(guò)的簇標(biāo)簽。最后，獲得最終的簇集合。那些無(wú)簇標(biāo)簽的節(jié)點(diǎn)則根據(jù)其到達(dá)鄰居的簇類別數(shù)標(biāo)記為樞紐點(diǎn)或離群點(diǎn)。

圖1 聚類并行過(guò)程細(xì)節(jié)

3.3 PDirSCAN的算法復(fù)雜度分析

假設(shè)有向網(wǎng)絡(luò)中，有n個(gè)節(jié)點(diǎn)，被p臺(tái)機(jī)器劃分成m份。由DirSCAN的算法復(fù)雜度可知串行計(jì)算的時(shí)間復(fù)雜度為Ts=O(n)，則并行后數(shù)據(jù)處理時(shí)間復(fù)雜度為O(n/p)。假設(shè)通信之前的同步用時(shí)為T0，由于每個(gè)節(jié)點(diǎn)都需要至少傳送到其他節(jié)點(diǎn)一次，因此并行時(shí)通信用時(shí)為Tc=T0+O(n(m -1)/2)。綜上所述，PDirSCAN總復(fù)雜度為，Tp=T0+ O(n(m-1)/2)+O(n/p)。若通信用時(shí)Tc小于串行計(jì)算用時(shí)Ts，則并行計(jì)算時(shí)間復(fù)雜度優(yōu)于串行計(jì)算。由于社交網(wǎng)絡(luò)大都是稀疏網(wǎng)絡(luò)，因此通信用時(shí)較少，并行算法存在速度優(yōu)勢(shì)。

4 實(shí)驗(yàn)與分析

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

本文在兩個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。在網(wǎng)絡(luò)數(shù)據(jù)集WebKB[13]上，進(jìn)行有向網(wǎng)絡(luò)聚類的準(zhǔn)確性實(shí)驗(yàn)，對(duì)比分析DirSCAN與SCAN。在大規(guī)模的社交網(wǎng)絡(luò)數(shù)據(jù)集Pokec[14]上，進(jìn)行PDirSCAN的并行效率實(shí)驗(yàn)。

WebKB數(shù)據(jù)集包含了Texas, Washington, Cornell, Wisconsin這4所大學(xué)網(wǎng)頁(yè)之間的鏈接情況，包含877個(gè)節(jié)點(diǎn)和1608個(gè)有向邊。這些網(wǎng)頁(yè)可分為5類：課程，教師，員工，學(xué)生以及項(xiàng)目。

Pokec大規(guī)模社交網(wǎng)站數(shù)據(jù)集記錄了斯洛伐克的好友關(guān)注關(guān)系網(wǎng)絡(luò)，包含1632803個(gè)節(jié)點(diǎn)和30622564條有向邊，平均節(jié)點(diǎn)出度為18.8。Pokec沒(méi)有真實(shí)分類，因此僅用于測(cè)試并行實(shí)驗(yàn)中的效率。

4.2 評(píng)價(jià)指標(biāo)介紹

準(zhǔn)確性實(shí)驗(yàn)采用聚類常用的評(píng)價(jià)指標(biāo)準(zhǔn)確率(Precision, P)、召回率(Recall, R)、F1值和邊緣索引 (Rand Index, RI)來(lái)評(píng)價(jià)聚類結(jié)果的準(zhǔn)確程度。真實(shí)情況下將同類兩個(gè)節(jié)點(diǎn)聚為一簇，為一個(gè)正確的聚類結(jié)果。這3個(gè)評(píng)價(jià)指標(biāo)的值越大表明聚類結(jié)果與真實(shí)情況越相似，聚類效果越好。

在并行效率實(shí)驗(yàn)中，我們采用并行實(shí)驗(yàn)中的常用評(píng)價(jià)指標(biāo)加速比(speedup)、規(guī)模增長(zhǎng)性(sizeup)和可擴(kuò)展性(scaleup)進(jìn)行度量。加速比指串行與并行處理最短用時(shí)之比，加速比越大說(shuō)明并行用時(shí)越短。規(guī)模增長(zhǎng)性是指并行計(jì)算m倍數(shù)據(jù)量與單倍數(shù)據(jù)量的時(shí)間比，該指標(biāo)越小說(shuō)明數(shù)據(jù)增多用時(shí)增長(zhǎng)慢。可擴(kuò)展性是指在單機(jī)上處理單倍數(shù)據(jù)量與在m臺(tái)機(jī)器上處理m倍數(shù)據(jù)量的時(shí)間比，該指標(biāo)越大表明可擴(kuò)展性越好。

4.3 實(shí)驗(yàn)設(shè)置

本文采用SCAN作為對(duì)比算法。SCAN只適用于無(wú)向網(wǎng)絡(luò)聚類，因此先將有向網(wǎng)絡(luò)轉(zhuǎn)換為無(wú)向網(wǎng)絡(luò)。算法中的參數(shù)ε將遍歷[0,1]中步長(zhǎng)為0.1的數(shù)值來(lái)進(jìn)行優(yōu)化，μ將遍歷[1,10]中步長(zhǎng)為1的數(shù)值來(lái)進(jìn)行優(yōu)化。

4.4 實(shí)驗(yàn)結(jié)果及分析

4.4.1 DirSCAN聚類算法的準(zhǔn)確性實(shí)驗(yàn)結(jié)果 在WebKB, Texas, Washington數(shù)據(jù)集上的聚類準(zhǔn)確率實(shí)驗(yàn)結(jié)果如表2所示。結(jié)果顯示，考慮了網(wǎng)絡(luò)有向性的DirSCAN算法，在準(zhǔn)確率P、召回率R、F1值和RI上都優(yōu)于無(wú)向圖聚類算法SCAN，分別提高0.39%, 8.83%, 2.34%和0.88%。其中，召回率R和F1值提升最明顯。在WebKB各大學(xué)的子數(shù)據(jù)集上也有相似結(jié)果，Texas子數(shù)據(jù)集中DirSCAN在召回率R、F1值上分別提升16.98%, 7.05%, Washington子數(shù)據(jù)集中DirSCAN在召回率R、F1值上分別提升11.44%, 3.05%，可見，考慮網(wǎng)絡(luò)有向性對(duì)聚類有效。

4.4.2 PDirSCAN并行化算法的效率實(shí)驗(yàn)結(jié)果 為了驗(yàn)證PDirSCAN的并行效率，本文在4臺(tái)計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)。每一臺(tái)機(jī)器的處理器都為2.59 GHz AMD Phenom(tm) II X4 810, 3G內(nèi)存。本文將Reduce任務(wù)的數(shù)目設(shè)置成與集群的機(jī)器數(shù)目相同，即每一臺(tái)機(jī)器處理至多一個(gè)Reduce任務(wù)。在所有并行實(shí)驗(yàn)中，數(shù)據(jù)集都被分成24份，保證所需要合并的次數(shù)相同。多次實(shí)驗(yàn)驗(yàn)證，并行實(shí)驗(yàn)結(jié)果與串行一致[11]。

在Pokec數(shù)據(jù)集上的并行效率實(shí)驗(yàn)結(jié)果如圖2所示。實(shí)驗(yàn)表明，(1)當(dāng)節(jié)點(diǎn)數(shù)量不變時(shí)，加速比隨機(jī)器數(shù)目增多而提高，說(shuō)明所需的處理時(shí)間減少了；當(dāng)節(jié)點(diǎn)數(shù)增加時(shí)，加速比增加更顯著，在8×105節(jié)點(diǎn)4臺(tái)機(jī)器，比單機(jī)處理速度提高了1.67倍，見圖2(a)。(2)單機(jī)處理節(jié)點(diǎn)時(shí)，規(guī)模增長(zhǎng)性提升較快，即節(jié)點(diǎn)增加使處理時(shí)間增長(zhǎng)(8×105節(jié)點(diǎn)比1×105節(jié)點(diǎn)耗時(shí)多了1.87倍)，而當(dāng)機(jī)器數(shù)增加時(shí)，規(guī)模增長(zhǎng)性提升緩慢，即時(shí)間消耗無(wú)顯著增加，使用4臺(tái)機(jī)器時(shí)，8×105節(jié)點(diǎn)比1×105節(jié)點(diǎn)耗時(shí)僅多了1.28倍，比單機(jī)快了0.59倍，見圖2(b)。(3)當(dāng)機(jī)器數(shù)目與數(shù)據(jù)量等比增加時(shí)，可擴(kuò)展性提高至1.1，即若單機(jī)處理1×105節(jié)點(diǎn)需費(fèi)t時(shí)，4臺(tái)機(jī)器采用PDirSCAN可僅用0.9t的時(shí)間處理4×105節(jié)點(diǎn)，見圖2(c)。

綜上所述，PDirSCAN在聚類結(jié)果與DirSCAN一致下，提高了處理速度，有較高的實(shí)際應(yīng)用價(jià)值。

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

本文針對(duì)社交網(wǎng)絡(luò)的有向交互性，提出基于結(jié)構(gòu)相似度的有向網(wǎng)絡(luò)聚類方法DirSCAN來(lái)檢測(cè)社區(qū)，F(xiàn)1值可提升2.34%。針對(duì)真實(shí)網(wǎng)絡(luò)大規(guī)模特性，本文提出基于MapReduce的并行化算法PDirSCAN提高算法速度1.67倍。實(shí)驗(yàn)結(jié)果表明本文算法提高了網(wǎng)絡(luò)聚類的效率和速度，具有較大的實(shí)用價(jià)值。

表2 兩種算法在WebKB, Texas, Washington數(shù)據(jù)集上的聚類結(jié)果(%)

圖2 PDirSCAN在Pokec數(shù)據(jù)集上的并行結(jié)果

[1] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133-1-066133-5.

[2] Lancichinetti A, Fortunato S, and Kertész J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009, 11(3): 033015-1-033015-18.

[3] Fallani F D V, Nicosia V, Latora V, et al.. Nonparametric resampling of random walks for spectral network clustering[J].Physical Review E, 2014, 89(1): 012802-1-012802-5.

[4] Xu Xiao-wei, Yuruk N, Feng Zhi-dan, et al.. SCAN: a structural clustering algorithm for networks[C]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, 2007: 824-833.

[5] Zhou Deng-yong, Huang Jia-yuan, and Sch?lkopf B. Learning from labeled and unlabeled data on a directed graph[C]. Proceedings of the 22nd International Conference on Machine Learning, Bonn, 2005: 1036-1043.

[6] Meila M and Pentney W. Clustering by weighted cuts in directed graphs[C]. Proceedings of the 7th SIAM International Conference on Data Mining, Minneapolis, 2007: 135-144.

[7] 肖杰斌, 張紹武. 基于隨機(jī)游走和增量相關(guān)節(jié)點(diǎn)的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)挖掘算法[J]. 電子與信息學(xué)報(bào), 2013, 35(4): 977-981. Xiao Jie-bin and Zhang Shao-wu. An algorithm of integrating random walk and increment correlative vertexes for mining community of dynamic networks[J]. Journal of Electronics & Information Technology, 2013, 35(4): 977-981.

[8] Ene A, Im S, and Moseley B. Fast clustering using MapReduce[C]. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, 2011: 681-689.

[9] Cao Yan, Cao Jian, and Li Ming-lu. Distributed data distribution mechanism in social network based on fuzzy clustering[J]. Foundations and Applications of Intelligent Systems, 2014, 213: 603-620.

[10] Chen Jia-jun, Chen Ji-meng, Liu Jie, et al.. PSCAN: a parallel structural clustering algorithm for networks[C]. Proceedings of the 2013 International Conference on Machine Learning and Cybernetics, Tianjin, 2013: 839-844.

[11] Zhao Wei-zhong, Venkataswamy M, and Xu Xiao-wei. PSCAN: a parallel structural clustering algorithm for big networks in mapReduce[C]. Proceedings of the 2013 IEEE 27th International Conference on Advanced Information Networking and Applications, Washington DC, 2013: 862-869.

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

[13] Craven M, DiPasquo D, Freitag D, et al.. Learning to extract symbolic knowledge from the world wide web[C]. Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98), Madison, 1998: 509-516.

[14] Takac L and Zabovsky M. Data analysis in public social networks[C]. Proceedings of International Scientific Conference & International Workshop Present Day Trends of Innovations, Lomza, 2012: 1-6.

陳季夢(mèng)： 女，1987年生，博士生，研究方向?yàn)閿?shù)據(jù)挖掘.

陳佳俊： 男，1988年生，碩士，研究方向?yàn)椴⑿信c分布式計(jì)算.

劉 杰： 男，1979年生，博士，副教授，研究方向?yàn)闄C(jī)器學(xué)習(xí).

Clustering Algorithms for Large-scale Social Networks Based on Structural Similarity

Chen Ji-meng①Chen Jia-jun②Liu Jie①Huang Ya-lou②Wang Yuan①Feng Xia③

①(College of Computer and Control Engineering, Nankai University, Tianjin 300071, China)
②(College of Software, Nankai University, Tianjin 300071, China)
③(Information Technology Research Base of CAAC, Civil Aviation University of China, Tianjin 300300, China)

To cluster the directed and large-scale social networks, a Structural Clustering Algorithm for Directed Networks (DirSCAN) and a corresponding Parallel algorithm (PDirSCAN) are proposed. Considering oriented behavioral relation between two vertices, DirSCAN is constructed based on action structural similarity and function analysis. To meet the need of large-scale social network analysis, a lossless PDirSCAN based on MapReduce distributed parallel architecture is designed to improve the processing performance. A large number of experimental results on real-world network datasets show that DirSCAN improves performance of SCAN up to 2.34% on F1, PDirSCAN runs 1.67 times faster than DirSCAN.

Social networks; Directed network clustering; Parallel algorithm; MapReduce

TP393

A

1009-5896(2015)02-0449-06

10.11999/JEIT140512

2014-04-22收到，2014-08-27改回

國(guó)家自然科學(xué)基金(61105049, 61300166)，中國(guó)民航信息技術(shù)科研基地開放課題基金(CAAC-ITRB-201303, CAAC-ITRB-201204)，天津市科技計(jì)劃項(xiàng)目(13ZCZDGX01098)和天津市自然科學(xué)基金(14JCQNJC00600)資助課題

*通信作者：劉杰 jliu@nankai.edu.cn