看到一个很有意思的算法，而且腾讯朋友圈lookalike一文中也有提及到，于是蹭一波热点，学习一下。论文是也发KDD2016

.

.

一、主要论文：node2vec: Scalable Feature Learning for Networks

本节引用自

a、微博洪亮劼 ：【论文每日读】node2vec: Scalable Feature Learning for Networks

b、简书：node2vec: Scalable Feature Learning for Networks

本文的特征抽取方式类似于聚类分析的非监督方法，本质上都是利用相邻节点之间的联系。文中提到了网络中的节点一般有两种相似度量：1.内容相似性，2.结构相似性。其中内容相似性主要是相邻节点之间的相似性，而结构上相似的的点并不一定是相邻的，可能隔得很远，这也是文中为何要把BFS和DFS相结合来选择邻居节点的原因。

文章的主要想法就是，利用SkipGram的方法，来为Networks抽取Representation。那么，自然，根据SkipGram的思路，最重要的就是定义这个Context，或者说是Neighborhood。​从文本的角度来说，这个Neighborhood当然就是当前Word周围的字，这个定义非常自然。但是对于Graph或者Network来说就来得没那么容易了。

文章阐述了一般所采用Depth-First Search或者是Breadth-First Search来Sample一个Node的周边Node的问题。简单来说，BFS比较容易有一个Microscopic的View而DFS容易有一个Macro-view，两者都有Representative的问题。

文章的核心思想是采用Random Walk来代替DFS或者BFS。文章定义了一种二阶的Random Walk，拥有两个参数，来控制多大的概率反复经过一些Node和控制所谓的Inward和Outward。总之，整个Random Walk的目的就是在DFS和BFS之间采取某种平衡。

文章虽然提出的是关于Node Feature提取的算法，但是Edge Feature也可以很容易从Node Feature导出。

总体感觉是，硬要用SkipGram或者WordVec的想法在Networks上做，还显得比较牵强。因为有这个Neighborhood的概念，在Graph上，反而不是那么直观得定义，因此所有类似的工作都显得比较别扭。当然，这篇文章也不失为一种不错的Heuristic。​

.

.

.

二、python实现

github网址

案例：

To run node2vec on Zachary’s karate club network, execute the following command from the project home directory:

python src/main.py --input graph/karate.edgelist --output emb/karate.emd

Options

You can check out the other options available to use with node2vec using:

python src/main.py --help

Input

The supported input format is an edgelist:

node1_id_int node2_id_int <weight_float, optional>

The graph is assumed to be undirected and unweighted by default. These options can be changed by setting the appropriate flags.

Output

The output file has n+1 lines for a graph with n vertices. The first line has the following format:

num_of_nodes dim_of_representation

The next n lines are as follows:

node_id dim1 dim2 ... dimd

where dim1, … , dimd is the d-dimensional representation learned by node2vec.

.

.

.

三、腾讯对node2vec的应用

微信公众号infoQ:当机器学习遇上复杂网络：解析微信朋友圈 Lookalike 算法

这个横轴是与广告进行互动的好友个数，纵轴是用户对广告的关注率（包括查看，点赞或者评论），我们发现这个关注率会随着好友数的增加而上升。这个数据拐点差不多是3到5个好友。

重点会挖掘这两个价值，就是社交同质性和社交影响力。

实际上在一个社交网络的节点也是这样的，我们经常会存在一些大的节点，他会有非常多的好友，有的人好友就达不到那么多。所以说其实在社交网络里面的一个节点的分布也是幂律分布。如何把Wodrd2Vec迁移到node2vec，这个时候就要产生一个节点的序列，它对应到了自然语言处理的一条句子，图结构里面的节点相当于NLP的一个单词。

所以在图网络上按照一个搜索的方法生成节点序列，这个节点的序列可以对应到自然语言的一个句子，后面我们通过Wodrd2Vec的框架，将节点embedding为一个向量。所以对于做network embedding的时候，这个生成节点序列的搜索策略非常重要。最简单的一个方法，就是随机游走，随机游走一方面生成节点序列，另一方面也是对图的一种采样，降低了计算量。

比如说我们的一个社交网络，我的同学会形成一个社团，设计这个P往回走，就更容易走到我这个群体。当P越大，它会越能体现同质性。Q越大的时候，它其实能够体现这种结构的相似性，不同的节点有不同的作用。比如说F节点和E节点它是连接这两个社团的桥接点。当Q大的时候，它体现的是网络结构的相似性。这时候我们怎么选P和Q？这个可以根据实际任务进行半监督的学习。

给大家看一下node2vec的结果，先给大家看这个算法的输出。这里有一个简单的图，做embedding之后的结果，1和2的节点向量是一样的，它会是重叠的一个向量，3、4、5、6也是一个重合的节点，它表达的是什么呢？为什么1和2完全重叠？其实1和2的网络环境是一模一样的，这个embedding的结果表达是是节点的社交网络环境，也就是我们说的拓扑特征。

对社交相似性的学习框架，大家可以看下面的图。 我们建立一个回归的model。现在做的是SVR模型。输入好友网络，沟通网络、文章的转发阅读网络等等，进行embedding得到特征向量表达，通过SVR模型，学习到这些特征和广告相似度的函数关系。这个函数关系计算出好友相似度，可以对好友进行排序。

我们看一下算法的效果。我们评估算法的效果，最直接的就是说我有多个算法，广告主需要100万的用户，我这几个算法都给出100万用户，然后看一下这100万的用户点击量是怎么样的，我们叫Lift值。其他的算法跟它进行对比，看一下它的效果有没有提升。那我们的算法相比直接的二分类模型有2倍-3倍的lift。