如何在Python中集群图形？

设G是图.所以G是一组节点和一组链接.我需要找到一种快速分割图形的方法.我现在正在使用的图表只有120*160个节点,但我可能很快会在另一个上下文(不是医学,但是网站开发)中处理同等问题,有数百万个节点.

所以,我所做的是将所有链接存储到图表矩阵中:

M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))

如果节点s连接到节点t,则M在位置s,t中保持1.我确保M是对称的M [s,t] = M [t,s],并且每个节点链接到它自己M [s,s] = 1.

如果我记得很好,如果我将M与M相乘,则结果是一个矩阵,表示连接通过两个步骤到达的顶点的图形.

因此,我继续将M自身与M一起使用,直到矩阵中的零数不再减少为止.现在我有连接组件的列表.现在我需要对这个矩阵进行聚类.

到目前为止,我对算法非常满意.我认为它简单,优雅,而且速度相当快.我在这部分遇到了麻烦.

基本上我需要将此图拆分为其连接的组件.

我可以浏览所有节点,看看它们连接的是什么.

但是如何排序矩阵重新排序.但我不知道是否可以这样做.

以下是目前的代码:

def findzeros(M):
    nZeros=0
    for t in M.flat:
        if not t:
            nZeros+=1
    return nZeros

M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))    
for s in data.keys():
    MatrixCells[s,s]=1
    for t in data.keys():
        if tthreashold:
                M[s,t]=1
                M[t,s]=1

nZeros=findzeros(M)
M2=M*M
nZeros2=findzeros(M2)

while (nZeros-nZeros2):
    nZeros=nZeros2
    M=M2
    M2=M*M
    nZeros2=findzeros(M2)

编辑:

有人建议我使用SVD分解.以下是5x5图表上问题的简单示例.我们将使用这个,因为19200x19200方阵并不容易看到簇.

import numpy
import scipy

M=numpy.mat(numpy.zeros((5,5)))

M[1,3]=1
M[3,1]=1
M[1,1]=1
M[2,2]=1
M[3,3]=1
M[4,4]=1
M[0,0]=1

print M

u,s,vh = numpy.linalg.linalg.svd(M)
print u
print s
print vh

基本上这里有4个集群:(0),(1,3),(2),(4)但是我仍然没有看到svn如何在这种情况下提供帮助.

为什么不使用像Python-Graph这样的真实图形库？它具有确定连接组件的功能(尽管未提供示例).我想象一个专用的库会比你编写的任何特殊的图形代码更快.

编辑:NetworkX似乎可能是比python-graph更好的选择; 它的文档(这里是连接组件功能)当然是.

在SciPy中,您可以使用稀疏矩阵.还要注意,有更有效的方法可以将矩阵自身相乘.无论如何,你要做的是通过SVD分解完成的.

介绍有用的链接.