16

设 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 与自身相乘，直到矩阵中零的数量不再减少。现在我有了连接组件的列表。现在我需要对这个矩阵进行聚类。

到目前为止，我对算法非常满意。我认为它简单、优雅且相当快。我在这部分遇到了麻烦。

本质上，我需要将此图拆分为其连接的组件。

我可以遍历所有节点，看看它们连接到什么。

但是如何对矩阵进行排序以重新排序行。但我不知道是否有可能做到这一点。

以下是到目前为止的代码：

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 t<s:
            if (scipy.corrcoef(data[t],data[s])[0,1])>threashold:
                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 在这种情况下如何提供帮助。

4

8 回答 8

14

为什么不使用真正的图形库，例如Python-Graph？它具有确定连接组件的功能（尽管没有提供示例）。我想一个专用库会比你编写的任何临时图形代码更快。

编辑：NetworkX似乎比 python-graph 更好；它的文档（这里是连接组件功能）当然是。

于 2009-03-17T10:50:17.957 回答
7

在 SciPy 中，您可以使用稀疏矩阵。另请注意，有更有效的方法可以将矩阵自身相乘。无论如何，您尝试做的事情可以通过 SVD 分解来完成。

带有有用链接的介绍。

于 2009-03-17T09:37:00.207 回答
4

还有graph_tool和networkit具有用于连接组件的高效例程，并且都有效地存储网络。如果您要使用数百万个节点，networkx 可能还不够（它是纯 python afaik）。这两个工具都是用 C++ 编写的，因此可以以合理的运行时间处理大图的分析。

正如 Phil 指出的那样，您的方法对于大型图（我们说的是几天、几周、几个月……）的计算时间将非常长，并且您对一百万个节点的图的表示将需要大约一百万 GB 的内存！

于 2015-04-26T19:37:21.873 回答
3

找到一个最优的图分区是一个 NP-hard 问题，所以无论算法是什么，它都将是一个近似值或启发式算法。毫不奇怪，不同的聚类算法会产生（非常）不同的结果。

纽曼模块化算法的Python实现： 模块化

另外：MCL、MCODE、CFinder、NeMo、clusterONE

于 2011-09-21T22:25:38.350 回答
2

这是一些简单的实现，它使用深度优先搜索找到连接的组件，我前段时间写过。虽然它很简单，但它可以很好地扩展到一万个顶点和边......


import sys
from operator import gt, lt

class Graph(object):
    def __init__(self):
        self.nodes = set()
        self.edges = {}
        self.cluster_lookup = {}
        self.no_link = {}

    def add_edge(self, n1, n2, w):
        self.nodes.add(n1)
        self.nodes.add(n2)
        self.edges.setdefault(n1, {}).update({n2: w})
        self.edges.setdefault(n2, {}).update({n1: w})

    def connected_components(self, threshold=0.9, op=lt):
        nodes = set(self.nodes)
        components, visited = [], set()
        while len(nodes) > 0:
            connected, visited = self.dfs(nodes.pop(), visited, threshold, op)
            connected = set(connected)
            for node in connected:
                if node in nodes:
                    nodes.remove(node)

            subgraph = Graph()
            subgraph.nodes = connected
            subgraph.no_link = self.no_link
            for s in subgraph.nodes:
                for k, v in self.edges.get(s, {}).iteritems():
                    if k in subgraph.nodes:
                        subgraph.edges.setdefault(s, {}).update({k: v})
                if s in self.cluster_lookup:
                    subgraph.cluster_lookup[s] = self.cluster_lookup[s]

            components.append(subgraph)
        return components

    def dfs(self, v, visited, threshold, op=lt, first=None):
        aux = [v]
        visited.add(v)
        if first is None:
            first = v
        for i in (n for n, w in self.edges.get(v, {}).iteritems()
                  if op(w, threshold) and n not in visited):
            x, y = self.dfs(i, visited, threshold, op, first)
            aux.extend(x)
            visited = visited.union(y)
        return aux, visited

def main(args):
    graph = Graph()
    # first component
    graph.add_edge(0, 1, 1.0)
    graph.add_edge(1, 2, 1.0)
    graph.add_edge(2, 0, 1.0)

    # second component
    graph.add_edge(3, 4, 1.0)
    graph.add_edge(4, 5, 1.0)
    graph.add_edge(5, 3, 1.0)

    first, second = graph.connected_components(op=gt)
    print first.nodes
    print second.nodes

if __name__ == '__main__':
    main(sys.argv)
于 2009-03-17T14:57:04.993 回答
2

正如其他人指出的那样，没有必要重新发明轮子。对优化聚类技术进行了很多思考。这是一个著名的聚类程序。

于 2009-03-18T03:39:18.323 回答
0

看起来有一个库PyMetis，它会为你划分你的图表，给定一个链接列表。通过将链接节点的原始列表（不是矩阵乘法派生的节点）传递给它，从图表中提取链接列表应该相当容易。

重复执行 M' = MM 对于 M 的大阶不会有效。对于 N 阶矩阵的完整矩阵乘法将花费 N 次乘法和 N-1 次加法每个元素，其中有 N 2，即 O(N 3 ) 操作。如果您将其缩放到“数百万个节点”，那将是每个矩阵-矩阵乘法的 O(10 18 ) 操作，您想要执行几个操作。

简而言之，您不想这样做。Vartec的SVD 建议将是那里唯一合适的选择。您最好的选择就是使用 PyMetis，而不是尝试重新发明图形分区。

于 2009-03-17T11:34:58.723 回答
-1

SVD 算法在这里不适用，但除此之外 Phil H 是正确的。

于 2009-03-18T02:28:41.707 回答