Python 随机游走算法实现图嵌入：详细步骤与代码示例

图嵌入 (graph embedding) 是将图中的节点映射到向量空间中的过程，通常用于图分类、节点聚类等任务中。其中，随机游走算法是一种常见的图嵌入方法。

下面是使用 Python 实现随机游走算法实现图嵌入的步骤：

构建图数据结构

首先，需要将图的节点和边信息读入并构建成图数据结构。可以使用 networkx 库来完成这一步骤。

import networkx as nx

# 读入节点和边信息
G = nx.read_edgelist('graph.txt', nodetype=int)

# 构建图数据结构
graph = {}
for node in G.nodes():
    neighbors = [n for n in G.neighbors(node)]
    graph[node] = neighbors

定义随机游走函数

随机游走算法的核心是定义一个随机游走函数，用于从图中某个节点出发，按照一定的概率随机游走到相邻节点。这里我们定义一个函数，输入参数为起始节点、游走步数和返回序列的长度，输出为一个游走序列。

import random

def random_walk(node, walk_len, seq_len):
    seq = [node]
    for i in range(walk_len):
        neighbors = graph[seq[-1]]
        if len(neighbors) == 0:
            break
        seq.append(random.choice(neighbors))
    
    seq = [str(s) for s in seq]
    while len(seq) < seq_len:
        seq.append(str(random.choice(list(graph.keys()))))
    
    return seq[:seq_len]

生成随机游走序列

使用随机游走函数生成一些随机游走序列，作为节点的嵌入向量。

num_walks = 10
walk_len = 80
seq_len = 10

walks = []
for node in graph.keys():
    for i in range(num_walks):
        walk = random_walk(node, walk_len, seq_len)
        walks.append(walk)

训练嵌入模型

将随机游走序列输入到嵌入模型中进行训练，得到每个节点的嵌入向量。

这里使用 gensim 库中的 Word2Vec 模型来完成训练。

from gensim.models import Word2Vec

model = Word2Vec(walks, size=128, window=5, min_count=0, sg=1, workers=4)

获取节点嵌入向量

最后，可以使用训练好的嵌入模型获取每个节点的嵌入向量，以便在图分类、节点聚类等任务中使用。

embedding = {}
for node in graph.keys():
    embedding[node] = model.wv[str(node)]

完整代码如下：

import networkx as nx
import random
from gensim.models import Word2Vec

# 读入节点和边信息
G = nx.read_edgelist('graph.txt', nodetype=int)

# 构建图数据结构
graph = {}
for node in G.nodes():
    neighbors = [n for n in G.neighbors(node)]
    graph[node] = neighbors

# 定义随机游走函数
def random_walk(node, walk_len, seq_len):
    seq = [node]
    for i in range(walk_len):
        neighbors = graph[seq[-1]]
        if len(neighbors) == 0:
            break
        seq.append(random.choice(neighbors))
    
    seq = [str(s) for s in seq]
    while len(seq) < seq_len:
        seq.append(str(random.choice(list(graph.keys()))))
    
    return seq[:seq_len]

# 生成随机游走序列
num_walks = 10
walk_len = 80
seq_len = 10

walks = []
for node in graph.keys():
    for i in range(num_walks):
        walk = random_walk(node, walk_len, seq_len)
        walks.append(walk)

# 训练嵌入模型
model = Word2Vec(walks, size=128, window=5, min_count=0, sg=1, workers=4)

# 获取节点嵌入向量
embedding = {}
for node in graph.keys():
    embedding[node] = model.wv[str(node)]