python - 来自连通图的 Numpy 集群

Question

聚类连通图的最佳方法是什么？

例1：

[[ 1 1 1 1 0 0]
 [ 1 1 1 1 0 0]
 [ 1 1 1 1 0 0]
 [ 1 1 1 1 0 0]
 [ 0 0 0 0 1 1]
 [ 0 0 0 0 1 1]]

结果 ：

==> [[0,1,2,3],[4,5]]

ex2

[[ 0 1 0 1 0 0]
 [ 1 1 0 1 0 0]
 [ 0 1 0 1 0 0]
 [ 1 0 0 0 0 0]
 [ 0 0 1 0 1 1]
 [ 0 0 0 0 1 1]]

结果 ：

==> [[0,1,3],[2,4,5]]

ex3

[[ 0 1 0 0 0 0]
 [ 1 1 0 0 0 0]
 [ 0 0 1 1 0 0]
 [ 0 0 0 1 0 0]
 [ 0 0 0 0 1 1]
 [ 0 0 0 0 1 1]]

结果 ：

==> [[0,1],[2,3],[4,5]]

谢谢

Answer 1

例如，在某些示例中ex2，您给出了一个有向图或有向图，例如A != A.T。在这种情况下，通过考虑强连通分量可以找到更合理的定义。在这种情况下，分裂是[0,1,3],[4,5],[2]。networkx可以帮助您找到这些：

import numpy as np
import networkx as nx

A = np.array([[0,1,0,1,0,0],
              [1,1,0,1,0,0],
              [0,1,0,1,0,0],
              [1,0,0,0,0,0],
              [0,0,1,0,1,1],
              [0,0,0,0,1,1]])

G = nx.from_numpy_matrix(A, create_using=nx.DiGraph()) 
for subg in nx.strongly_connected_component_subgraphs(G):
    print subg.nodes()