基于結構相似度的大規模社交網絡聚類算法

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

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

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

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

基于結構相似度的大規模社交網絡聚類算法

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

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

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

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

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

社交網絡；有向網絡聚類；并行算法；MapReduce

1 引言

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

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

文獻[4]在鏈接稠密度的基礎上，同時考慮結構相似度，提出SCAN算法，并分析節點功能。然而，該算法僅針對無向網絡聚類，未考慮社交網絡的有向性。考慮社交網絡中的關系存在有向性，文獻[5]將有向邊轉換為無向邊，再使用傳統的無向網絡聚類方法聚類，然而該無向化方法損失了社交網絡的有向結構特性。文獻[6]將有向網絡聚類問題轉化成對有向圖進行加權切割的優化問題進行解決。但是文獻[5,6]算法并未區分網絡中的節點功能。因此，本文基于SCAN提出有向網絡聚類算法(DirSCAN)。

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

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

2 有向網絡聚類算法DirSCAN

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

2.1 DirSCAN算法的基本定義

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

根據結構相似度假設，兩節點的到達節點重合越多則越相似，因此，兩點之間的結構相似度定義為

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

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

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

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

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

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

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

2.2 DirSCAN算法流程

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

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

表1 有向網絡聚類算法DirSCAN

2.3 DirSCAN算法的復雜度分析

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

3 并行有向網絡聚類算法PDirSCAN

為了適應大規模社交網絡的聚類，本節將在MapReduce并行平臺上設計并行化算法PDirSCAN。

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

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

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

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

3.2 PDirSCAN中簇擴展的并行化

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

圖1 聚類并行過程細節

3.3 PDirSCAN的算法復雜度分析

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

4 實驗與分析

4.1 實驗數據集

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

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

Pokec大規模社交網站數據集記錄了斯洛伐克的好友關注關系網絡，包含1632803個節點和30622564條有向邊，平均節點出度為18.8。Pokec沒有真實分類，因此僅用于測試并行實驗中的效率。

4.2 評價指標介紹

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

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

4.3 實驗設置

本文采用SCAN作為對比算法。SCAN只適用于無向網絡聚類，因此先將有向網絡轉換為無向網絡。算法中的參數ε將遍歷[0,1]中步長為0.1的數值來進行優化，μ將遍歷[1,10]中步長為1的數值來進行優化。

4.4 實驗結果及分析

4.4.1 DirSCAN聚類算法的準確性實驗結果 在WebKB, Texas, Washington數據集上的聚類準確率實驗結果如表2所示。結果顯示，考慮了網絡有向性的DirSCAN算法，在準確率P、召回率R、F1值和RI上都優于無向圖聚類算法SCAN，分別提高0.39%, 8.83%, 2.34%和0.88%。其中，召回率R和F1值提升最明顯。在WebKB各大學的子數據集上也有相似結果，Texas子數據集中DirSCAN在召回率R、F1值上分別提升16.98%, 7.05%, Washington子數據集中DirSCAN在召回率R、F1值上分別提升11.44%, 3.05%，可見，考慮網絡有向性對聚類有效。

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

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

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

5 結束語

本文針對社交網絡的有向交互性，提出基于結構相似度的有向網絡聚類方法DirSCAN來檢測社區，F1值可提升2.34%。針對真實網絡大規模特性，本文提出基于MapReduce的并行化算法PDirSCAN提高算法速度1.67倍。實驗結果表明本文算法提高了網絡聚類的效率和速度，具有較大的實用價值。

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

圖2 PDirSCAN在Pokec數據集上的并行結果

[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]. 電子與信息學報, 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年生，博士生，研究方向為數據挖掘.

陳佳俊： 男，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)，中國民航信息技術科研基地開放課題基金(CAAC-ITRB-201303, CAAC-ITRB-201204)，天津市科技計劃項目(13ZCZDGX01098)和天津市自然科學基金(14JCQNJC00600)資助課題

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