node2vec

node2vec 在DeepWalk 的基础上引入了网络的同质性(homophily)和结构性(structural equivalence)的概念。

同质性指节点同属于某一个社区，在下图中u和s1同属于一个社区。 结构性指节点的结构角色类似，如下图中s6与u虽然属于两个不同的社区，但是他们都属于中心节点，结构类似。

                                          

 

从BFS和DFS的角度来看，BFS反映了结构性，局限于搜索近邻点，BFS可得到节点的邻点微观视角； DFS反映了同质性，DFS可以探索网络更大的区域，更好地反应邻点的宏观视角（对社区发现很重要）。

 

node2vec 通过节点间的跳转概率来混合BFS和DFS。定义一个2阶的带有参数p和q的random walk 。考虑如下图的一个刚刚遍历了边(t,v)​, 停留在节点​ 的random walk。

                                              

对于下一步从的转移概率\pi_{v x}​(从v出发，得到的边vx)：

                                                              \pi_{v x}=\alpha_{p q}(t, x) \cdot w_{v x}

其中​为边的权重， \alpha_{p q}(t, x)的定义如下式, 其中​为节点t和x之间的最短距离，必须取值为{0,1,2}

 

                                                           \alpha_{p q}(t, x)=\left\{\begin{array}{ll}{\frac{1}{p}} & {\text { if } d_{t x}=0} \\ {1} & {\text { if } d_{t x}=1} \\ {\frac{1}{q}} & {\text { if } d_{t x}=2}\end{array}\right.

上式中，参数p被称为返回参数（return parameter），p越小，随机游走回节点t的可能性越大，node2vec就更注重表达网络的结构性。p越大时，鼓励适当的探索，避免2-hop跳转的冗余

参数q被称为进出参数（in-out parameter），q>1 时， node2vec 类似BFS， 更注重表达网络的结构性， q<1时，则随机游走到远方节点的可能性越大，类似DFS，node2vec更注重表达网络的同质性。

 

关于实现

作者给出的python参考代码中（论文中也提到了这一点，使用之后，时间复杂度为O(1))，跳转到相邻节点的概率采样，使用了一种叫alias sampling的近似采样方法

 

参考

  1. https://arxiv.org/pdf/1607.00653.pdf

  2. github

  3. 深度学习中不得不学的Graph Embedding方法

  4. 关于Node2vec算法中Graph Embedding同质性和结构性的进一步探讨

版权声明：本文为beingstrong原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/beingstrong/article/details/97689454