큰 그래프의 간단한 경로 쿼리

Question

큰 그래프 데이터에 대한 질문이 있습니다. 거의 1 억 개의 에지와 약 5 백만 개의 노드를 가진 커다란 그래프가 있다고 가정 해보십시오.이 경우, 모든 간단한 경로 길이를 줄 수있는 가장 좋은 그래프 마이닝 플랫폼은 무엇입니까? < = k (k = 3,4 인 경우 , 5) 주어진 두 노드 사이. 주요 관심사는 그 경로를 얻는 속도입니다. 또 다른 것은 그래프가 지향된다는 것입니다. 그러나 프로그램은 경로를 계산할 때 방향을 무시하지만 실제로 경로가 지정되면 실제로 방향이 지정된 가장자리를 반환합니다. 예컨대

:

A -> C < - D는 -> B 3.

감사 미리 길이 노드 A와 B 사이의 유효한 경로이다.

Answer 1

네트워크에서이 작업을 수행하는 방법입니다. 그것은 대략 here에 주어진 솔루션을 기반으로합니다. 나는 a->b과 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 ([가장자리] (인접)에 대한 경로 (인접 항목) _ 경로가 제외 항목에있는 인접 항목 인 경우 getPaths (G, 인접 항목, 대상 , maxLength-1, excludeSet)

Answer 2

나는 다루기 쉽고 배우기 쉬운 Gephi을 사용하는 것이 좋습니다.

Neo4j이 약간의 코딩으로 요구 사항을 충족시킬지라도 발견했습니다.