DeepWalk（深度游走）算法

整理自：

Deepwalk(深度游走)算法简介_Mr.Cheng1996的博客-CSDN博客

DeepWalk是一种将随机游走(random walk)和word2vec两种算法相结合的图结构数据挖掘算法。该算法能够学习网络的隐藏信息，能够将图中的节点表示为一个包含潜在信息的向量，如图1-2所示。

Deepwalk算法

该算法主要分为随机游走和生成表示向量两个部分。首先利用随机游走算法(Random walk)从图中提取一些顶点序列；然后借助自然语言处理的思路，将生成的顶点序列看作由单词组成的句子，所有的序列可以看作一个大的语料库(corpus)，最后利用自然语言处理工具word2vec将每一个顶点表示为一个维度为d的向量。

符号定义：一个图可以表示为：
G = ( V , E )
其中，V 表示顶点的集合；E表示边的集合, 且 E ⊆ V × V 。

如果在图G的基础上再加上顶点的向量表示和顶点所属的标注（网络节点分类问题中，网络中的每个顶点都有一个类别，所属的类别即为该顶点的标注）就构成了一个标注图(labeled graph)。顶点的表示X是一个|V|×s维的矩阵，|V|表示顶点的数量，s是代表每个顶点的向量的维数（一般比较小），所以X即为将每个顶点的向量结合在一起形成的矩阵。Y则是每个顶点的标注构成的矩阵。

文中提到，在学习一个网络表示的时候需要注意的几个性质：

适应性，网络表示必须能适应网络的变化。网络是一个动态的图，不断地会有新的节点和边添加进来，网络表示需要适应网络的正常演化。
属于同一个社区的节点有着类似的表示。网络中往往会出现一些特征相似的点构成的团状结构，这些节点表示成向量后必须相似。
低维。代表每个顶点的向量维数不能过高，过高会有过拟合的风险，对网络中有缺失数据的情况处理能力较差。
连续性。低维的向量应该是连续的。

提到网络嵌入，可能会让人联想到NLP中的word2vec，也就是词嵌入(word embedding)。前者是将网络中的节点用向量表示，后者是将单词用向量表示。因为大多数机器学习的方法的输入往往都是一个向量，算法也都基于对向量的处理，从而将不能直接处理的东西转化成向量表示，这样就能利用机器学习的方法对其分析，这是一种很自然的思想。

本文处理网络节点的表示(node representation)就是利用了词嵌入（词向量）的的思想。词嵌入的基本处理元素是单词，对应网络网络节点的表示的处理元素是网络节点；词嵌入是对构成一个句子中单词序列进行分析，那么网络节点的表示中节点构成的序列就是随机游走。

所谓随机游走(random walk)，就是在网络上不断重复地随机选择游走路径，最终形成一条贯穿网络的路径。从某个特定的端点开始，游走的每一步都从与当前节点相连的边中随机选择一条，沿着选定的边移动到下一个顶点，不断重复这个过程。下图所示绿色部分即为一条随机游走。

使用随机游走有两个好处：

并行化，随机游走是局部的，对于一个大的网络来说，可以同时在不同的顶点开始进行一定长度的随机游走，多个随机游走同时进行，可以减少采样的时间。
适应性，可以适应网络局部的变化。网络的演化通常是局部的点和边的变化，这样的变化只会对部分随机游走路径产生影响，因此在网络的演化过程中不需要每一次都重新计算整个网络的随机游走。

文中提到网络中随机游走的分布规律与NLP中句子序列在语料库中出现的规律有着类似的幂律分布特征。那么既然网络的特性与自然语言处理中的特性十分类似，那么就可以将NLP中词向量的模型用在网络表示中，这正是本文所做的工作。