如何对在NetworkX中创建的图形g进行聚类

Question

我正在尝试将集群应用于数据集。在此之前，我必须将图划分为n个簇，我不知道如何做到这一点

Answer 1

假设您的未加权和无向图的边列表保存在edges.txt文件中。您可以按照以下步骤对图的节点进行聚类。

步骤1:获取图中每个节点的嵌入。这意味着您需要为每个节点获得连续向量表示。您可以使用node2vec、deepwal等图嵌入方法来获得嵌入。注意，这种方法在向量表示(嵌入空间(中保持了图的节点之间的结构相似性。下面的例子展示了如何做到这一点。

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)