当前位置:   article > 正文

Deepwalk(深度游走)算法简介_deepwalk算法

deepwalk算法

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

主要思想

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

图1 输入: 图信号

在这里插入图片描述

图2 输出: 图节点嵌入

Deepwalk算法

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

  1. 符号定义:一个图可以表示为:
    G = ( V , E ) G = (V,E) G=(V,E)其中, V V V表示顶点的集合; E E E表示边的集合, 且 E ⊆ V × V E \subseteq V \times V EV×V
  2. 算法:
算法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 ΦRV×d
1. 随机初始化 Ф Ф Ф
2: for i = 0 i=0 i=0 to γ γ γ do
3:   将顶点随机排列,即 O = S h u f f l e ( V ) O=Shuffle(V) O=Shuffle(V)
4:    for 每一个 v i ∈ O vi∈O viO 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 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.

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/864927
推荐阅读
相关标签
  

闽ICP备14008679号