Znajdowanie połączonych komponentów przy użyciu Hadoop/MapReduce

Question

Potrzebuję znaleźć podłączone komponenty dla ogromnego zestawu danych. (Wykres jest nieukierunkowany)

Jednym z oczywistych wyborów jest MapReduce. Ale jestem nowicjuszem MapReduce i mam dość czasu, aby go odebrać i samemu go zakodować.

Zastanawiam się, czy istnieje istniejący interfejs API dla tego samego, ponieważ jest to bardzo powszechny problem w analizie sieci społecznościowej?

Co najmniej, jeśli ktoś jest świadomy jakiegokolwiek wiarygodnego (wypróbowanego) źródła, za pomocą którego co najmniej mogę samemu zacząć wdrażanie?

Dzięki

Answer 1

ja naprawdę nie wiem, czy API jest dostępny która ma metody, aby znaleźć silnie powiązane komponenty. Ale zaimplementowałem algorytm BFS, aby znaleźć odległość od węzła źródłowego do wszystkich innych węzłów na wykresie (wykres był grafem skierowanym do 65 milionów węzłów).

Chodziło o to, aby zbadać sąsiadów (odległość 1) dla każdego węzła w jednej iteracji i podać wynik redukcji z powrotem do mapy, aż odległości się zbiegną. Mapa emituje najkrótsze odległości możliwe z każdego węzła i zmniejsza aktualizację węzła o najkrótszą odległość od listy.

Proponuję sprawdzić this out. Ponadto, this could help. Te dwa łącza dadzą ci podstawową wiedzę na temat algorytmów graficznych w paradygmacie zmniejszania mapy (jeśli nie jesteś już zaznajomiony). Zasadniczo trzeba przekręcić algorytm, aby używać DFS zamiast BFS.

Answer 2

I napisał o tym na własne oczy:

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

Ale MapReduce nie jest dobrym rozwiązaniem dla tych rzeczy analizy wykresu. Lepiej użyj BSP (bulk synchronous parallel) do tego, Apache Hama zapewnia dobre API grafów na Hadoop HDFS.

Pisałem algorytmu podłączonych komponentów z MapReduce tutaj: (wyszukiwarki Mindist)

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

również wersja BSP dla Apache Hama można znaleźć tutaj:

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

Implementacja nie jest tak trudna jak w MapReduce i jest co najmniej 10 razy szybsza. Jeśli jesteś zainteresowany, sprawdź najnowszą wersję w TRUNK i odwiedź naszą listę mailingową.

http://hama.apache.org/

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

Answer 3

Możesz zajrzeć na Pegasus project z Carnegie Mellon University. Zapewniają wydajną i elegancką implementację za pomocą MapReduce. Zapewniają także pliki binarne, próbki i bardzo szczegółową dokumentację.

Sama implementacja oparta jest na Mnożonej Iteratywnej Mnożnikowej Wektorowej (GIM-V) zaproponowanej przez U Kanga w 2009 roku.

PEGASUS: A Peta-Scale Graph Mining System - Wdrożenie i Obserwacje U Kang, Charalampos E. Tsourakakis Christos Faloutsos W IEEE International Conference on Data Mining (ICDM 2009)

EDIT: Oficjalna realizacja rzeczywiście ogranicza się do 2,1 miliardy węzłów (identyfikator węzła są przechowywane jako liczby całkowite). Tworzę widelec na github (https://github.com/placeiq/pegasus), aby udostępnić mój patch i inne ulepszenia (np. Kompresja Snappy).

Answer 4

To trochę stare pytanie, ale tutaj jest coś, co chcesz do kasy. Zaimplementowaliśmy podłączony komponent za pomocą map-reduce na platformie Spark.

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