深度游走:一种社交表示的在线学习算法 主要思想Deepwalk算法参考文献
主要思想
Deepwalk是一种将随机游走(random walk)和word2vec两种算法相结合的图结构数据挖掘算法。该算法能够学习网络的隐藏信息,能够将图中的节点表示为一个包含潜在信息的向量,如图1-2所示。
该算法主要分为随机游走和生成表示向量两个部分。首先利用随机游走算法(Random walk)从图中提取一些顶点序列;然后借助自然语言处理的思路,将生成的定点序列看作由单词组成的句子,所有的序列可以看作一个大的语料库(corpus),最有利用自然语言处理工具word2vec将每一个顶点表示为一个维度为d的向量。
符号定义:一个图可以表示为:G = ( V , E ) G = (V,E) G=(V,E)其中, V V V表示顶点的集合; E E E表示边的集合, 且 E ⊆ V × V E subseteq V times V E⊆V×V。算法: 算法1: D e e p W a l k ( G , w , d , γ , t ) DeepWalk(G, w, d, γ, t) DeepWalk(G,w,d,γ,t)输入:图 G ( V , E ) G(V, E) G(V,E) 窗口尺寸 w w w 输出维度 d d d 以每个节点开始的路径数量 γ γ γ 每条路径的长度 t t t输出:隐含信息的表示矩阵 Φ ∈ R ∣ V ∣ × d Phi in textbf R^{vert V vert} times d Φ∈R∣V∣×d1. 随机初始化 Ф Ф Ф2: for i = 0 i=0 i=0 to γ γ γ do3: 将顶点随机排列,即 O = S h u f f l e ( V ) O=Shuffle(V) O=Shuffle(V)4: for 每一个 v i ∈ O vi∈O vi∈O do:5: W v i = R a n d o m W a l k ( G , v i , t ) W_{v_i} = RandomWalk(G, v_i, t) Wvi=RandomWalk(G,vi,t)6. W o r d 2 v e c ( Ф , W v i , w ) Word2vec(Ф, W_{v_i}, w) Word2vec(Ф,Wvi,w)7. end for8. 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.