0

大きなグラフデータについて質問があります。ほぼ 1 億のエッジと約 500 万のノードを持つ大きなグラフがあるとします。この場合、長さ <=k (k=3,4 の場合) のすべての単純なパスを与えることができる、あなたが知っている最高のグラフ マイニング プラットフォームは何ですか? ,5) 任意の 2 つのノード間。主な懸念事項は、これらのパスを取得する速度です。もう 1 つのことは、グラフが有向であることですが、プログラムがパスを計算するときに方向を無視し、それらのパスを見つけたら実際に有向のエッジを返すようにしたいと考えています。

例えば：

a -> c <- d -> b は、長さ 3 のノード 'a' と 'b' の間の有効なパスです。

前もって感謝します。

4

2 に答える 2

1

したがって、これは networkx で行う方法です。それは私がここで与えた解決策に大まかに基づいています。a->bと は、あなたが望む2つの異なるパスであると想定していa<-bます。これをリストのリストとして返します。各サブリストは、パスの (順序付けられた) エッジです。

import networkx as nx
import itertools

def getPaths(G,source,target, maxLength, excludeSet=None):
    #print source, target, maxLength, excludeSet
    if excludeSet== None:
        excludeSet = set([source])
    else:
        excludeSet.add(source)# won't allow a path starting at source to go through source again.
    if maxLength == 0:
        excludeSet.remove(source)
        return []
    else:
        if G.has_edge(source,target):
            paths=[[(source,target)]]
        else:
            paths = []
        if G.has_edge(target,source):
            paths.append([(target,source)])
        #neighbors_iter is a big iterator that will give (neighbor,edge) for each successor of source and then for each predecessor of source.

        neighbors_iter = itertools.chain(((neighbor,(source,neighbor)) for neighbor in G.successors_iter(source) if neighbor != target),((neighbor,(neighbor,source)) for neighbor in G.predecessors_iter(source) if neighbor != target))

        #note that if a neighbor is both a predecessor and a successor, it shows up twice in this iteration.  

        paths.extend( [[edge] + path for (neighbor,edge) in neighbors_iter if neighbor not in excludeSet for path in getPaths(G,neighbor,target,maxLength-1,excludeSet)] )

        excludeSet.remove(source) #when we move back up the recursion, don't want to exclude this source any more

        return paths

G=nx.DiGraph()
G.add_edges_from([(1,2),(2,3),(1,3),(1,4),(3,4),(4,3)])

print getPaths(G,1,3,2)

>[[(1, 3)], [(1, 2), (2, 3)], [(1, 4), (4, 3)], [(1, 4), (3, 4)]]

networkx のダイクストラ アルゴリズムを変更することで、より効率的なアルゴリズムに到達することが期待されます (ダイクストラ アルゴリズムにはカットオフがありますが、デフォルトでは最短パスのみを返し、エッジ方向に従います)。 .

これは、paths.extend 全体の代替バージョンです。 excludeSet) if len(path)>0 ] )

于 2015-01-31T08:28:31.477 に答える
0

扱いやすく、習得しやすいGephiを使用することをお勧めします。

見つかった場合でも、Neo4jは少しのコーディングで要件を満たします。

于 2015-01-30T16:34:03.690 に答える