Deepwalk(深度游走)算法简介

Mr.Cheng1996

33841人浏览 · 2019-09-11 19:33:51

Mr.Cheng1996 · 2019-09-11 19:33:51 发布

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

主要思想

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.

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模