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

陳季夢陳佳俊劉 杰*黃亞樓王 嫄馮 霞

①(南開大學計算機與控制工程學院 天津 300071)

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

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

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

陳季夢①陳佳?、趧?杰*①黃亞樓②王 嫄①馮 霞③

①(南開大學計算機與控制工程學院 天津 300071)

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

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

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

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

1 引言

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

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

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

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

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

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

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

2.1 DirSCAN算法的基本定義

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

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

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

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

當一個節(jié)點擁有較多的到達鄰居節(jié)點，我們認為其足夠活躍，將其定義為核節(jié)點，用于擴大簇。

定義1 核節(jié)點。若節(jié)點v的到達鄰居節(jié)點個數(shù)超過某一臨界值，則v為核節(jié)點，定義為

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

擴大簇的過程如定義2所示。

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

2.2 DirSCAN算法流程

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

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

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

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

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

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

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

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

MapReduce的并行數(shù)據(jù)處理過程可分為兩個步驟：Map和Reduce。Map將輸入的＜key, value＞對映射到新的＜key, value＞對上，用來將數(shù)據(jù)打散成多組子數(shù)據(jù)。Reduce獨立并行地處理各組子數(shù)據(jù)。MapReduce自身提供了很好的容錯性，使得整個任務(wù)不會因為某個處理節(jié)點的癱瘓而整體崩潰。

3.1 PDirSCAN中識別到達鄰居的并行化

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

3.2 PDirSCAN中簇擴展的并行化

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

圖1 聚類并行過程細節(jié)

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

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

4 實驗與分析

4.1 實驗數(shù)據(jù)集

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

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

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

4.2 評價指標介紹

準確性實驗采用聚類常用的評價指標準確率(Precision, P)、召回率(Recall, R)、F1值和邊緣索引 (Rand Index, RI)來評價聚類結(jié)果的準確程度。真實情況下將同類兩個節(jié)點聚為一簇，為一個正確的聚類結(jié)果。這3個評價指標的值越大表明聚類結(jié)果與真實情況越相似，聚類效果越好。

在并行效率實驗中，我們采用并行實驗中的常用評價指標加速比(speedup)、規(guī)模增長性(sizeup)和可擴展性(scaleup)進行度量。加速比指串行與并行處理最短用時之比，加速比越大說明并行用時越短。規(guī)模增長性是指并行計算m倍數(shù)據(jù)量與單倍數(shù)據(jù)量的時間比，該指標越小說明數(shù)據(jù)增多用時增長慢。可擴展性是指在單機上處理單倍數(shù)據(jù)量與在m臺機器上處理m倍數(shù)據(jù)量的時間比，該指標越大表明可擴展性越好。

4.3 實驗設(shè)置

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

4.4 實驗結(jié)果及分析

4.4.1 DirSCAN聚類算法的準確性實驗結(jié)果 在WebKB, Texas, Washington數(shù)據(jù)集上的聚類準確率實驗結(jié)果如表2所示。結(jié)果顯示，考慮了網(wǎng)絡(luò)有向性的DirSCAN算法，在準確率P、召回率R、F1值和RI上都優(yōu)于無向圖聚類算法SCAN，分別提高0.39%, 8.83%, 2.34%和0.88%。其中，召回率R和F1值提升最明顯。在WebKB各大學的子數(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ò)有向性對聚類有效。

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

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

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

5 結(jié)束語

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

表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] 肖杰斌, 張紹武. 基于隨機游走和增量相關(guān)節(jié)點的動態(tài)網(wǎng)絡(luò)社團挖掘算法[J]. 電子與信息學報, 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.

陳季夢： 女，1987年生，博士生，研究方向為數(shù)據(jù)挖掘.

陳佳?。?男，1988年生，碩士，研究方向為并行與分布式計算.

劉 杰： 男，1979年生，博士，副教授，研究方向為機器學習.

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改回

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

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