连通图的numpy集群 [英] Numpy cluster from connected graph

问题描述

集群连接图的最佳方法是什么?

What is the best way to cluster connected graph ?

ex1:

[[ 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]]

谢谢

推荐答案

在某些示例中，例如ex2，您给出了一个有向图或一个有向图，例如A != A.T.在这种情况下，可以通过考虑 强连接的组件 .在这种情况下，拆分为[0,1,3],[4,5],[2]. networkx 可以帮助您找到这些:

In some of the examples, say ex2, you've given a digraph, or a directed graph such that A != A.T. In this case a more reasonable definition can be found by considering strongly connected components. In this case the splitting is [0,1,3],[4,5],[2]. networkx can help you find these:

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()

这篇关于连通图的numpy集群的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！