16

G をグラフとします。したがって、G はノードの集合とリンクの集合です。グラフをすばやく分割する方法を見つける必要があります。私が現在取り組んでいるグラフには 120*160 ノードしかありませんが、別のコンテキスト (医学ではなく Web サイト開発) で数百万のノードを持つ同等の問題にすぐに取り組んでいる可能性があります。

だから、私がしたことは、すべてのリンクをグラフマトリックスに格納することでした:

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 を掛けると、結果は 2 つのステップで到達した頂点を結ぶグラフを表す行列になります。

したがって、行列内のゼロの数が減少しなくなるまで、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

In SciPy you can use sparse matrices. Also note, that there are more efficient ways of multiplying matrix by itself. Anyway, what you're trying to do can by done by SVD decomposition.

Introduction with useful links.

于 2009-03-17T09:37:00.207 に答える
4

接続されたコンポーネントのための効率的なルーチンを備えたgraph_toolとnetworkitもあり、どちらもネットワークを効率的に保存します。何百万ものノードで作業する場合、networkx では十分ではない可能性があります (純粋な python です)。これらのツールはどちらも C++ で記述されているため、妥当な実行時間で大きなグラフの分析を処理できます。

Phil が指摘しているように、あなたのメソッドは大きなグラフの場合、計算時間が非常に長くなり (数日、数週間、数か月...)、100 万ノードのグラフの表現には 100 万ギガバイトのメモリが必要になります。 !

于 2015-04-26T19:37:21.873 に答える
3

Finding an optimal graph partition is an NP-hard problem, so whatever the algorithm, it is going to be an approximation or a heuristic. Not surprisingly, different clustering algorithms produce (wildly) different results.

Python implementation of Newman's modularity algorithm: modularity

Also: MCL, MCODE, CFinder, NeMo, clusterONE

于 2011-09-21T22:25:38.350 に答える
2

他の人が指摘したように、車輪を再発明する必要はありません。最適なクラスタリング手法には多くの考慮が払われています。よく知られたクラスタリング プログラムの 1 つを次に示します。

于 2009-03-18T03:39:18.323 に答える
2

これは、深さ優先検索を使用して接続コンポーネントを見つける単純な実装です。以前に書いたものです。非常にシンプルですが、頂点とエッジの数が 1 万まで拡張できます...


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 に答える
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 に答える