[HADOOP] Hadoop / MapReduce를 사용하여 연결된 구성 요소 찾기

Hadoop / MapReduce를 사용하여 연결된 구성 요소 찾기

거대한 데이터 세트에 연결된 구성 요소를 찾아야합니다. (그래프가 우회 됨)

한 가지 확실한 선택은 MapReduce입니다. 그러나 나는 MapReduce의 초보자이며, 그것을 집어 들고 스스로 코드를 작성하는 데 시간이 부족합니다.

소셜 네트워크 분석에서 매우 일반적인 문제이므로 동일한 API가 있는지 궁금한 점이 있습니까?

아니면 적어도 누군가가 믿을만한 (시도하고 테스트 한) 소스를 사용하고 적어도 내가 직접 구현을 시작할 수 있는지 알고 있습니까?

감사

해결법

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

   1.나는 나 자신을 위해 그것에 관하여 blogged했다 :

   나는 나 자신을 위해 그것에 관하여 blogged했다 :

   http://codingwiththomas.blogspot.de/2011/04/graph-exploration-with-hadoop-mapreduce.html

   그러나 MapReduce는 이러한 그래프 분석 작업에 적합하지 않습니다. BSP (bulk synchronous parallel)를 사용하면 Apache Hama는 Hadoop HDFS 위에 훌륭한 그래프 API를 제공합니다.

   MapReduce를 사용하여 연결된 구성 요소 알고리즘을 작성했습니다 (Mindist 검색).

   https://github.com/thomasjungblut/tjungblut-graph/tree/master/src/de/jungblut/graph/mapreduce

   또한 Apache Hama의 BSP 버전은 다음에서 찾을 수 있습니다.

   https://github.com/thomasjungblut/tjungblut-graph/blob/master/src/de/jungblut/graph/bsp/MindistSearch.java

   구현은 MapReduce만큼 어렵지 않으며 적어도 10 배 더 빠릅니다. 관심이 있으시면 TRUNK에서 최신 버전을 확인하고 메일 링리스트를 방문하십시오.

   http://hama.apache.org/

   http://apache.org/hama/mail-lists.html

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

   2.강하게 연결된 구성 요소를 찾을 수있는 방법이있는 API를 사용할 수 있는지 잘 모르겠습니다. 그러나 BFS 알고리즘을 구현하여 소스 노드에서 다른 모든 노드까지의 거리를 그래프로 나타 냈습니다 (그래프는 6 천 5 백만 노드의 큰 그래프였습니다).

   강하게 연결된 구성 요소를 찾을 수있는 방법이있는 API를 사용할 수 있는지 잘 모르겠습니다. 그러나 BFS 알고리즘을 구현하여 소스 노드에서 다른 모든 노드까지의 거리를 그래프로 나타 냈습니다 (그래프는 6 천 5 백만 노드의 큰 그래프였습니다).

   아이디어는 한 번의 반복에서 각 노드에 대해 이웃 노드 (거리 1)를 탐색하고 거리가 수렴 될 때까지 축소 출력을지도에 제공하는 것이 었습니다. 지도는 각 노드에서 가능한 한 최단 거리를 방출하고 목록에서 최단 거리로 노드를 업데이트합니다.

   나는 이것을 확인하는 것이 좋습니다. 또한 도움이 될 수 있습니다. 이 두 링크는지도의 그래프 알고리즘에 대한 기본 아이디어를 제공합니다 (이미 익숙하지 않은 경우). 본질적으로 BFS 대신 DFS를 사용하려면 알고리즘을 왜곡해야합니다.

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

   3.Carnegie Mellon University의 Pegasus 프로젝트를 살펴볼 수 있습니다. MapReduce를 사용하여 효율적이고 우아한 구현을 제공합니다. 또한 바이너리, 샘플 및 매우 자세한 문서를 제공합니다.

   Carnegie Mellon University의 Pegasus 프로젝트를 살펴볼 수 있습니다. MapReduce를 사용하여 효율적이고 우아한 구현을 제공합니다. 또한 바이너리, 샘플 및 매우 자세한 문서를 제공합니다.

   구현 자체는 2009 년 U Kang이 제안한 GIM-V (Generalized Iterative Matrix-Vector) 곱셈을 기반으로합니다.

   편집하다: 공식 구현은 실제로 2.1 억 개의 노드로 제한됩니다 (노드 ID는 정수로 저장됩니다). github (https://github.com/placeiq/pegasus)에 포크를 만들어 내 패치와 다른 향상된 기능 (예 : 명랑한 압축)을 공유합니다.

4. ==============================

   4.조금 낡은 질문이지만 여기에 체크 아웃 할 항목이 있습니다. Spark 플랫폼에서 map-reduce를 사용하여 연결된 구성 요소를 구현했습니다.

   조금 낡은 질문이지만 여기에 체크 아웃 할 항목이 있습니다. Spark 플랫폼에서 map-reduce를 사용하여 연결된 구성 요소를 구현했습니다.

   https://github.com/kwartile/connected-component

from https://stackoverflow.com/questions/10677388/finding-connected-components-using-hadoop-mapreduce by cc-by-sa and MIT license