Deepwalk(深度游走)算法简介

深度游走：一种社交表示的在线学习算法

主要思想

Deepwalk是一种将随机游走(random walk)和word2vec两种算法相结合的图结构数据挖掘算法。该算法能够学习网络的隐藏信息，能够将图中的节点表示为一个包含潜在信息的向量，如图1-2所示。
在这里插入图片描述

图1 输入: 图信号

在这里插入图片描述

图2 输出: 图节点嵌入

Deepwalk算法

该算法主要分为随机游走和生成表示向量两个部分。首先利用随机游走算法(Random walk)从图中提取一些顶点序列；然后借助自然语言处理的思路，将生成的定点序列看作由单词组成的句子，所有的序列可以看作一个大的语料库(corpus)，最有利用自然语言处理工具word2vec将每一个顶点表示为一个维度为d的向量。

符号定义：一个图可以表示为：
$G = (V, E)$ 其中， $V$ 表示顶点的集合； $E$ 表示边的集合, 且 $\subseteq V \times V$ 。
算法:

算法1: $D e e p W a l k (G, w, d, γ, t)$
输入：图 $G (V, E)$
窗口尺寸 $w$
输出维度 $d$
以每个节点开始的路径数量 $γ$
每条路径的长度 $t$
输出：隐含信息的表示矩阵 $\Phi \in \textbf R^{\vert V \vert} \times d$
1. 随机初始化 $Ф$
2: for $i = 0$ to $γ$ do
3: 将顶点随机排列，即 $O = S h u f f l e (V)$
4: for 每一个 $v i \in O$ do:
5: $W_{v_i} = RandomWalk(G, v_i, t)$
6. $Word2vec(Ф, W_{v_i}, w)$
7. end for
8. end for

参考文献

[1] Perozzi B, Al-Rfou R, Skiena S. DeepWalk: Online Learning of Social Representations[C]. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14, 2014: 701-710.

原文链接：https://blog.csdn.net/qq_42570717/article/details/100733117