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 aufzunehmen und selbst zu programmieren.
Ich habe mich gerade gefragt, ob es eine API für dasselbe gibt, da es ein sehr häufiges Problem in der Analyse sozialer Netzwerke ist.
Oder zumindest, wenn jemand eine zuverlässige (erprobte) Quelle kennt, mit der ich zumindest selbst mit der Implementierung beginnen kann?
Danke
Ich habe darüber selbst gebloggt:
Aber MapReduce passt nicht gut zu diesen Graph-Analyse-Dingen. Besser verwenden Sie BSP (Bulk-synchrone Parallele) dafür Apache Hama bietet eine gute Grafik-API über Hadoop HDFS.
Ich habe hier einen Algorithmus für verbundene Komponenten mit MapReduce geschrieben: (Mindist-Suche)
Auch eine BSP-Version für Apache Hama finden Sie hier:
Die Implementierung ist nicht so schwierig wie in MapReduce und ist mindestens 10-mal schneller. Wenn Sie interessiert sind, überprüfen Sie die neueste Version in TRUNK und besuchen Sie unsere Mailingliste.
Ich weiß nicht wirklich, ob eine API verfügbar ist, die Methoden hat, stark verbundene Komponenten zu finden. Aber ich implementierte den BFS-Algorithmus, um die Entfernung 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 untersuchen und die Ausgabe von reduce zurück zur Karte zu führen, 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, dies . Außerdem könnte dies helfen . 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.
Vielleicht möchten Sie sich das Pegasus-Projekt von der Carnegie Mellon University ansehen. 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 von U Kang 2009 vorgeschlagenen Verallgemeinerten Iterativen Matrix-Vektor-Multiplikation (GIM-V).
PEGASUS: Ein Peta-Scale-Graph-Mining-System - Implementierung und Beobachtungen U Kang, Charalampos E. Tsorakakis, Christos Faloutsos IEEE Internationale Konferenz für Data Mining (ICDM 2009)
BEARBEITEN: Die offizielle Implementierung ist tatsächlich auf 2,1 Milliarden Knoten beschränkt (Knoten-ID werden als Ganzzahlen gespeichert). Ich erstelle einen Fork auf Github ( Ссылка ), um meinen Patch und andere Verbesserungen (z. B. Snappy-Komprimierung) zu teilen.
>Es ist eine kleine alte Frage, aber hier ist etwas, was Sie auschecken möchten. Wir haben die verbundene Komponente mit map-reduce auf der Spark-Plattform implementiert.
Tags und Links hadoop mapreduce graph-algorithm graph social-networking