Node2Vec随机游走策略

可视化演示

展示决策树构建中的信息熵计算、信息增益比较和最优分裂选择过程，动态演示ID3算法的核心决策逻辑。

1. 图嵌入动机：把街区浓缩成一张名片

你是城市规划师，要给整座城市做旅游手册。街区太多，不能把每一条街道都写进去，你只能把每个街区浓缩成一张名片：位置、氛围、人气、和谁相邻。图嵌入也想做同样的事——把图中每个节点压缩成一串数字向量，让这串数字尽可能表达它在网络里的“社交位置”。

传统做法给节点做 one-hot 编号，就像给街区贴一个孤立序号，看不出街区之间的任何关系。图嵌入追求的是“向量距离近，节点关系近”。这样，分类、聚类、推荐等下游任务就能直接吃这些向量，而不必手工设计复杂特征。

技术上，Node2Vec 先定义了一个从节点到向量的映射函数，把节点投影到低维空间：

一张名片虽小，却能浓缩街区的“人脉圈”，这也是图嵌入的意义：牺牲细节，换回可以被计算的结构信息。

2. 随机游走基础：用游客脚印收集城市故事

名片不能凭空捏造，需要素材。于是你派出许多游客，让他们在城市里随机穿行，每走一步就记下一个节点。这些脚印连起来，就形成一条“节点序列”，如同自然语言处理里的句子，节点是词，序列是句子。

有了句子，就能借用 Word2Vec 的思路：用滑动窗口截取“上下文”，让出现在同一窗口里的节点互相学习。若两个节点经常被同一条游走路线带到一起，它们的向量就会变得相似。

一条随机游走序列可以写成：

游客脚印越丰富，模型看到的“句子”就越多，学出的街区名片也越准确。

3. 二阶马尔可夫：记住来路才有方向感

如果游客每到一个岔路口都完全失忆，只凭当前街区做决定，那么路线会非常混乱。现实中有方向感的游客会回头看看：我从哪条街来的？上一条街和我当前位置的关系是什么？Node2Vec 也引入了这份“来路记忆”，让游走不仅看当前节点，还看上一跳节点。

这就是二阶马尔可夫性：决策时既考虑现在，也考虑刚刚走过的路。它帮助模型区分“折返”和“前行”，从而产生更丰富的结构信号。

下一步选择候选节点 x 的概率可以写成：

记住来路，游客才不会像无头苍蝇；这正是 Node2Vec 比朴素随机游走更“懂结构”的原因。

4. p与q参数：给游客装上性格旋钮

同样是逛城市，有人喜欢在刚离开的小巷里反复折返，好像要确认每个细节；有人则喜欢大步流星冲向新的远方。Node2Vec 用两个旋钮模拟这两种性格：p 控制“回头”的冲动，q 控制“远走”的欲望。

当从前一个节点 t 走到当前节点 v，再决定下一步 x 时，算法根据 x 与 t 的距离给边权施加一个调整系数。距离为 0 表示回到 t，距离为 1 表示 x 与 t 直接相连，距离为 2 表示 x 离 t 有两跳，属于“更远的选择”。

这个调整系数写出来是：

两个旋钮一左一右，决定了游客是在熟悉的街区反复巡逻，还是沿着大道一路探索远方。

5. 归一化转移：把吸引力变成真实概率

岔路口的“吸引力分数”不能直接用。比如一个路口有五条路，吸引力分别是 2、1、1、1、1，游客并不会把 2 当成概率，而要先算总吸引力，再计算每条路所占比例。归一化就是把各项权重除以总和，让它们加在一起等于 1。

在 Node2Vec 中，非归一化概率 π 要除以当前节点所有邻居的非归一化概率之和，才能得到真正的转移概率：

只有做完归一化，游客的选择才符合概率规律，采样才不会偏向某个路口。

6. DeepWalk对比：从无差别乱逛到偏好漫游

在 Node2Vec 出现之前，DeepWalk 已经用随机游走做过图嵌入。但 DeepWalk 的游客没有性格：每到一个路口，所有邻居被选中的概率完全一样，只管往前走，不回头也不探险。

Node2Vec 把它升级为带偏置的游走，用 p、q 两个旋钮重新分配岔路口的吸引力。事实上，当 p=1、q=1 时，Node2Vec 就退化成 DeepWalk：

DeepWalk 像“无差别乱逛”，Node2Vec 则是“带剧本的漫游”。后者能根据任务需要捕捉局部社群或全局骨架，表达力自然更强。

7. 调参经验：游走次数和长度决定素材质量

拍一部城市纪录片，如果只派一个游客出门十分钟，素材肯定不够；如果派太多游客走太远，又会拍到大量重复场景。Node2Vec 的调参也类似，核心是三个量：游走次数、游走长度、窗口大小。

游走次数 r 决定总共采集多少条序列，游走长度 l 决定每条序列走多长，窗口大小 k 决定模型用多宽的上下文学习。三者共同决定了喂给 Word2Vec 的样本总规模：

实际经验中，p、q 通常设为 0.25 到 4 之间的值，r 和 l 则根据图规模调整。素材太少学不准确，素材太多训练变慢，平衡才是关键。

8. 评估可视化：旅行日记能否还原城市地图

训练完向量，怎么知道游客的旅行日记有没有真正抓住街区关系？一个朴素的想法是：把学到的向量拿去做相似度计算，看关系近的街区向量是否也更近。另一个思路是把向量喂给下游分类任务，看准确率如何。

最常用的相似度指标是余弦相似度——它只看两个向量的方向是否一致，不受向量长度影响：

除了相似度，还可以把向量降维后画在二维平面上，肉眼观察社区是否聚在一起。旅行日记写得越准，这座城市的社交版图就越清晰。

AI 应用场景

Python 演示

import randomfrom collections import defaultdict class BiasedRandomWalk:    def __init__(self, adj_list, p, q, walk_length):        self.adj_list = adj_list        self.p = p        self.q = q        self.walk_length = walk_length     def _alpha(self, prev, cur, nxt):        if prev is None or nxt == prev:            return 1.0 / self.p        if nxt in self.adj_list[prev]:            return 1.0        return 1.0 / self.q     def _transition(self, prev, cur):        weights = []        for nxt in self.adj_list[cur]:            weights.append(self._alpha(prev, cur, nxt))        return random.choices(self.adj_list[cur], weights=weights, k=1)[0]     def walk(self, start):        path = [start]        prev = None        cur = start        while len(path) < self.walk_length:            nxt = self._transition(prev, cur)            prev, cur = cur, nxt            path.append(nxt)        return path def main():    adj_list = {        0: [1, 2],        1: [0, 2, 3],        2: [0, 1, 4],        3: [1, 4, 5],        4: [2, 3, 5],        5: [3, 4],    }    walker = BiasedRandomWalk(adj_list, p=0.5, q=2.0, walk_length=6)    for _ in range(3):        print(walker.walk(0)) if __name__ == "__main__":    main()

1. class BiasedRandomWalk:定义带偏置游走器，相当于给游客装上了 p、q 两个偏好旋钮。
2. def _alpha(self, prev, cur, nxt):根据上一跳、当前节点和候选节点计算非归一化调整系数。
3. return 1.0 / self.p候选点是上一跳节点时，回退系数由 p 控制。
4. if nxt in self.adj_list[prev]:候选点与上一跳直接相连，系数保持 1。
5. return random.choices(self.adj_list[cur], weights=weights, k=1)[0]按归一化后的权重采样下一步。
6. walker = BiasedRandomWalk(adj_list, p=0.5, q=2.0, walk_length=6)p 小 q 大的配置让游走偏向局部区域。

常见误区

面试题