Algoritmo del coeficiente de agrupamiento local distribuido (MapReduce/Hadoop)

Question

Implementé el paradigma MapReduce basado en local clustering coefficient algorithm. Sin embargo, me he encontrado con problemas serios para conjuntos de datos más grandes o conjuntos de datos específicos (alto grado promedio de un nodo). Traté de ajustar mi plataforma hadoop y el código, sin embargo, los resultados fueron insatisfactorios (por decir lo menos). No, he vuelto mi atención para realmente cambiar/mejorar el algoritmo. A continuación es mi actual algoritmo (pseudo código)

foreach(Node in Graph) { 
    //Job1 
    /* Transform edge-based input dataset to node-based dataset */ 

    //Job2 
    map() { 
    emit(this.Node, this.Node.neighbours) //emit myself data to all my neighbours 
    emit(this.Node, this.Node) //emit myself to myself 
    } 

    reduce() { 
    NodeNeighbourhood nodeNeighbourhood; 
    while(values.hasNext) { 
     if(myself) 
     this.nodeNeighbourhood.setCentralNode(values.next) //store myself data 
     else 
     this.nodeNeighbourhood.addNeighbour(values.next) //store neighbour data 
    } 

    emit(null, this.nodeNeighbourhood) 
    } 

    //Job3 
    map() { 
    float lcc = calculateLocalCC(this.nodeNeighbourhood) 
    emit(0, lcc) //emit all lcc to specific key, combiners are used 
    } 

    reduce() { 
    float combinedLCC; 
    int numberOfNodes; 
    while(values.hasNext) { 
     combinedLCC += values.next; 
    } 

    emit(null, combinedLCC/numberOfNodes); // store graph average local clustering coefficient 
    } 
} 

poco más detalles sobre el código. Para los gráficos dirigidos, los datos vecinos están restringidos a ID de nodo y ID de destino de bordes OUT (para disminuir el tamaño de los datos), para su Id. De nodo e ID de destino de los bordes también. Los búferes de ordenación y fusión se han aumentado a 1.5 Gb, flujos de fusión 80.

Se puede ver claramente que Job2 es el problema real de todo el algoritmo. Genera una gran cantidad de datos que deben ser ordenados/copiados/fusionados. Esto básicamente mata el rendimiento de mi algoritmo para ciertos conjuntos de datos. ¿Puede alguien guiarme sobre cómo mejorar el algoritmo (estaba pensando en crear un Job2 iterativo ["procesar" solo M nodos de N en cada iteración hasta que cada nodo sea "procesado"], pero he abandonado esta idea por ahora) . En mi opinión, la salida del mapa de Job2 debería reducirse para evitar costosos procesos de clasificación/fusión, que matan el rendimiento.

También he implementado el mismo algoritmo (3 trabajos, el mismo patrón de "comunicación", también problema "Job2") para la plataforma Giraph. Sin embargo, Giraph es una plataforma en memoria y el algoritmo para los mismos conjuntos de datos "problemáticos" da como resultado una OutOfMemoryException.

Para cualquier comentario, comentario, guía, le agradeceré.

---

ACTUALIZACIÓN

voy a cambiar el algoritmo "drásticamente". Encontré este artículo Counting Triangles.

Una vez que se implemente el código, voy a publicar mi opinión aquí y un código más detallado (si este enfoque será exitoso).

---

UPDATE_2

Al final he terminado "modificar" NodeIterator algoritmo ++ para mis necesidades (papel Yahoo está disponible a través de un enlace en el artículo). Desafortunadamente, aunque puedo ver una mejora en el rendimiento, el resultado final no es tan bueno como esperaba. La conclusión a la que llegué es que el clúster que tengo disponible es demasiado pequeño para que los cálculos de LCC sean factibles para estos conjuntos de datos específicos. Entonces la pregunta permanece, o mejor dicho evoluciona. ¿Alguien sabe de un algoritmo eficiente distribuido/secuencial para calcular LCC o triángulos con recursos limitados disponibles? (De ninguna manera estoy diciendo que el algoritmo NodeIterator ++ es malo, simplemente declaro que los recursos que están disponibles para mí simplemente no son suficientes).

Answer 1

En el documento "MapReduce en MPI para algoritmos de gráficos a gran escala", los autores dan una descripción agradable de una implementación de MapReduce de recuento de triángulos. El documento está disponible aquí: http://www.sciencedirect.com/science/article/pii/S0167819111000172, pero es posible que necesite una cuenta para acceder al documento. (Estoy en un sistema de la Universidad que paga la suscripción, por lo que nunca sé a qué tengo acceso solo porque ya han pagado). Los autores pueden tener un borrador del documento publicado en los sitios web personales.

Hay otra forma de contar los triángulos, probablemente mucho menos eficiente a menos que el gráfico sea bastante denso. Primero, construye la matriz de adyacencia de tu gráfica, A. Luego calcula A^3 (podrías hacer la multiplicación de la matriz en paralelo con bastante facilidad). Luego, sume las (i, i) entradas de A^3 y divida la respuesta entre 6. Eso le dará el número de triángulos porque la entrada i, j de A^k cuenta el número de caminatas de longitud k de i j y dado que solo estamos buscando 3 caminatas de longitud, cualquier caminata que comience en i y termine en i después de 3 pasos es un triángulo ... contando por un factor de 6. Esto es principalmente menos eficiente porque el tamaño de la matriz será muy grande en comparación con el tamaño de un edgelist si su gráfico es escaso.