前面写的1、Deepwalk和Node2vec等图算法的本质是特征提取器，对graph进行采样，对采样序列建立模型，最终将节点转化为特征向量，这就是嵌入式。
2、图形算法的优越性
graph是将复杂的连接关系模型化，通过用户的行动系列可以更好地学习的items的高次相似关系。
同时，在构建数据集的过程中，可以让长尾产品接受更多的训练，弥补数据稀疏问题，有效提高覆盖率。
一. Deepwalk 1，来源： 14年KDD: 《DeepWalk: Online Learning of Social Representations》
2、思想： Deepwalk的主要思想是在物品组成的图结构上随机游走，生成大量的物品序列，将这些物品序列作为训练样本输入word2vec进行训练，得到物品的嵌入式训练。
RandomWalk是一种深度优先扫描算法，可重复访问所访问的节点。 指定当前接入开始节点，从相邻的随机采样节点作为下一个接入节点，重复该过程，直到接入序列长度满足预设条件。
3、图标：
4、算法流程4步：
)图a表示原始的用户行动系列)图b基于这些用户行动系列构筑物品相关图，物品a、b之间产生边缘的理由是由于用户U1相继购买了物品a和物品b，从而产生了从a到b的有向边缘之后，如果生成多个相同的有向边，有向边的权重就会被强化。 将所有用户的行为序列转换为物品关联图中的边后(在原deepwalk paper中没有权重，是randomWalk ) )得到全局物品关联图。 )图c以随机行走方式随机选择起点，在每个节点上重新生成一部分物品列(样本)。 得到局部相关的训练数据，deepwalk将这一系列看作语言模型的一个短语，在给定某个短语的中心词时，使上下文单词出现的概率最大化。 )图d最终将这些物品列输入word2vec模型，生成最终的物品Embedding向量。 5、deepwalk的跳跃概率
定义到达节点vi后，下一个遍历vi的临接点vj的概率。 跳跃概率与跳跃节点的边出权重成正相关(跳跃概率=当前边出权重/所有边出权重之和)。
6、随机游走生成所有单词串
在语言模型的框架中，以给出游走的所有节点为前提，接下来游走/访问的节点有可能是v_i :
假设有以下映射函数，得到节点的潜在表示(即后面得到的embedding，即被提取的节点的特征)。
利用神经概率语言模型建模知识，deepWalk中节点单词表示的概率建模方法归结为以下优化问题：
(目标函数采用最大似然函数、样本|参数单词预测上下文； context由给定节点单词的左右两侧w窗口内的单词组成； 不考虑文中上下文单词出现的顺序，直接最大化上下文中出现的所有单词的概率)
伽马重复执行deepwalk算法。 在每个循环中，打乱词汇表v，生成随机排序并遍历所有节点。 然后得到以各节点为起点节点的随机游走列W_vi，利用语言模型SkipGram更新节点的嵌入式表示。
二、Node2vec 1、来源： 2016年出现的n2v，与DeepWalk相比，采用调整随机游走权重的方法将graph embedding结果与网络同质性(homophily )和结构性(structural equily )进行比较
2、思想
按作者原文理解： use flexible，biasedrandomwalksthatcantradeoffbetweenlocalandglobalviewsofthenetwork。
3、图解
具体地说，所谓网络的“同质性”，来自邻近节点的嵌入式表示应该尽可能近似，如图4所示，节点u和与其相连的节点s1、s2、s3、s4的嵌入式表示应该相近，这是
“结构”意味着结构上类似节点的嵌入式距离应当尽可能地近。在图4中，节点u和节点s6是各自本地网络的中心节点，结构上类似，嵌入式距离的表示也应当近似
node2vec与deepwalk不同，主要通过节点间的跳跃概率。 跳跃概率是考虑当前的跳跃节点和从上一个节点到下一个节点的"距离"，用返回参数p和出入(或远离)参数q来控制游动的方向的三个阶段的关系(例如，
节点转移的图像如下。
这里，d_tx是指从节点t到节点x的距离，参数p和q都控制着随机游动的倾向。
参数p被称为返回参数return parameter，p越小越有可能随机返回节点t，节点2 vec的重点是表现网络的结构性
参数q被称为进入参数(in-out parameter )，q越小，随机游走到远方节点的可能性越高，节点2 vec更注重表现网络的同质性，相反，当前节点位于附近节点的可能性越高
游走。4、算法流程
）计算转移概率矩阵，即构建全网转移概率图。(preNode, curNode, [curNode所有邻居dstNode的跳转概率] )
2. ）采样，生成训练样本序列
3. ）梯度下降优化
维度d，每个节点生成r个长度为l的语料序列。上下文context长度为k。
start node : u
初始节点u和它的邻域表示：{u,s4,s5,s6,s8,s9}
u的邻域：$N_s(u)=(s_4,s_5,s_6,s_8,s_9)$
walk是节点u生成的随机游走的样本结果集。为了便于说明，上下两个伪代码框分别从0开始编号。
第5行到第8行对每个顶点进行r轮游走，生成长度为l的顶点序列，保存在集合walks中。
第9行是做梯度下降优化。推荐使用负采样
5、总结
node2vecWalk部分的第1步是初始化序列walk，只需注意此时walk已经包含了两个元素[pre, curr]，然后进行l步n2v游走。第3行获取walk中上一步的节点作为当前节点curr，…剩下就没有难度了。
注意，在GetNeighbors中，对于当前节点curr，可以对所有邻居采样，再计算。
代码写得很清楚，只需要注意构建图的时候，对每个节点先走一步，产生(prevNodeId ,currentNodeId) 这个itempair，在调用node2vecWalk，对currentNodeId走l轮，产生(item1,item2,item3..)
参考：https://zhuanlan.zhihu.com/p/90783845
三、node2vec源码运行1、下载地址：https://github.com/aditya-grover/node2vec
2、python 版本：src/main.py中修改
1）路径：
default='graph/karate.edgelist'—>default='../graph/karate.edgelist' # 构造的边 default='emb/karate.emb'—>default='../emb/karate.emb' # 生成的模型2) 做下类型转换
walks = [map(str, walk) for walk in walks]—>walks = [list(map(str, walk)) for walk in walks]3) save_word2vec_format方法已弃用
model.save_word2vec_format(args.output)—>model.wv.save_word2vec_format(args.output) 3、scala版本上述项目中node2vec_spark为scala版本的项目
1）导入项目
先删除.idea文件目录，然后在文件src下右键—Make Directory as—Sources Root【否则会出现import本地文件找不到路径的问题】