DeepWalk算法详解

一、DeepWalk算法缺点

DeepWalk算法是一种用于图嵌入的无监督学习算法，它在学习图的低维表示方面表现出色。然而，它也有一些缺点：

1、DeepWalk算法基于随机游走，对于大图，这个方法可能会带来较高的计算复杂度。

2、DeepWalk算法依赖于节点的邻居关系，在节点之间存在高度长距离的图上时，DeepWalk效果可能不佳。

3、DeepWalk算法不能捕获节点的全局结构信息。

二、DeepWalk算法详解刘建平

DeepWalk算法是由加拿大蒙特利尔大学的Jian Tang等人在2015年提出的一种无监督学习算法。它通过把每个节点看做一个词，将图转换成一个句子，然后通过Word2Vec模型学习每个节点的低维表示。

DeepWalk算法之所以能够有效地学习节点的低维表示，是因为它利用了本质上与自然语言处理相同的思路：图是一种高维数据，很难直接处理，但是可以将其映射到低维空间中，这样可以更好地进行处理。

其中，DeepWalk算法的核心是随机游走过程。该过程从某个节点开始，依次按照一定的策略，选择这个节点的邻居节点进行移动，最终形成一个游走路径。重复执行该过程，就可以得到一系列游走路径，这些路径就是DeepWalk算法中的“句子”。Word2Vec对“句子”进行学习，得到每个节点的低维表示。

三、DeepWalk算法的用处

DeepWalk算法可以帮助应用程序中节点之间的相似性计算、节点分类、社区检测等领域。因为在图中，通常节点之间的相似性是由它们在图上的结构相似性决定的，而DeepWalk算法可以有效地捕捉这种结构信息。

可以利用DeepWalk算法帮助数据挖掘的应用：对于大规模的有标签和无标签网络数据集，DeepWalk通过将节点映射到低维向量空间，形成对节点的嵌入表示，弥补了浅层方法的局限性并成功将节点嵌入进向量空间。

可以利用嵌入向量在下游机器学习任务，例如节点分类、边预测、社区发现、数据可视化、相似性计算等等。

四、DeepWalk算法谱聚类

DeepWalk算法可以利用得到的节点嵌入向量进行谱聚类。谱聚类是一种标准的无监督分类技术，可以将相似的数据划分成同一组。

谱聚类之所以能够在各种分类问题中表现良好，是因为它能够有效地从数据的内在特征中提取信息。相似特征具有相似的嵌入向量，因此可以通过谱聚类将节点分组。

#deepwalk谱聚类代码示例
import networkx as nx
from gensim.models.word2vec import Word2Vec
from sklearn.cluster import KMeans
from sklearn.decomposition import PCA
from sklearn.mixture import GaussianMixture

graph=nx.read_edgelist("email-Eu-core.txt",nodetype=int)
walks=[]
for node in graph.nodes():
    for i in range(5):
        walk=nx.random_walk(graph, [node], length=20)
        walks.append([str(node) for node in walk])
model=Word2Vec(walks,size=128,window=10,min_count=0,sg=1,workers=8)
embeddings=model.wv
X=list(embeddings.values())
km=KMeans(n_clusters=42,n_init=20,tol=1e-12)
km.fit(X)

gmm=GaussianMixture(n_components=42, covariance_type='diag',tol=1e-8,min_covar=1e-8)
gmm.fit(X)

pca=PCA(n_components=2)
pca.fit(X)
reduced_X=pca.fit_transform(X)

五、DeepWalk算法以及实现

DeepWalk算法的核心是对图进行随机游走，得到游走序列，然后使用Skip-gram模型训练节点的嵌入向量。下面是DeepWalk算法的实现步骤：

1、构造图的邻接矩阵。

2、利用任意节点开始的随机游走算法，生成一系列游走路径，称为“句子”。

3、利用Word2Vec模型，对“句子”进行学习，得到每个节点的低维表示，即嵌入向量。

在Python中，可以使用Gensim库提供的Word2Vec函数实现DeepWalk算法。下面是DeepWalk算法的实现代码：

#DeepWalk算法代码示例
from gensim.models import Word2Vec
from gensim.models.word2vec import LineSentence
from sklearn.neighbors import NearestNeighbors
import networkx as nx

#加载图
G=nx.read_edgelist("email-Eu-core.txt", nodetype=int)

#生成游走路径
sentences=[]
num_walks=10 
walk_length=80 
for _ in range(num_walks):              
    for node in G.nodes():
        sentence=[node]
        for _ in range(walk_length-1):
            neighbors=list(G.neighbors(sentence[-1]))
            sentence.append(np.random.choice(neighbors))
        sentences.append([str(i) for i in sentence])
            
#训练Word2Vec模型
model=Word2Vec(sentences, size=128, window=5, min_count=0, sg=1, iter=1)

#保存节点的嵌入向量
embeddings={}
for node in G.nodes():
    embeddings[node]=model.wv[str(node)]

#寻找最近的节点
knn=NearestNeighbors(n_neighbors=10)
knn.fit(embeddings.values())
print(knn.kneighbors([embeddings[0]])[1])

六、DeepWalk算法基本原理

DeepWalk算法通过将图转化为文本序列，然后利用Word2Vec模型学习每个节点的嵌入向量。下面是DeepWalk算法的基本原理：

1、生成节点邻接矩阵A。

2、从一个初始节点开始，按照随机游走策略，不断移动到与它邻接的节点。

3、重复上面的步骤生成多个游走路径，这些路径就是DeepWalk算法中的“句子”。

4、利用Word2Vec模型训练“句子”，得到每个节点的嵌入向量。

通过生成节点的嵌入向量，我们可以将图中节点的低维信息捕捉到。在得到节点的嵌入向量后，可以使用这些向量进行节点分类、社区检测等任务。