MapReduce、Python 和 NetworkX

Question

我在Python中用NetworkX库实现了一个无权随机游走的功能，主要是为了处理我自己构建的图。下面是我程序中与随机游走相关的一小段代码。在程序的其他地方，我有一个方法用来创建图，还有一个方法用来模拟我写的各种自定义图测试方法。其中一个测试方法是随机选择图中的两个节点，然后在这两个节点之间进行随机游走。通过这个随机游走，我主要计算两个东西：一是“到达时间”，也就是从起点到终点经过的链接数量；二是“通勤时间”，也就是从起点到终点再回到起点所经过的链接数量。

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

如果你使用这篇论文中详细介绍的公式，就不需要真的去做随机漫步了。

Answer 2

我不太明白map-reduce能怎么帮你。它通常用于一种两步操作：第一步是对很多不同的数据进行独立的计算，第二步是把所有这些结果合并在一起。也许有一种聪明的方法可以用map-reduce来处理你的随机游走，但我想不出来。

你的随机游走是完全随机的：它可能会出现很多循环，甚至在两个节点之间来回跳动，然后再继续前进。也许你想要限制一下，这样就不用搜索那么大的空间？

Answer 3

关于你的问题：

1. 你需要回应Ned的评论。他比我先说了这个。要解释你的代码，稍后会详细说。

2. 我无法理解一个可以并行运行的随机行走算法。因为它们本质上是线性的，每一步都依赖于前一步。你不可能在不知道前一个节点的情况下知道下一个要跳到哪个节点（除了起始节点）。如果你的代码确实表示一个随机行走，其中的选择与之前的选择无关，你需要在问题中解释清楚。

3. 假设每个随机行走是独立的，你可以同时运行多个随机行走。我们称这种情况为极易并行，这是一件很幸运的事情。

4. 我不明白你为什么要在这里使用Hadoop。第一步应该是，“我能否仅仅写一个基本程序，并使用qsub（或类似的）脚本将这个程序的多个运行分配给服务器？”如果答案是否定的，下一步是，“我能否使用multiprocessing模块？”如果你选择使用multiprocessing，可能想看看Jesse Noller在PyCon 2009的multiprocessing演讲。

现在，关于你的具体代码……

1. 你需要解释一下图中的节点是什么。我不明白你为什么把它们当作字典（调用.keys()）。如果它们是字典，告诉我们键和值是什么。我希望你不是把邻居存储为键，因为NetworkX已经通过Graph.neighbors()方法提供了这个功能。如果你把节点的邻居存储在节点本身里，那你对NetworkX库有误解。让图来为你处理这些事情。

2. 在unweighted_random_walk()中，你的逻辑重复了两次，一次是从起始节点到目标节点，另一次是从目标节点回到起始节点。为什么？你只需要一个方向的逻辑。调用这个函数两次。第一次用起始节点和目标节点作为参数来获取一个方向，然后交换参数的顺序，先目标节点再起始节点来获取另一个方向的行走。这样你就有了两个独立的调用，可以并行运行。

3. 不要使用while True:——不仅在这里，通常也不要。你应该始终指明继续的实际条件。例如：

   while current_point != ending_point:
       ...
   

4. 不要返回一个信息的字符串，直接返回信息。例如：

   return hitting_time
   

   注意，按照我在上面第2点的建议，你只需要返回到达时间，并将去程和回程的到达时间相加，得到总通勤时间。方便吧？

另见

• Disco项目，这是一个Python可用的MapReduce实现
• Jesse Noller在PyCon 2009的关于并发和分布式计算的演讲

编辑：添加了Jesse Noller的演讲链接和Disco的链接。