python - MapReduce、Python 和 NetworkX

Question

我已经为我使用 NetworkX 在 Python 中构建的图形实现了一个未加权的随机游走函数。下面是我处理随机游走的程序片段。在我的程序的其他地方，我有一个创建图形的方法，还有一个模拟我编写的各种自定义图形测试方法的方法。其中一种图测试方法从图中随机选择两个节点，并在它们之间随机游走。从这个随机游走中计算的两件事是命中时间(从起点到终点遍历的链接数)和通勤时间(从起点到终点再回到起点的遍历链接数) ).

def unweighted_random_walk(starting_point,ending_point, graph):
    '''
    starting_point: String that represents the starting point in the graph
    ending_point: String that represents the ending point in the graph
    graph: A NetworkX Graph object
    '''
    ##Begin the random walk
    current_point=starting_point
    #current_node=graph[current_point]
    current_point_neighors=graph.neighbors(current_point)
    hitting_time=0

    #Determine the hitting time to get to an arbitrary neighbor of the
    #starting point
    while current_point!=ending_point:
        #pick one of the edges out of the starting_node with equal probs
        possible_destination=current_point_neighbors[random.randint(0,current_point_neighors)]
        current_point=possible_destination
        current_point_neighbors=graph.neighbors(current_point)
        hitting_time+=1
    return hitting_time

我的随机游走代码非常简单，因为我只是选择随机节点直到到达终点。但是，当我尝试运行几次随机游走时(我想我有时需要运行一百万次)，当前的实现速度非常慢。

我的问题是:有没有什么方法可以使用 Hadoop MapReduce 来并行化此处针对此随机游走进行的某些操作？有没有更好的方法让我进行随机游走？

Answer 1

我看不出 map-reduce 对您有何帮助。它用于具有两部分操作的地方:第一部分是可以对许多不同数据元素独立执行的计算，第二部分以某种方式组合所有这些结果。也许有一种聪明的方法可以使用 map-reduce 来帮助进行这种随机游走，但我没有看到。

您的随机游走是完全随机的:它可能以许多循环结束，甚至在继续之前在相同的两个节点之间来回跳跃。也许您想以某种方式限制它，这样您就没有那么大的搜索空间？