Graph particion algo con la base de datos de gráficos Neo4j

partitioning metis

Question

Sé que hay algunas herramientas de algoritmo de partición de gráficos famosas como METIS que está implementada por karypis Lab ( http://glaros.dtc.umn.edu/gkhome/metis/metis/overview )

pero quiero saber si hay algún método para particionar el gráfico almacenado en Neo4j. o tengo que volcar los datos del Neo4j y transformar el nodo y el formato de borde manualmente para que se ajusten al formato de entrada METIS?

Answer 1

Al haber trabajado de forma independiente con METIS y Neo4j en el pasado, no conozco ninguna herramienta para generar un archivo METIS de Neo4j. Dicho esto, escribir una herramienta de este tipo debería ser una tarea fácil y sería una gran contribución de la comunidad.

Otro enfoque para integrar METIS con Neo4j podría ser conectar METIS a Neo4j desde C ++ a través de JNI. Sin embargo, esto va a ser mucho más complicado, ya que tendría que ocuparse de cosas como transacciones, concurrencia, etc.

En la cuestión más general de los gráficos de particionamiento, es bastante posible implementar algunos de los algoritmos más conocidos y simples con un esfuerzo razonable.

Answer 2

En cuanto a los algoritmos nuevos e interesantes, esto no es exhaustivo ni de vanguardia, pero estos son los primeros lugares que buscaría:

Algoritmo Específico : DiDiC (Distributed Diffusive Clustering) - Lo usé una vez en mi tesis ( Partitioning Graph Databases )

• Usted itera sobre todos los nodos, luego para cada nodo recupera todos los vecinos, con el fin de difundir algo de "alguna unidad" a todos sus vecinos
• Fácil de implementar.
• Puede hacerse determinista
• Iterativo: como está basado en iteraciones (como Súper pasos en Pregel), puede detenerlo en cualquier momento. Cuanto más tiempo lo dejes, mejor será el resultado, en teoría (aunque en algunos casos, en ciertas formas de gráfico puede ser inestable)
• Cuando implementamos esto lo ejecutamos para 100 iteraciones en una máquina con ~ 30GB de RAM, para hasta ~ 4 millones de nodos, no tomó más de dos días en completarse.

Algoritmo específico : EvoCut "Encontrar cortes dispersos localmente utilizando conjuntos en evolución" - Algoritmo probabilístico local de Microsoft - relacionado con estos documentos

• Difícil de implementar
• Algoritmo local - Patrones de acceso tipo BFS (caminatas aleatorias)
• Ha pasado un tiempo desde que leí ese artículo, pero recuerdo que se basó en abstracciones limpias:
  • EvoNibble (enchufable: decide la cantidad de vecindad para agregar al clúster actual
  • EvoCut (llama a EvoNibble varias veces para encontrar el clúster local)
  • EvoPartition (llama a EvoCut repetidamente para particionar todo el gráfico)
• No determinista

Familia de algoritmo general : Agrupación jerárquica de gráficos

Desde un alto nivel:

• Coarsen el gráfico al colapsar los nodos en nodos agregados
  • estrategia de reducción de peso es seleccionable
• Encontrar clusters en el gráfico grueso / más pequeño
  • estrategia de agrupación es seleccionable
• Incrementalmente decoarsen el gráfico, refinando en la agrupación en cada paso
  • la estrategia de refinación es seleccionable

Notas:

• Si el gráfico cambia lentamente (o no es necesario que los resultados estén actualizados), es posible volver a engordar una vez (o con poca frecuencia) y luego trabajar con el gráfico grueso: para ahorrar cómputo.
• No sé de un algoritmo específico para recomendar

Limitaciones generales : las cosas que hacen pocos algoritmos de agrupamiento:

• Tipos de nodo no reconocidos, es decir, todos los nodos tratados por igual
• Tipos de relación no reconocidos, es decir, todas las relaciones reciben el mismo trato
• Dirección de la relación no reconocida - es decir, relaciones tratadas como no dirigidas