Network Embedding_LINE

输入：网络图   输出： 节点的向量表示 适用范围：大规模（百万的顶点和数十亿的边）的任意类型的网络：有向或无向、有权或无权。文章中只提到可以扩展到规模很大的网络，小规模网络应该也可以。

First-order Proximity（一阶相似度）：两个顶点之间的自身相似（不考虑其他顶点）。 对于由边（u，v）连接的每一对顶点，边上的权重w(uv)表示u和v之间的相似度，如果在u和v之间没有观察到边，则它们的一阶相似度为0。一阶邻近通常意味着现实世界网络中两个节点的相似性。例如，在社交网络中相互交友的人往往有着相似的兴趣;在万维网上相互链接的页面倾向于谈论类似的话题。

Second-order Proximity（二阶相似度）：网络中一对顶点（u，v）之间的二阶相似度是它们邻近网络结构之间的相似性。 在数学上，设pu=（wu，1，...，wu，| V |）表示u与所有其他顶点的一阶相似度，则u和v之间的二阶相似度 由 pu和pu决定。 如果没有顶点与u和v都连接，则u和v之间的二阶相似度为0。

因为有些边观察不到等原因，一阶相似度不足以保存网络结构。因此提出共享相似邻居的顶点倾向于彼此相似，即二阶相似度。 例如，在社交网络中，分享相似朋友的人倾向于有相似的兴趣，从而成为朋友; 在词语共现网络中，总是与同一组词语共同出现的词往往具有相似的含义。

最优化目标：

1）只保留一阶相似度的LINE模型（一阶相似度只能用于无向图，不能用于有向图。）

顶点 Vi ,Vj 。分别对应向量Ui,Uj。 Wij: 边的权值。

最小化目标： 两个概率分布的KL散度  。两个概率为：经验概率（边的权值得到）和联合概率（向量计算得到）。已经经过化简，去掉了常数项。

联合概率

2）只保留二阶相似度的LINE模型（每个节点，两个向量表示）

每个顶点扮演两个角色：顶点本身和其他顶点的邻居。因此，为每个节点引入两个向量表示ui和ui`：ui是vi被视为顶点时的表示，ui`是当vi被视为特定邻居时的表示。

最小化目标： 两个概率分布的KL散度  。两个概率为：经验概率（边的权值得到）和联合概率（向量计算得到）。已经经过化简，去掉了常数项。

表示，vj是vi的邻居的概率  。其中，|V|是网络中顶点的数目。

参考：https://www.jianshu.com/p/82b9c88a23ad

https://www.jianshu.com/p/8bb4cd0df840

https://www.ccir2017.cn/attachments/oral%20report/3_17_%E5%9F%BA%E4%BA%8E%E7%BD%91%E7%BB%9C%E8%A1%A8%E7%A4%BA%E5%AD%A6%E4%B9%A0%E7%9A%84%E4%B8%AA%E6%80%A7%E5%8C%96%E5%95%86%E5%93%81%E6%8E%A8%E8%8D%90_%E6%96%B0%20.pdf