DeepWalk

论文出处：https://arxiv.org/pdf/1403.6652.pdf

算法：

DeepWalk的思想是：对于图中的每个结点，我们都要以它为起点生成 γ \gammaγ 个具有最大长度的随机游走序列，最终会得到 ∣ V ∣ ⋅ γ |V|\cdot \gamma∣V∣⋅γ 个序列。将每一个序列看成一个句子，将其中的结点看成单词，于是我们可以对这些序列应用 Word2Vec（Skip-Gram + Hierachical Softmax） 得到结点的嵌入表示。

在上图中，w ww 是窗口大小，即在 Skip-Gram 模型中，用中心词预测 2 w 2w2w 个上下文词；d dd 是结点向量的维度；γ \gammaγ 决定了对于图中的每一个结点，我们要以它为起点生成多少个随机游走序列；t tt 是随机游走序列的最大长度。

简单实现

以无向图为例，假设结点都用整型数字标识，相应实现如下

import random
from gensim.models import Word2Vec


def random_walk(graph, root, walk_length):
	# graph为networkx中的无向图类型，root为整型
	# 该函数每次只生成一个随机游走序列
    seq = [root]
    for _ in range(walk_length - 1):
        seq.append(random.choice(list(graph.neighbors(seq[-1]))))
    return seq


def deep_walk(graph, windows_size, embed_size, gamma, walk_length):
    seqs = [random_walk(graph, node, walk_length) for node in graph.nodes for _ in range(gamma)]
    model = Word2Vec(seqs, vector_size=embed_size, window=windows_size, sg=1, hs=1)
    return model.wv

Node2Vec

论文出处：https://arxiv.org/pdf/1607.00653.pdf

DeepWalk 实际上就是把 Word2Vec 用在了图上，Node2Vec 在 DeepWalk 的基础上进行了改进，把完全随机游走（假设一个结点有 N NN 个邻居结点，则下一步到每个邻居结点的概率都为 1 / N 1/N1/N）改成了有偏随机游走（下一步到每个邻居结点的概率不同）。

如下图，Node2Vec 使用的是二阶随机游走，即下一步往哪里走不仅取决于当前结点，还取决于上一结点：

算法：

通过伪代码可以看出，该算法与 DeepWalk 的主要区别在于结点的采样策略。因为 DeepWalk 是完全随机游走，所以每次只需要从邻居结点中随机选取一个就OK了，而 Node2Vec 是有偏随机游走，所以需要用到 Alias Sampling 技术，它的时间复杂度是 O ( 1 ) O(1)O(1)（空间换时间）。

有关 Alias Sampling 可参考：https://www.keithschwarz.com/darts-dice-coins/。

简单实现

目前有现成的第三方库（基于NetworkX和Gensim），项目地址：https://github.com/eliorc/node2vec。

from node2vec import Node2Vec

G = nx.les_miserables_graph()
model = Node2Vec(G, dimensions=32, walk_length=3, num_walks=600, p=2, q=0.5, workers=4).fit(window=3,
                                                                                            min_count=1,
                                                                                            batch_words=4)