performance - Algoritmo de coeficiente de agrupamiento local distribuido(MapReduce/Hadoop)

algorithm graph

Question

He implementado el algoritmo de coeficiente de agrupamiento local basado en el paradigma de MapReduce. Sin embargo, me he encontrado con serios problemas para conjuntos de datos más grandes o conjuntos de datos específicos (alto grado promedio de un nodo). Intenté ajustar mi plataforma hadoop y el código, sin embargo, los resultados no fueron satisfactorios (por decir lo menos). No, he centrado mi atención en cambiar / mejorar el algoritmo. A continuación se muestra mi algoritmo actual (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 adyacentes se restringen a los ID de nodo y los ID de destino de los bordes OUT (para disminuir el tamaño de los datos), y para los no dirigidos también se identifican los ID de nodo y de destino de los bordes. Los buffers de clasificación y fusión se incrementan a 1.5 Gb, fusionando las secuencias 80.

Se puede ver claramente que Job2 es el problema real de todo el algoritmo. Genera una gran cantidad de datos que deben ordenarse / copiarse / fusionarse. Básicamente, esto mata el rendimiento de mi algoritmo para ciertos conjuntos de datos. Alguien me puede guiar sobre cómo mejorar el algoritmo (estaba pensando en crear un trabajo iterativo2 ["procesar" solo M nodos fuera de N en cada iteración hasta que cada nodo esté "procesado"], pero por el momento he abandonado esta idea) . En mi opinión, el mapa-salida de Job2 debería reducirse, para evitar procesos costosos de ordenación / fusión, que destruyen el rendimiento.

También he implementado el mismo algoritmo (3 trabajos también, el mismo patrón de "comunicación", también problema "Trabajo2") 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 excepción OutOfMemoryException.

Para cualquier comentario, comentario, pauta estaré agradecido.

ACTUALIZAR

Voy a cambiar el algoritmo "drásticamente". He encontrado este artículo Contando Triángulos .

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

Actualización_2

Al final, he terminado de "modificar" el algoritmo NodeIterator ++ según mis necesidades (el artículo de 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 he llegado es que el grupo que está disponible para mí 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 más bien evoluciona. ¿Alguien sabe de un algoritmo distribuido / secuencial eficiente para calcular LCC o triángulos con recursos limitados disponibles? (De ninguna manera estoy afirmando que el algoritmo NodeIterator ++ es malo, simplemente afirmo 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 proporcionan una descripción agradable de una implementación de MapReduce del conteo 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 universitario que paga por la suscripción, por lo que nunca sé a qué solo tengo acceso porque ya pagaron). Los autores pueden tener un borrador del documento publicado en el (los) sitio (s) web personal (es).

Hay otra forma de contar los triángulos, probablemente mucho menos eficiente a menos que su gráfica sea bastante densa. 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 entradas (i, i) 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 longitud que k va desde i Para j, y como solo observamos las caminatas de longitud 3, cualquier caminata que comience en i y termine en i después de 3 pasos es un triángulo ... recuento por un factor de 6. Esto es principalmente menos eficiente debido a que 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.