如何对使用NetworkX创建的图形g进行聚类？

Question

我正在尝试将聚类应用于数据集。在此之前，我必须将图形划分为n个簇，但我不知道该如何做。

- aravind rokkam

---

这是最近出现的一个例子 https://stackoverflow.com/a/62891137/9698684 - yatu

Answer 1

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

第1步：获取图中每个节点的嵌入。这意味着您需要为每个节点获取一个连续向量表示。您可以使用图嵌入方法，例如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

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

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)

- Roohollah Etemadi

---

有关加权和有向图的建议？ - Borhan Kazimipour

对于有向图，请使用以下代码加载图形并将其转换为有向图：G = nx.read_weighted_edgelist（“edges.txt”）和G = G.to_directed（）。其他部分应该是相同的。请注意，edges.txt文件还包含边及其权重，例如：SourceNode_ID DestinationNode_ID Weight；您还可以在https://github.com/agoodweathercc/EmbeddingEval中找到有用的信息。 - Roohollah Etemadi