DeepWalk的输入是一张图或者网络，输出为网络中顶点的向量表示。DeepWalk通过截断随机游走(truncated random walk)学习出一个网络的社会表示(social representation)
image.png
前提假设
随机游走的分布规律与NLP中句子序列在语料库中出现的规律有着类似的幂律分布特征。那么既然网络的特性与自然语言处理中的特性十分类似，那么就可以将NLP中词向量的模型用在网络表示中。
image.png
优化目标
image.png
image.png
image.png
- 映射函数选取
image.png
忽视顶点顺序，更好地表达顶点临近关系，只需要计算一个顶点的向量。
skip-gram
image.png
Hierarchical Softmax解决迭代计算量庞大的问题。
Huffman编码是一种熵编码方式，对于出现频率高的符号用较短的编码表示，出现频率较低的符号用较长的编码表示，从而达到编码压缩的目的。Hierarchical Softmax树也可以采用Huffman编码的方式生成，高频词用较短的路径到达，低频词用较长的路径到达，可以进一步降低整个训练过程的计算量。
image.png
伪代码
image.png
截断随机游走
image.png
随机游走长度固定。根结点vi，随机路径Wvi。
注意的点
-
适应性，网络表示必须能适应网络的变化。
网络是一个动态的图，不断地会有新的节点和边添加进来，网络表示需要适应网络的正常演化。 - 属于同一个社区的节点有着类似的表示。网络中往往会出现一些特征相似的点构成的团状结构，这些节点表示成向量后必须相似。
-
低维。
代表每个顶点的向量维数不能过高，过高会有过拟合的风险，对网络中有缺失数据的情况处理能力较差。 -
连续性。
低维的向量应该是连续的。
参考
w2v: https://www.jianshu.com/p/3217e8c00549
文献：https://arxiv.org/pdf/1403.6652.pdf
https://zhuanlan.zhihu.com/p/45167021
slide：http://www.perozzi.net/publications/14_kdd_deepwalk-slides.pdf
