node2vec

首先是两种图的游走方式，深度优先游走（DFS）、广度优先游走（BFS）
BFS倾向于在初始节点的周围游走，可以反映出一个节点的邻居的微观特性；而DFS一般会跑的离初始节点越来越远，可以反映出一个节点邻居的宏观特性

本文引入了两个参数来控制随机游走产生的方式

image.png

上图中，对于一个随机游走，如果已经采样了（t,v），也就是说现在停留在节点v上，那么下一个要采样的节点x是哪个呢？
定义了一个概率分布，也就是一个节点到它的不同邻居的转移概率：

image.png
直观解释一下这个分布：
1、如果t和x相等，那么采样x的概率为1/p；

2、如果t和x相连，那么采样x的概率为1；
3、如果t和x不相连，那么采样x的概率为1/q；
参数p和q的意义分别如下：
返回概率p：
如果p>max(q,1)，那么采样会尽量不往回走，对应上图的情况，就是下一个节点不太可能是上一个访问的节点t；
如果p<max(q,1)，那么采样会倾向于返回上一个节点，这样就会一直在起始点周围某些节点来回转来转去；
出入参数q：
如果q>1，那么游走会倾向于在起始点周围的节点之间跑，可以反映出一个节点的BFS特性；
如果q<1，那么游走会倾向于往远处跑，反映出DFS特性

其实DeepWalk是根据边的权重进行随机游走，而node2vec加了一个权重调整参数，t是上一个节点，v是最新节点，x是候选下一个节点，d(t,x)是t到候选节点的最小跳数
通过不同的p和q参数设置，来达到保留不同信息的目的
当p=1，q=1时，游走方式就等同于DeepWalk中的随机游走