1. 概述
DeepWalk算法是在KDD2014中提出的算法，最初应用在图表示（Graph Embedding）方向，由于在推荐系统中，用户的行为数据固然的可以表示成图的形式，因此DeepWalk算法也常被用于推荐系统中的item embedding的计算。Graph Embedding使用低维稠密向量的形式表示途中的节点，使得在原始图中相似（不同的方法对相似的定义不同）的节点其在低维表达空间也接近。
2. 算法思想
DeepWalk算法借鉴了word2vec算法的思想，word2vec是NLP中一种常用的word embedding方法，word2vec通过语料库中的句子序列来描述词与词的共现关系，进而学习到词语的向量表示。DeepWalk算法与word2vec类似，使用图中节点与节点的共现关系来学习节点的向量表示。在DeepWalk中通过使用随机游走(RandomWalk)的方式在图中进行节点采样来模拟语料库中的预料，进而使用word2vec的方式学习出节点的共现关系。
2.1. RandomWalk
RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件，其算法思想如下所示：
其代码大致如下：
代码语言：javascript复制def deep_worker(self):
for _ in range(self.nums):
for node in self.G.nodes():
self.node_series.append(self.random_walker(node))
def random_walker(self, first_node):
series = [first_node]
for _ in range(1, self.walk_length):
nodes_list = list(self.G.adj[first_node])
first_node = random.choice(nodes_list)
series.append(first_node)
return series2.2. word2vec
word2vec的基本原理不再在本文中详细给出，可以参阅其他的一些材料，Python下可以通过gensim里的Word2Vec实践：
代码语言：javascript复制from gensim.models import Word2Vec
w2v_model = Word2Vec(walks,sg=1,hs=1)参考文献
- Perozzi B, Alrfou R, Skiena S. DeepWalk: online learning of social representations[J]. 2014:701-710.
- DeepWalk源码
- 《DeepWalk: Online Learning of Social Representations》笔记
- C实现的DeepWalk
