Suchen von verbundenen Komponenten mit Hadoop/MapReduce

Question

Ich muss verbundene Komponenten für einen großen Datensatz finden. (Graph ist ungerichtet)

Eine offensichtliche Wahl ist MapReduce. Aber ich bin ein Neuling für MapReduce und habe keine Zeit, es aufzuheben und es selbst zu programmieren.

Ich habe mich gerade gefragt, ob es eine vorhandene API für das gleiche gibt, da es ein sehr häufiges Problem in der Analyse von sozialen Netzwerken ist?

Oder zumindest wenn jemand eine zuverlässige (erprobte) Quelle kennt, mit der ich zumindest mit der Implementierung beginnen kann?

Dank

Answer 1

Ich weiß nicht wirklich, wenn eine API zur Verfügung, welche Methoden stark verbundene Komponenten zu finden hat. Aber ich implementierte den BFS-Algorithmus, um den Abstand vom Quellknoten zu allen anderen Knoten im Graphen zu finden (der Graph war ein gerichteter Graph mit einer Größe von 65 Millionen Knoten).

Die Idee war, die Nachbarn (Entfernung von 1) für jeden Knoten in einer Iteration zu erkunden und die Ausgabe von reduzieren zurück zur Karte, bis die Entfernungen konvergieren. Die Karte sendet die kürzesten Entfernungen, die von jedem Knoten möglich sind, und reduziert den Knoten mit der kürzesten Entfernung von der Liste.

Ich würde vorschlagen zu überprüfen this out. Auch this could help. Diese beiden Links geben Ihnen die Grundidee zu Graphalgorithmen im Map Reduce Paradigma (wenn Sie sich nicht bereits auskennen). Im Wesentlichen müssen Sie den Algorithmus verdrehen, um DFS anstelle von BFS zu verwenden.

Answer 2

ich gebloggt es für mich:

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

Aber MapReduce ist nicht eine gute Passform für diese Analyse der Graphik Dinge. Besser verwenden Sie BSP (Bulk-synchrone Parallele), Apache Hama bietet eine gute Graph-API zusätzlich zu Hadoop HDFS.

Ich habe einen angeschlossenen Komponenten Algorithmus mit MapReduce hier geschrieben: (MinDist Suche)

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

Auch kann eine BSP-Version für Apache Hama hier:

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

Die Implementierung ist nicht so schwierig wie in MapReduce und es ist mindestens 10 mal schneller. Wenn Sie interessiert sind, überprüfen Sie die neueste Version in TRUNK und besuchen Sie unsere Mailingliste.

http://hama.apache.org/

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

Answer 3

Sie können an der Pegasus project von der Carnegie Mellon University zu suchen. Sie bieten eine effiziente - und elegante - Implementierung mit MapReduce. Sie bieten auch Binärdateien, Beispiele und eine sehr detaillierte Dokumentation.

Die Implementierung selbst basiert auf der 2009 von U Kang vorgeschlagenen Verallgemeinerten Iterativen Matrix-Vektor-Multiplikation (GIM-V).

PEGASUS: A Peta-Scale Graph Mining System - Implementierung und Beobachtungen U Kang, Charalampos E. Tsourakakis, Christos Faloutsos In IEEE International Conference on Data Mining (ICDM 2009)

EDIT: Die offizielle Implementierung ist tatsächlich begrenzt auf 2,1 Milliarden Knoten (Knoten-ID werden als Ganzzahlen gespeichert). Ich erstelle eine Gabel auf Github (https://github.com/placeiq/pegasus), um meinen Patch und andere Verbesserungen (zB. Snappy-Komprimierung) zu teilen.

Answer 4

Es ist eine kleine alte Frage, aber hier ist etwas, was Sie auschecken möchten. Wir haben die verbundene Komponente mithilfe von map-reduce auf der Spark-Plattform implementiert.

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