基于DeepWalk的社团检测方法

彭欣宇

摘要：该文提出一种基于DeepWalk的网络社团检测方法。该算法的基本思想是基于图嵌入的DeepWalk方法，利用网络随机游走的方式，把网络结构映射到欧氏空间中，然后利用经典机器学习聚类算法进行聚类，从而得到社团。该文在具有社团标签的网络中进行实验，从实验中验证了这种思想的可行性，取得了显著的效果。

关键词：DeepWalk；社团检测；聚类

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）04-0168-02

1 概述

伴随着网络技术和计算机科学的技术高速发展，尤其是智能手机兴起与快速普及，使人类已经步入了一个全新的网络时代。在人们生活的方方面面，随处可见复杂网络的身影，如科学家之间的合作网络，国家电力网络，电信通讯网络等等。因此，近几年，复杂网络的研究价值和应用价值越来越受到学术界和工业界的认可与重视。

随着对网络拓扑性质的深入研究，人们发现在许多的网络结构中都能挖掘出一种共同的性质：社团结构。这种结构在我们生活中也随处可见，比如在社交关系中，如果来自同一个学校或者公司，那么这群人的连接也会比来自其他学校或者公司的一群人联系更加紧密。社团结构与计算机科学中的图分割和社会学中的分级聚类有着密不可分的关系。[1]分级聚类是基于各个节点连接的相似性或强度将网络划分各个子群，且根据划分时往网络中添加还是移除边可分为凝聚算法和分裂算法两类，其中应用非常广泛的是Girvan和Newman提出的基于边介数的分裂算法[2]和Breiger等人提出的Concor算法[3]；图形分割最有名的算法是Kernighan-lin算法[4]和谱方法法[5]。

本文不同于之前的算法研究，提出一种基于DeepWalk的方法进行社团检测，将网络映射到欧氏空间中，然后利用机器学习的聚类方法进行聚类得到社团。

本文首先介绍deepwalk和机器学习中常见的聚类算法，并通过实验来验证本文提出算法的可行性，最后是本文结论。

2 相关研究

2.1 社团检测算法

网络的社团结构具有同一社团内部节点连接紧密，不同的社团节点连接稀疏[5]的属性，而社团检测方法旨在揭示出网络中真实存在的社团结构。社团检测通常使用Newman提出的Modularity[5]来衡量算法的，Modularity（常用Q表示）通常定义为：

其中，表示网络社团个数，表示网络连接总数，表示社团内连接总数，表示社团内节点度之和。

近年来随着复杂网络社团检测的研究发展，社团检测算法大致可以分为以下三类[6]：1）基于优化的划分方法，主要分为谱方法[5，7]和局部搜索方法。2）启发式方法。如最大流社团算法[8]、Newman算法（grivan newman，GN）等。3）其他划分方法。如基于随机游走的相似度算法[9]和节点聚类中心度算法[10]等。

2.2 DeepWalk

我们传统表示网络是基于图挽留表示方式。比如我们可以用一个G=（V，E）来定义一个网络，V是网络中的节点集合，E是网络中的边集合。我们用不同的符号命名不同的节点，用二维数组或者邻接矩阵来存储网络的连边情况。当我们使用邻接矩阵记录网络拓扑的时候就可以利用线性代数的一些概念去解决网络中的一些问题。但是缺点也很明显，如果网络是一个稀疏的网络，那么会浪费大量的存储空间。

所以现在提出一种网络表示学习（Network Representation Learning， NRL），也称图嵌入法（Graph Embedding Method， GEM）的方式来表达网络。这种方法的思想是用一种向量表示网络中的节点。

DeepWalk[11]借用了NLP的方法，利用SkipGram的方法进行网络中节点的表示学习。按照SkipGram的思路，我们需要解决的就是如果定义“文本内容”，也就是“邻居”。在自然语言处理里面，单词的邻居就是周围的单词，而在DeepWalk是用随机游走的序列来作为网络节点的邻居。

具体步骤：首先随机游走随机均匀地选取网络节点，并生成固定长度的游走序列。这个游走序列就相当于自然语言中的句子，节点的序列是句子，而序列中的节点就是句子中的单词，然后将这个生成的序列放入SkipGram进行训练得到模型。

2.3 聚类算法

聚类分析也叫群分析，其主要研究分类问题的一种基于统计分析方法，在数据挖掘中也有重要的应用。

聚类算法主要思想是依据某种特定的标准（比如数据之间的距离）把一个数据集划分为不同的类或者簇，使内部的数据具有较高的相似性，而不同簇的数据之间差异较大。较通俗的解释就是让相似的数据尽可以聚集在一起，不同的数据相距更远，从而可以清晰划分数据的类。常见的算法有K-Means和层次聚类等

2.3.1 K-Means聚类算法

K-Means是经典的聚类算法，K为事先确定的常数，常数K也同时意味着数据最终的类别数量。首先随机选取K个类的质心，计算每个数据与质心的距离，将每个数据分到最近的质心类，然后重新计算每个类的质心，重复以上过程，直至质心不再改变，最终确定每个类的成员数据。

K-Means算法思想簡单，易于实现，但是同时也存有一些问题。比如，K-Means是EM算法求解过程，计算的结果是一个局部最优的结果，所以这就导致最终的效果会受到初始质心的影响。其次，K值的选取也会影响聚类的效果。最优的K值应该是吻合数据本身的结构，但是这个非常难掌握，因此K值的选择也是一个较大的挑战。除了以上的问题，当数据量很大的时候，K-Means的计算时间也非常大。

2.3.2 层次聚类算法

层次聚类是聚类算法中常见的算法。层次聚类通过计算不同类别之间的相似性来创建一棵有层次的聚类树。在树的结构中，未聚类的原始数据是树的底层数据，树的顶层是一个树的聚类根节点。层次聚类有两种方式，一种是自下而上的合并，另一种是自上而下的分裂。

層次聚类的合并方式是通过计算两个数据之前的相似性，将所有数据中最相似的两个数据点进行组合，并不断迭代这个过程，直到所有的点聚类结束。一般计算层次聚类的合并算法是通过衡量每一个类别的数据点与其他点的距离来反映它们的相似性，距离越小表示越相似。

层次聚类的分裂方式则与之前的合并思路完全相反。首先会将所有的点看成一个类，然后找出距离最远的两个，然后分配到不同的类中，接着计算其它数据与它们的距离，然后分配到距离近的一类。反复迭代，直到达到设定的条件。

3 算法介绍

我们提出了一种不同传统社团检测的方法，而是用图嵌入的方式表示网络，并使用机器学习的聚类算法来进行社团检测。

基于DeepWalk的社团检测方法如下：

首先我们使用DeepWalk得到节点的向量形式：输入网络结构，对网络中的每一个节点生成γ个随机游走，每个随机游走过程均匀抽样网络中的一个点为游走的根节点，然后每次从当前节点均匀地选取邻居节点为下一个节点，循环以上步骤，直到游走路径长度达到规定长度。

接下来用SkipGram模型进行训练，得到每个点的点的词向量。

最后我们使用传统的机器学习聚类算法（如K-Means或者是层次聚类）得到网络的聚类结果。

4 实验结果与分析

4.1 实验数据

在本次实验中，我们使用两个具有真实社团背景的网络作为实验数据：1）Zacharys karate club[12]， 2） Books about US politics[13]

所以F定义：

4.3 实验结果

实验中我们分别选用K-means和层次聚类作为聚类方法，并与Asynchronous Fluid Communities algorithm[14]对比。

通过实验结果表明，通过基于DeepWalk的社团检测方法可以取得一个不错的效果，从而证明了该算法的可行性。

5 结束语

本文基于图嵌入方法提出了一种基于DeepWalk的社团检测方法。该算法将网络通过DeepWalk的方式，将网络中的节点映射到了欧氏空间中，并且通过传统机器学习的聚类方法进行聚类，最终得到社团结果。最后，我们在有真实社团标签的网络进行社团检测，通过实验结果，可以证明我们算法的有效性与可行性。通过这种方式，我们将复杂网络的社团检测问题转化为机器学习的聚类问题，从而可以使用聚类算法解决社团检测。

参考文献：

[1] 汪小帆，李翔，陈关荣.网络科学导论[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] 邓小龙，王柏，吴斌，杨胜琦.基于信息熵的复杂网络社团划分建模和验证[M].计算机研究与发展， 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.