在自然语言处理、文本挖掘中，常常使用词向量作为单词（Word）内在含义的表达，从传统的向量表达到近几年的词嵌入（Word Embedding）表达，词向量已经作为一种文本的常用特征得到广泛应用。类似的，一些研究者希望通过网络结构中的连接关系，得到网络中顶点（vertex）的向量表示，作为基本特征应用到聚类、分类等任务上。

Deepwalk

Deepwalk来源于《DeepWalk: Online Learning of Social Representations》这篇论文，它的思想非常简单，主要借鉴了word2vec，将网络结构通过Random walk的方式，转换为类似“sentence”的节点序列的形式。Word2Vec是Mikolov带领Google研发的用来产生词嵌入表达的模型，其中又包括skip-grams 或continuous-bag-of-words（CBOW）两种方式。

在deepwalk的这篇论文中，为了说明网络结构中的节点和文本中的词具有可比性，作者根据对社交网络的图和Wikipedia中的文本进行分别统计，发现都遵循zipf’s定律，说明词和经过Random walk后图的节点，具有相似的特性。如下图所示：

将网络结构转化为“sentence”序列后，以通过word2vec中的Skip-gram模型或者CBOW模型，训练得到每个节点的向量表示形式，进而可以用余弦距离或者欧式距离来求得两个节点之间的相似度。这篇论文采用了Skip-gram模型。

Deepwalk算法描述，见下图。对图G，随机采样1个节点v，然后以此为起点连续采样，直到达到最大路径长度t，再通过Skip-gram来更新参数。

Deepwalk实现很简单，在网络结构上主要考虑节点间是否存在连接的边，但是效果稳定，在评测数据上取得了很不错的效果，且代码健壮。在应用上deepwalk支持directed/undirected网络，原始代码不支持带权重的网络结构。