python - MapReduce、Python 和 NetworkX

Question

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

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 来并行化此随机游走中正在进行的一些操作？有没有更好的方法让我随机游走？

score 5 · Accepted Answer

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

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

score 2 · Accepted Answer

要解决您的问题：

您需要解决 Ned 的评论。他打我说。解释你的代码；稍后会详细介绍。
我无法理解可以并行运行的步行算法。就其本质而言，它们都是线性过程。每一步都依赖于前一步。如果不知道前一个节点（起始节点除外），您不可能知道要跳转到的下一个节点。如果您的代码确实代表了一个随机游走，其中选择都独立于之前的选择，您需要在您的问题中解释这一点。
但是，假设每个随机游走都是独立的，您可以同时运行许多随机游走。我们称这种场景为embarassingly parallel，这是一件非常幸运的事情。
我不知道你为什么要使用 Hadoop，特别是在这里。第一步应该是，“我可以把它写成一个基本程序，然后使用一个 qsub（或等效的）脚本将这个程序的一堆运行分包到服务器上吗？” 如果答案是否定的，下一步是“我可以使用多处理模块吗？” 如果您使用多处理，您可能想看看Jesse Noller 在 PyCon 2009 上的多处理演示。

现在，关于您的特定代码...

您需要解释图中的节点是什么。我很困惑为什么您将它们视为字典（调用.keys()）。如果它们是字典，请告诉我们键和值是什么。我希望您不要将邻居作为密钥存储在那里，因为 NetworkX 已经通过该Graph.neighbors()方法为您提供了这一点。如果您将节点的邻居存储在节点本身中，那么您对 NetworkX 库有误解。让图表为您完成工作。
您有两次相同的逻辑unweighted_random_walk()，一次是从开始节点到目标节点的行程，然后是从目标节点到开始节点的行程。为什么？您所需要的只是一个方向的逻辑。调用此函数两次。使用起始节点和目标节点作为参数调用它以获取一个方向的方向，然后将参数的顺序交换为目标，然后开始获取另一个方向的步行。然后，您有两个独立的调用，现在可以并行运行它们。
不要使用while True:— 不仅在这里，而且在一般情况下。您应该始终指出要继续的实际条件。例如，
```
while current_point != ending_point:
    ...
```
不要返回一串信息，直接返回信息。例如，
```
return hitting_time
```
请注意，按照我在上面第 2 点中的建议，您只需要返回击球时间，并将 there-call 和 back-call 的击球时间相加即可获得总通勤时间。方便，对吧？

也可以看看

用于 Python 可访问 MapReduce 实现的Disco 项目
Jesse Noller 在PyCon 2009上关于并发和分布式计算的演讲

编辑：包含指向 Jesse Noller 的演示文稿和迪斯科的链接。

score 0 · Accepted Answer

0

如果您使用本文中详述的公式，则不必实际执行随机游走。

于 2013-11-12T15:07:17.993 回答

python - MapReduce、Python 和 NetworkX

3 回答 3

Related

Reference