基于DeepWalk的社團檢測方法

彭欣宇

摘要：該文提出一種基于DeepWalk的網(wǎng)絡(luò)社團檢測方法。該算法的基本思想是基于圖嵌入的DeepWalk方法，利用網(wǎng)絡(luò)隨機游走的方式，把網(wǎng)絡(luò)結(jié)構(gòu)映射到歐氏空間中，然后利用經(jīng)典機器學(xué)習(xí)聚類算法進行聚類，從而得到社團。該文在具有社團標簽的網(wǎng)絡(luò)中進行實驗，從實驗中驗證了這種思想的可行性，取得了顯著的效果。

關(guān)鍵詞：DeepWalk；社團檢測；聚類

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）04-0168-02

1 概述

伴隨著網(wǎng)絡(luò)技術(shù)和計算機科學(xué)的技術(shù)高速發(fā)展，尤其是智能手機興起與快速普及，使人類已經(jīng)步入了一個全新的網(wǎng)絡(luò)時代。在人們生活的方方面面，隨處可見復(fù)雜網(wǎng)絡(luò)的身影，如科學(xué)家之間的合作網(wǎng)絡(luò)，國家電力網(wǎng)絡(luò)，電信通訊網(wǎng)絡(luò)等等。因此，近幾年，復(fù)雜網(wǎng)絡(luò)的研究價值和應(yīng)用價值越來越受到學(xué)術(shù)界和工業(yè)界的認可與重視。

隨著對網(wǎng)絡(luò)拓撲性質(zhì)的深入研究，人們發(fā)現(xiàn)在許多的網(wǎng)絡(luò)結(jié)構(gòu)中都能挖掘出一種共同的性質(zhì)：社團結(jié)構(gòu)。這種結(jié)構(gòu)在我們生活中也隨處可見，比如在社交關(guān)系中，如果來自同一個學(xué)?；蛘吖?，那么這群人的連接也會比來自其他學(xué)?；蛘吖镜囊蝗喝寺?lián)系更加緊密。社團結(jié)構(gòu)與計算機科學(xué)中的圖分割和社會學(xué)中的分級聚類有著密不可分的關(guān)系。[1]分級聚類是基于各個節(jié)點連接的相似性或強度將網(wǎng)絡(luò)劃分各個子群，且根據(jù)劃分時往網(wǎng)絡(luò)中添加還是移除邊可分為凝聚算法和分裂算法兩類，其中應(yīng)用非常廣泛的是Girvan和Newman提出的基于邊介數(shù)的分裂算法[2]和Breiger等人提出的Concor算法[3]；圖形分割最有名的算法是Kernighan-lin算法[4]和譜方法法[5]。

本文不同于之前的算法研究，提出一種基于DeepWalk的方法進行社團檢測，將網(wǎng)絡(luò)映射到歐氏空間中，然后利用機器學(xué)習(xí)的聚類方法進行聚類得到社團。

本文首先介紹deepwalk和機器學(xué)習(xí)中常見的聚類算法，并通過實驗來驗證本文提出算法的可行性，最后是本文結(jié)論。

2 相關(guān)研究

2.1 社團檢測算法

網(wǎng)絡(luò)的社團結(jié)構(gòu)具有同一社團內(nèi)部節(jié)點連接緊密，不同的社團節(jié)點連接稀疏[5]的屬性，而社團檢測方法旨在揭示出網(wǎng)絡(luò)中真實存在的社團結(jié)構(gòu)。社團檢測通常使用Newman提出的Modularity[5]來衡量算法的，Modularity（常用Q表示）通常定義為：

其中，表示網(wǎng)絡(luò)社團個數(shù)，表示網(wǎng)絡(luò)連接總數(shù)，表示社團內(nèi)連接總數(shù)，表示社團內(nèi)節(jié)點度之和。

近年來隨著復(fù)雜網(wǎng)絡(luò)社團檢測的研究發(fā)展，社團檢測算法大致可以分為以下三類[6]：1）基于優(yōu)化的劃分方法，主要分為譜方法[5，7]和局部搜索方法。2）啟發(fā)式方法。如最大流社團算法[8]、Newman算法（grivan newman，GN）等。3）其他劃分方法。如基于隨機游走的相似度算法[9]和節(jié)點聚類中心度算法[10]等。

2.2 DeepWalk

我們傳統(tǒng)表示網(wǎng)絡(luò)是基于圖挽留表示方式。比如我們可以用一個G=（V，E）來定義一個網(wǎng)絡(luò)，V是網(wǎng)絡(luò)中的節(jié)點集合，E是網(wǎng)絡(luò)中的邊集合。我們用不同的符號命名不同的節(jié)點，用二維數(shù)組或者鄰接矩陣來存儲網(wǎng)絡(luò)的連邊情況。當我們使用鄰接矩陣記錄網(wǎng)絡(luò)拓撲的時候就可以利用線性代數(shù)的一些概念去解決網(wǎng)絡(luò)中的一些問題。但是缺點也很明顯，如果網(wǎng)絡(luò)是一個稀疏的網(wǎng)絡(luò)，那么會浪費大量的存儲空間。

所以現(xiàn)在提出一種網(wǎng)絡(luò)表示學(xué)習(xí)（Network Representation Learning， NRL），也稱圖嵌入法（Graph Embedding Method， GEM）的方式來表達網(wǎng)絡(luò)。這種方法的思想是用一種向量表示網(wǎng)絡(luò)中的節(jié)點。

DeepWalk[11]借用了NLP的方法，利用SkipGram的方法進行網(wǎng)絡(luò)中節(jié)點的表示學(xué)習(xí)。按照SkipGram的思路，我們需要解決的就是如果定義“文本內(nèi)容”，也就是“鄰居”。在自然語言處理里面，單詞的鄰居就是周圍的單詞，而在DeepWalk是用隨機游走的序列來作為網(wǎng)絡(luò)節(jié)點的鄰居。

具體步驟：首先隨機游走隨機均勻地選取網(wǎng)絡(luò)節(jié)點，并生成固定長度的游走序列。這個游走序列就相當于自然語言中的句子，節(jié)點的序列是句子，而序列中的節(jié)點就是句子中的單詞，然后將這個生成的序列放入SkipGram進行訓(xùn)練得到模型。

2.3 聚類算法

聚類分析也叫群分析，其主要研究分類問題的一種基于統(tǒng)計分析方法，在數(shù)據(jù)挖掘中也有重要的應(yīng)用。

聚類算法主要思想是依據(jù)某種特定的標準（比如數(shù)據(jù)之間的距離）把一個數(shù)據(jù)集劃分為不同的類或者簇，使內(nèi)部的數(shù)據(jù)具有較高的相似性，而不同簇的數(shù)據(jù)之間差異較大。較通俗的解釋就是讓相似的數(shù)據(jù)盡可以聚集在一起，不同的數(shù)據(jù)相距更遠，從而可以清晰劃分數(shù)據(jù)的類。常見的算法有K-Means和層次聚類等

2.3.1 K-Means聚類算法

K-Means是經(jīng)典的聚類算法，K為事先確定的常數(shù)，常數(shù)K也同時意味著數(shù)據(jù)最終的類別數(shù)量。首先隨機選取K個類的質(zhì)心，計算每個數(shù)據(jù)與質(zhì)心的距離，將每個數(shù)據(jù)分到最近的質(zhì)心類，然后重新計算每個類的質(zhì)心，重復(fù)以上過程，直至質(zhì)心不再改變，最終確定每個類的成員數(shù)據(jù)。

K-Means算法思想簡單，易于實現(xiàn)，但是同時也存有一些問題。比如，K-Means是EM算法求解過程，計算的結(jié)果是一個局部最優(yōu)的結(jié)果，所以這就導(dǎo)致最終的效果會受到初始質(zhì)心的影響。其次，K值的選取也會影響聚類的效果。最優(yōu)的K值應(yīng)該是吻合數(shù)據(jù)本身的結(jié)構(gòu)，但是這個非常難掌握，因此K值的選擇也是一個較大的挑戰(zhàn)。除了以上的問題，當數(shù)據(jù)量很大的時候，K-Means的計算時間也非常大。

2.3.2 層次聚類算法

層次聚類是聚類算法中常見的算法。層次聚類通過計算不同類別之間的相似性來創(chuàng)建一棵有層次的聚類樹。在樹的結(jié)構(gòu)中，未聚類的原始數(shù)據(jù)是樹的底層數(shù)據(jù)，樹的頂層是一個樹的聚類根節(jié)點。層次聚類有兩種方式，一種是自下而上的合并，另一種是自上而下的分裂。

層次聚類的合并方式是通過計算兩個數(shù)據(jù)之前的相似性，將所有數(shù)據(jù)中最相似的兩個數(shù)據(jù)點進行組合，并不斷迭代這個過程，直到所有的點聚類結(jié)束。一般計算層次聚類的合并算法是通過衡量每一個類別的數(shù)據(jù)點與其他點的距離來反映它們的相似性，距離越小表示越相似。

層次聚類的分裂方式則與之前的合并思路完全相反。首先會將所有的點看成一個類，然后找出距離最遠的兩個，然后分配到不同的類中，接著計算其它數(shù)據(jù)與它們的距離，然后分配到距離近的一類。反復(fù)迭代，直到達到設(shè)定的條件。

3 算法介紹

我們提出了一種不同傳統(tǒng)社團檢測的方法，而是用圖嵌入的方式表示網(wǎng)絡(luò)，并使用機器學(xué)習(xí)的聚類算法來進行社團檢測。

基于DeepWalk的社團檢測方法如下：

首先我們使用DeepWalk得到節(jié)點的向量形式：輸入網(wǎng)絡(luò)結(jié)構(gòu)，對網(wǎng)絡(luò)中的每一個節(jié)點生成γ個隨機游走，每個隨機游走過程均勻抽樣網(wǎng)絡(luò)中的一個點為游走的根節(jié)點，然后每次從當前節(jié)點均勻地選取鄰居節(jié)點為下一個節(jié)點，循環(huán)以上步驟，直到游走路徑長度達到規(guī)定長度。

接下來用SkipGram模型進行訓(xùn)練，得到每個點的點的詞向量。

最后我們使用傳統(tǒng)的機器學(xué)習(xí)聚類算法（如K-Means或者是層次聚類）得到網(wǎng)絡(luò)的聚類結(jié)果。

4 實驗結(jié)果與分析

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

在本次實驗中，我們使用兩個具有真實社團背景的網(wǎng)絡(luò)作為實驗數(shù)據(jù)：1）Zacharys karate club[12]， 2） Books about US politics[13]

所以F定義：

4.3 實驗結(jié)果

實驗中我們分別選用K-means和層次聚類作為聚類方法，并與Asynchronous Fluid Communities algorithm[14]對比。

通過實驗結(jié)果表明，通過基于DeepWalk的社團檢測方法可以取得一個不錯的效果，從而證明了該算法的可行性。

5 結(jié)束語

本文基于圖嵌入方法提出了一種基于DeepWalk的社團檢測方法。該算法將網(wǎng)絡(luò)通過DeepWalk的方式，將網(wǎng)絡(luò)中的節(jié)點映射到了歐氏空間中，并且通過傳統(tǒng)機器學(xué)習(xí)的聚類方法進行聚類，最終得到社團結(jié)果。最后，我們在有真實社團標簽的網(wǎng)絡(luò)進行社團檢測，通過實驗結(jié)果，可以證明我們算法的有效性與可行性。通過這種方式，我們將復(fù)雜網(wǎng)絡(luò)的社團檢測問題轉(zhuǎn)化為機器學(xué)習(xí)的聚類問題，從而可以使用聚類算法解決社團檢測。

參考文獻：

[1] 汪小帆，李翔，陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論[M].2012.

[2] Onta?ón S， Plaza E. Case-based Learning from Proactive Communication[C]//IJCAI. 2007（7）：999-1004.

[3] Kirkby R， Frank E， Reutemann P. Weka explorer user guide for version 3-5-8[J]. University of Waikato， 2007.

[4] Parameter setting in evolutionary algorithms[M]. Springer Science & Business Media， 2007.

[5] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical review E， 2006， 74（3）：036104.

[6] 鄧小龍，王柏，吳斌，楊勝琦.基于信息熵的復(fù)雜網(wǎng)絡(luò)社團劃分建模和驗證[M].計算機研究與發(fā)展， 2012.

[7] Shiga M， Takigawa I， Mamitsuka H. A spectral clustering approach to optimally combining numericalvectors with a modular network[C]//Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2007： 647-656.

[8] Rosvall M， Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks[J]. Proceedings of the National Academy of Sciences， 2007， 104（18）：7327-7331.

[9] Pons P， Latapy M. Computing communities in large networks using random walks[C].//ISCIS， 2005（3733）：284-293.

[10] Fortunato S， Latora V， Marchiori M. Method to find community structures Based on information centrality[J]. Physical review E， 2004， 70（5）：056104.

[11] Perozzi B， Al-Rfou R， Skiena S. Deepwalk： Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2014： 701-710.

[12] W. W. Zachary， An information flow model for conflict and fission in small groups， Journal of Anthropological Research 1977（33）：452-473.

[13] V. Krebs， unpublished，http：//www.orgnet.com/.

[14] Parés F， Garcia-Gasulla D， Vilalta A， et al. Fluid Communities： A Competitive and Highly Scalable Community Detection Algorithm[J].2017.