¿Guardando gráficos muy grandes en algoritmos de partición de gráficos de disco/transmisión?

Question

Supongamos que tengo un gran gráfico no ponderado, no ponderado (que comienza en cientos de millones de vértices, ~ 10 aristas por vértice), no distribuido y procesado solo por un solo subproceso y que deseo hacer búsquedas amplias en él . Espero que estén vinculados a E/S, por lo tanto, necesito un diseño de página de disco bueno para BFS, el espacio en disco no es un problema. Las búsquedas pueden comenzar en cada vértice con la misma probabilidad. Intuitivamente eso significa minimizar el número de bordes entre vértices en diferentes páginas de disco, que es un problema de partición de gráfico.

El gráfico en sí parece un espagueti, piense en un conjunto aleatorio de puntos interconectados al azar, con algunos sesgos hacia los bordes más cortos.

El problema es, ¿cómo una partición grafica así de grande? Los particionadores de gráficos disponibles que he encontrado funcionan con gráficos que se ajustan solo a la memoria. No pude encontrar descripciones ni implementaciones de ningún algoritmo de partición de gráficos de transmisión.

O, tal vez hay una alternativa al gráfico de particionamiento para obtener un diseño de disco que funciona bien con BFS?

Ahora como una aproximación utilizo el hecho de que los vértices tienen coordenadas espaciales adjuntas a ellos y pongo los vértices en el disco en el orden de clasificación de Hilbert. De esta forma, los vértices espacialmente cercanos aterrizan en la misma página, pero la presencia o ausencia de borde entre ellos se ignora por completo. ¿Puedo hacerlo mejor?

Como alternativa, puedo dividir el gráfico en partes utilizando el orden de clasificación de Hilbert para los vértices, particionar los subgrafos, coserlos hacia atrás y aceptar particiones pobres en las costuras.

Algunas cosas que han estudiado ya:

1. How to store a large directed unweighted graph with billions of nodes and vertices
2. http://neo4j.org/ - me encontré con cero información sobre cómo lo hace el gráfico trazado en el disco

implementaciones de partición (a menos que esté equivocado, todos ellos deben ajustar el gráfico en la memoria):

1. http://glaros.dtc.umn.edu/gkhome/views/metis
2. http://www.sandia.gov/~bahendr/chaco.html
3. http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/
4. http://www.cerfacs.fr/algor/Softs/MESHPART/

EDIT: información sobre cómo los gráficos se parece y que BFS puede comenzar por todas partes. EDITAR: idea en los subgrafos de particionamiento

Answer 1

Ningún algoritmo realmente necesita "encajar en la memoria": siempre puede ingresar y sacar las páginas según sea necesario. Pero desea evitar que el cálculo tarde demasiado tiempo, y la partición global de gráficos en el caso genérico es un problema NP completo, que es "irracionalmente largo" para la mayoría de los problemas que ni siquiera caben en la memoria.

Afortunadamente, desea realizar búsquedas amplias, lo que significa que desea un formato en el que la amplitud de primer grado sea el cálculo sencillo. No conozco ningún algoritmo que haga esto, pero puede construir su propio diseño de amplitud si está dispuesto a permitir un poco de espacio adicional en el disco.

Si los bordes no están sesgados hacia las interacciones locales, entonces desenredar el gráfico será difícil. Si están sesgados hacia las interacciones locales, entonces sugiero un algoritmo como el siguiente:

• Elija un conjunto aleatorio de vértices como puntos de partida a lo largo de todo el conjunto de datos.
• Para cada vértice, recoge todos los vértices vecinos (realiza un barrido a través del conjunto de datos).
• Para cada conjunto de vértices vecinos, recolecte el conjunto de vecinos-de-vecinos y clasifíquelos según la cantidad de bordes que se conecten a ellos. Si no tiene espacio en una página para almacenarlos todos, mantenga los vértices más conectados. Si tiene espacio para guardarlos todos, puede desechar los menos útiles (por ejemplo, si la fracción de bordes mantenida dentro de una página/fracción de vértices que necesita una relación de almacenamiento cae "demasiado baja", donde "demasiado baja") dependerá de cuánta amplitud necesiten realmente sus búsquedas, y de si puede hacer una poda, etc., entonces no incluya las del barrio.
• Repita el proceso de recopilación y clasificación de vecinos hasta que su vecindario esté lleno (por ejemplo, rellena el tamaño de página que más le convenga). Luego, compruebe si hay repeticiones entre los inicios elegidos al azar. Si tiene un pequeño número de vértices en ambos, elimínelos de uno u otro, lo que menos rompa los bordes. número de vértices que aparecen en ambos, mantenga el vecindario con la mejor relación (vértices en el vecindario/borde roto) y arroje el otro.

Ahora tiene algunos vecindarios locales que son aproximadamente óptimos a nivel local, ya que las primeras búsquedas tienden a quedar dentro. Si su búsqueda de amplitud elimina las ramas improductivas con bastante eficacia, entonces esto es probablemente lo suficientemente bueno. De lo contrario, es probable que desee que los vecindarios adyacentes se agrupen.

Si no necesita que los barrios adyacentes se agrupen demasiado, separe los vértices que ha agrupado en barrios y repita el proceso en los datos restantes hasta que se tengan en cuenta todos los vértices. Cambia cada identificador de vértice a (vértice, vecindario), y listo: cuando sigue los bordes, sabe exactamente qué página tomar, y la mayoría de ellos estarán cerca dada la construcción.

Si necesita vecindarios adyacentes, tendrá que hacer un seguimiento de sus barrios en crecimiento. Repite el proceso anterior (elige al azar, crece vecindarios), pero ahora clasifica a los vecinos según la cantidad de bordes que satisfacen dentro del vecindario y qué fracción de sus bordes que salen del vecindario están en un grupo existente. Es posible que necesite factores de ponderación, pero algo como

score = (# edges within) - (# neighborhoods outside) - (# neighborhoodless edges outside) 

probablemente lo solucionará.

Ahora bien, esto es no a nivel mundial o incluso localmente óptima, pero esto o algo muy parecido a él debería darle una estructura muy bien conectada localmente, y debe dejar a producir un conjunto de cubierta de los barrios que tienen relativamente alta interconectividad.

De nuevo, depende de si su búsqueda de amplitud prunes ramas o no. Si lo hace, lo más barato es maximizar la interconectividad local. Si no es lo que hay que hacer, es minimizar la conectividad externa, y en ese caso, sugeriría simplemente recopilar conjuntos de ancho hasta cierto tamaño y guardarlos (con duplicación en los bordes de los conjuntos). no está muy limitado por el espacio en el disco duro, ¿verdad?).

Answer 2

Es posible que desee consultar HDF5. A pesar de que H representa jerárquico, puede almacenar gráficos, verificar la documentación bajo la palabra clave "Grupos" y está diseñado para conjuntos de datos muy grandes. Si entiendo correctamente, los 'archivos' de HDF5 pueden extenderse a través de múltiples 'o' s 'archivos'. Ahora, HDF5 es solo una estructura de datos, más un conjunto de bibliotecas para manipulaciones de bajo y alto nivel de la estructura de datos. De repente, no tengo ni idea acerca de la transmisión de algoritmos de partición de gráficos, pero me atengo a la idea de que si obtienes la estructura de datos, los algoritmos correctos serán más fáciles de implementar.

¿Qué es lo que ya sabes sobre el mega-gráfico? ¿Se divide naturalmente en subgrafos densos que a su vez están escasamente conectados?¿Sería un tipo topológico del gráfico una mejor base para el almacenamiento en disco que el ordenamiento espacial existente?

Respondiendo respuestas nítidas a tales preguntas, tal vez solo tenga que morder la bala y leer el gráfico varias veces para construir las particiones, en cuyo caso solo quiere la E/S más rápida que pueda administrar y un diseño sofisticado de las particiones en los nodos es bueno, pero no tan importante. Si puede dividir el gráfico en subgráficos que tienen bordes individuales para los otros subgráficos, tal vez pueda hacer que el problema sea más manejable.

Desea un diseño bueno para BFS, pero BFS generalmente se aplica a árboles. ¿Su gráfico tiene una raíz única desde la que iniciar todos los BFS? De lo contrario, el diseño de BFS desde un vértice no será óptimo para BFS desde otro vértice.

Answer 3

Comprobar esta entrada del blog:

"búsqueda gráfica en amplitud utilizando un mapa-algoritmo iterativo reducir"

http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm