data-mining - 大图上的简单路径查询

Question

我有一个关于大图数据的问题。假设我们有一个包含近 1 亿条边和大约 500 万个节点的大型图，在这种情况下，您所知道的最好的图挖掘平台可以提供所有长度 <=k 的简单路径（对于 k=3,4 ,5) 在任意两个给定节点之间。主要关注的是获得这些路径的速度。另一件事是图是有向的，但我们希望程序在计算路径时忽略方向，但在发现这些路径后仍返回实际有向边。

例如：

a -> c <- d -> b 是节点“a”和“b”之间长度为 3 的有效路径。

提前致谢。

Answer 1

所以这是一种在networkx中实现的方法。它大致基于我在这里给出的解决方案。我假设这是您想要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 中的 dijkstra 算法，您会得到一个更有效的算法（请注意，dijkstra 算法有一个截止点，但默认情况下它只会返回最短路径，并且会遵循边缘方向） .

这是整个 paths.extend 的替代版本： 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) 如果 len(path)>0 ] )

Answer 2

我建议使用易于处理和学习的Gephi 。

如果你找到了它，Neo4j会通过一些编码来满足你的要求。