python - 如何对在 NetworkX 中创建的图 g 进行聚类？

Question

我正在尝试将聚类应用于数据集。在此之前，我必须将图形分成 n 个集群，但我不知道该怎么做。

Answer 1

假设 边缘列表您的 未加权 和 未定向 图 保存在文件edges.txt 中。您可以按照以下步骤对图的节点进行聚类。
第一步:获取 每个节点的嵌入在图中。这意味着你需要得到一个 连续向量表示对于每个节点。您可以使用图嵌入方法，例如 node2vec , deepwalk 等来获得嵌入。请注意，此类方法保留了向量表示(嵌入空间)中图形节点之间的结构相似性。下面的示例展示了如何做到这一点。

import networkx as nx
G=nx.Graph();
G=nx.read_edgelist("edges.txt") # edges.txt contains the edge list of your graph

# help to draw https://networkx.github.io/documentation/networkx-1.9/examples/drawing/labels_and_colors.html
nx.draw(G,with_labels = True,node_color='b',node_size=500);

from node2vec import Node2Vec
# Generate walks
node2vec = Node2Vec(G, dimensions=2, walk_length=20, num_walks=10,workers=4)
# Learn embeddings 
model = node2vec.fit(window=10, min_count=1)
#model.wv.most_similar('1')
model.wv.save_word2vec_format("embedding.emb") #save the embedding in file embedding.emb

第 2 步:应用聚类方法。一旦获得节点的向量表示，就可以根据这些表示对节点进行聚类。请参阅下面的示例。

from sklearn.cluster import KMeans
import numpy as np


X = np.loadtxt("embedding.emb", skiprows=1) # load the embedding of the nodes of the graph
#print(X)
# sort the embedding based on node index in the first column in X
X=X[X[:,0].argsort()]; 
#print(X)
Z=X[0:X.shape[0],1:X.shape[1]]; # remove the node index from X and save in Z

kmeans = KMeans(n_clusters=2, random_state=0).fit(Z) # apply kmeans on Z
labels=kmeans.labels_  # get the cluster labels of the nodes.
print(labels)