Encontrar componentes conectados usando Hadoop/MapReduce

Question

Necesito encontrar componentes conectados para un gran conjunto de datos. (El gráfico no está dirigido)

Una opción obvia es MapReduce. Pero soy un novato en MapReduce y tengo poco tiempo para recogerlo y codificarlo yo mismo.

Me preguntaba si existe alguna API para la misma ya que es un problema muy común en el Análisis de redes sociales.

O al menos si alguien conoce alguna fuente confiable (probada y probada) con la cual al menos puedo comenzar con la implementación yo mismo?

Gracias

Answer 1

realmente no saben si una API está disponible, que tiene métodos para encontrar componentes fuertemente conectados. Pero, implementé el algoritmo BFS para encontrar la distancia desde el nodo fuente a todos los demás nodos en el gráfico (el gráfico era un gráfico dirigido de hasta 65 millones de nodos).

La idea era explorar los vecinos (distancia de 1) para cada nodo en una iteración y alimentar la salida de reducir al mapa, hasta que las distancias convergen. El mapa emite las distancias más cortas posibles desde cada nodo y reduce la actualización del nodo con la distancia más corta desde la lista.

Yo sugeriría que marque this out. Además, this could help. Estos dos enlaces le darán la idea básica sobre los algoritmos de gráficos en el paradigma de reducción de mapas (si usted ya no está familiarizado). Esencialmente, debe girar el algoritmo para usar DFS en lugar de BFS.

Answer 2

blogged sobre él para mí mismo:

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

Pero MapReduce no es una buena opción para estas cosas análisis gráfico. Es mejor usar BSP (paralelo síncrono masivo) para eso, Apache Hama proporciona una buena API de gráficos sobre Hadoop HDFS.

He escrito un algoritmo de componentes conectados con MapReduce aquí: (MinDist búsqueda)

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

también una versión BSP para Apache Hama se puede encontrar aquí:

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

La implementación no es tan difícil como en MapReduce y es al menos 10 veces más rápida. Si está interesado, consulte la última versión en TRUNK y visite nuestra lista de correo.

http://hama.apache.org/

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

Answer 3

Es posible que desee ver en la Pegasus project de la Universidad Carnegie Mellon. Proporcionan una implementación eficiente y elegante con MapReduce. También proporcionan archivos binarios, muestras y una documentación muy detallada.

La implementación en sí misma se basa en la multiplicación general iterativa de matrices-vectores (GIM-V) propuesta por U Kang en 2009.

PEGASUS: A Peta-Scale Graph Mining System - Implementación y Observaciones T Kang, Charalampos E. Tsourakakis, Christos Faloutsos En IEEE Conferencia Internacional sobre Minería de Datos (ICDM 2009)

EDIT: La aplicación oficial es en realidad limita a 2.1 mil millones de nodos (id del nodo se almacenan como enteros). Estoy creando un fork en github (https://github.com/placeiq/pegasus) para compartir mi parche y otras mejoras (por ejemplo, compresión Snappy).

Answer 4

Es una vieja pregunta, pero aquí hay algo que quiere pagar. Implementamos el componente conectado usando map-reduce en la plataforma Spark.

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