[HADOOP] MapReduce, Python 및 NetworkX

MapReduce, Python 및 NetworkX

필자는 NetworkX를 사용하여 파이썬으로 작성한 그래프에 대해 가중치없는 무작위 걸기 함수를 구현했습니다. 아래는 무작위 걸음을 다루는 내 프로그램의 스 니펫입니다. 내 프로그램의 다른 곳에서는 그래프를 만드는 메서드가 있고 필자가 작성한 다양한 사용자 지정 그래프 테스트 메서드를 시뮬레이트하는 메서드가 있습니다. 이 그래프 테스트 방법 중 하나는 그래프에서 두 노드를 무작위로 선택하고 두 노드 사이에서 임의의 보행을 실행합니다. 이 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를 사용하여이 임의의 워크에 대해 수행중인 작업 중 일부를 병렬화 할 수있는 방법이 있습니까? 무작위로 걸을 수있는 더 좋은 방법이 있습니까?

해결법

1. ==============================

   1.귀하의 질문에 답변하십시오 :

   귀하의 질문에 답변하십시오 :

   자, 특정 코드에 관해서는 ...

   또한보십시오

   편집 : Jesse Noller의 프리젠 테이션 및 Disco에 대한 링크가 포함되어 있습니다.

2. ==============================

   2.map-reduce가 당신을 도울 수있는 방법을 모르겠습니다. 첫 번째 부분은 많은 다른 데이터 요소에서 독립적으로 수행 할 수있는 계산이고 두 번째 부분은 어떻게 든 모든 결과를 결합하는 두 부분 연산을 사용하는 경우에 사용됩니다. 아마이 무작위 걸음을 돕기 위해 map-reduce를 사용하는 영리한 방법이 있지만 나는 그것을 보지 못합니다.

   map-reduce가 당신을 도울 수있는 방법을 모르겠습니다. 첫 번째 부분은 많은 다른 데이터 요소에서 독립적으로 수행 할 수있는 계산이고 두 번째 부분은 어떻게 든 모든 결과를 결합하는 두 부분 연산을 사용하는 경우에 사용됩니다. 아마이 무작위 걸음을 돕기 위해 map-reduce를 사용하는 영리한 방법이 있지만 나는 그것을 보지 못합니다.

   무작위 걸음은 완전히 무작위입니다. 계속 진행하기 전에 동일한 두 노드간에 앞뒤로 건너 뛰고 많은 루프가 생길 수 있습니다. 아마도 당신은 어떻게 든 그것을 제약하기를 원할 것입니다. 그래서 당신은 검색 할 공간이 너무 넓지는 않습니까?

3. ==============================

   3.이 백서에 설명 된 공식을 사용하면 실제로 무작위 걸음을 수행 할 필요가 없습니다.

   이 백서에 설명 된 공식을 사용하면 실제로 무작위 걸음을 수행 할 필요가 없습니다.

from https://stackoverflow.com/questions/1694237/mapreduce-python-and-networkx by cc-by-sa and MIT license