Partición de gráficos

Subdivisión de vértices en conjuntos disjuntos

En matemáticas, una partición de grafos es la reducción de un grafo a un grafo más pequeño al particionar su conjunto de nodos en grupos mutuamente excluyentes. Los bordes del grafo original que se cruzan entre los grupos producirán bordes en el grafo particionado. Si el número de bordes resultantes es pequeño en comparación con el grafo original, entonces el grafo particionado puede ser más adecuado para el análisis y la resolución de problemas que el original. Encontrar una partición que simplifique el análisis de grafos es un problema difícil, pero que tiene aplicaciones en la computación científica, el diseño de circuitos VLSI y la programación de tareas en computadoras multiprocesador, entre otros. ^[1] Recientemente, el problema de la partición de grafos ha ganado importancia debido a su aplicación para la agrupación y detección de camarillas en redes sociales, patológicas y biológicas. Para una encuesta sobre las tendencias recientes en métodos computacionales y aplicaciones, consulte Buluc et al. ^[2] Dos ejemplos comunes de partición de grafos son los problemas de corte mínimo y corte máximo .

Complejidad del problema

Por lo general, los problemas de partición de grafos caen dentro de la categoría de problemas NP-hard . Las soluciones a estos problemas generalmente se derivan usando heurísticas y algoritmos de aproximación. ^[3] Sin embargo, se puede demostrar que la partición uniforme de grafos o un problema de partición de grafos balanceado es NP-completo para aproximarse dentro de cualquier factor finito. ^[1] Incluso para clases de grafos especiales como árboles y cuadrículas, no existen algoritmos de aproximación razonables, ^[4] a menos que P=NP . Las cuadrículas son un caso particularmente interesante ya que modelan los grafos resultantes de simulaciones de Modelo de Elementos Finitos (FEM) . Cuando no solo se aproxima el número de aristas entre los componentes, sino también los tamaños de los componentes, se puede demostrar que no existen algoritmos completamente polinomiales razonables para estos grafos. ^[4]

Problema

Considere un grafo G = ( V , E ), donde V denota el conjunto de n vértices y E el conjunto de aristas. Para un problema de partición balanceada ( k , v ), el objetivo es particionar G en k componentes de tamaño v · ( n / k ), como máximo , mientras se minimiza la capacidad de las aristas entre componentes separados. ^[1] Además, dado G y un entero k > 1, particione V en k partes (subconjuntos) V ₁ , V ₂ , ..., V _k tales que las partes sean disjuntas y tengan el mismo tamaño, y se minimice el número de aristas con puntos finales en diferentes partes. Tales problemas de partición se han discutido en la literatura como aproximaciones de bicriterio o de aumento de recursos. Una extensión común es la de los hipergrafos , donde una arista puede conectar más de dos vértices. Una hiperarista no se corta si todos los vértices están en una partición, y se corta exactamente una vez en caso contrario, sin importar cuántos vértices haya en cada lado. Este uso es común en la automatización del diseño electrónico .

Análisis

Para un problema específico de partición balanceada ( k , 1 +  ε ), buscamos encontrar una partición de costo mínimo de G en k componentes con cada componente conteniendo un máximo de (1 +  ε )·( n / k ) nodos. Comparamos el costo de este algoritmo de aproximación con el costo de un corte ( k ,1), donde cada uno de los k componentes debe tener el mismo tamaño de ( n / k ) nodos cada uno, siendo así un problema más restringido. Por lo tanto,

${\displaystyle \max _{i}|V_{i}|\leq (1+\varepsilon )\left\lceil {\frac {|V|}{k}}\right\rceil .}$

Ya sabemos que el corte (2,1) es el problema de bisección mínima y es NP-completo. ^[5] A continuación, evaluamos un problema de 3 particiones donde n  = 3 k , que también está acotado en tiempo polinomial. ^[1] Ahora, si suponemos que tenemos un algoritmo de aproximación finito para la partición ( k , 1)-balanceada, entonces, o bien la instancia de 3 particiones se puede resolver usando la partición ( k ,1)-balanceada en G o no se puede resolver. Si la instancia de 3 particiones se puede resolver, entonces el problema de partición ( k , 1)-balanceada en G se puede resolver sin cortar ninguna arista. De lo contrario, si la instancia de 3 particiones no se puede resolver, la partición ( k , 1)-balanceada óptima en G cortará al menos una arista. Un algoritmo de aproximación con un factor de aproximación finito tiene que diferenciar entre estos dos casos. Por lo tanto, puede resolver el problema de 3 particiones, lo cual es una contradicción bajo el supuesto de que P  =  NP . Por lo tanto, es evidente que el problema de partición balanceado ( k ,1) no tiene un algoritmo de aproximación de tiempo polinomial con un factor de aproximación finito a menos que P  =  NP . ^[1]

El teorema del separador planar establece que cualquier grafo planar de n vértices se puede dividir en partes aproximadamente iguales mediante la eliminación de O( √ n ) vértices. Esto no es una partición en el sentido descrito anteriormente, porque el conjunto de particiones consta de vértices en lugar de aristas. Sin embargo, el mismo resultado también implica que todo grafo planar de grado acotado tiene un corte equilibrado con O( √ n ) aristas.

Métodos de partición de gráficos

Dado que la partición de grafos es un problema difícil, las soluciones prácticas se basan en heurísticas. Hay dos amplias categorías de métodos, locales y globales. Los métodos locales bien conocidos son el algoritmo de Kernighan-Lin y los algoritmos de Fiduccia-Mattheyses , que fueron los primeros cortes de dos vías efectivos mediante estrategias de búsqueda local. Su principal inconveniente es la partición inicial arbitraria del conjunto de vértices, que puede afectar la calidad de la solución final. Los enfoques globales se basan en propiedades de todo el grafo y no dependen de una partición inicial arbitraria. El ejemplo más común es la partición espectral, donde una partición se deriva de vectores propios aproximados de la matriz de adyacencia, o la agrupación espectral que agrupa los vértices del grafo utilizando la descomposición propia de la matriz laplaciana del grafo .

Métodos multinivel

Un algoritmo de partición de gráficos multinivel funciona aplicando una o más etapas. Cada etapa reduce el tamaño del gráfico colapsando vértices y aristas, particiona el gráfico más pequeño, luego vuelve a mapear y refina esta partición del gráfico original. ^[6] Se puede aplicar una amplia variedad de métodos de partición y refinamiento dentro del esquema multinivel general. En muchos casos, este enfoque puede brindar tiempos de ejecución rápidos y resultados de muy alta calidad. Un ejemplo ampliamente utilizado de dicho enfoque es METIS , ^[7] un particionador de gráficos, y hMETIS, el particionador correspondiente para hipergrafos. ^[8] Un enfoque alternativo originado en ^[9] e implementado, por ejemplo, en scikit-learn es el agrupamiento espectral con la partición determinada a partir de vectores propios de la matriz laplaciana del gráfico para el gráfico original calculado por el solucionador LOBPCG con preacondicionamiento multigrid .

Partición espectral y bisección espectral

Dado un gráfico con matriz de adyacencia , donde una entrada implica una arista entre el nodo y , y matriz de grado , que es una matriz diagonal, donde cada entrada diagonal de una fila , , representa el grado del nodo del nodo . La matriz laplaciana se define como . Ahora, una partición de corte de razón para un gráfico se define como una partición de en disjuntos , y , minimizando la razón ${\displaystyle G=(V,E)}$ ${\displaystyle A}$ ${\displaystyle A_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle D}$ ${\displaystyle i}$ ${\displaystyle d_{ii}}$ ${\displaystyle i}$ ${\displaystyle L}$ ${\displaystyle L=D-A}$ ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle W}$

${\displaystyle {\frac {|E(G)\cap (U\times W)|}{|U|\cdot |W|}}}$

del número de aristas que realmente cruzan este corte al número de pares de vértices que podrían soportar dichas aristas. La partición de gráficos espectrales puede motivarse ^[10] por analogía con la partición de una cuerda vibrante o un sistema de masa-resorte y extenderse de manera similar al caso de pesos negativos del gráfico. ^[11]

Valor propio y vector propio de Fiedler

En tal escenario, el segundo valor propio más pequeño ( ) de , produce un límite inferior en el costo óptimo ( ) de la partición de corte de razón con . El vector propio ( ) correspondiente a , llamado vector de Fiedler , biseca el gráfico en solo dos comunidades según el signo de la entrada del vector correspondiente . La división en un mayor número de comunidades se puede lograr mediante bisecciones repetidas o utilizando múltiples vectores propios correspondientes a los valores propios más pequeños. ^[12] Los ejemplos en las Figuras 1,2 ilustran el enfoque de bisección espectral. ${\displaystyle \lambda _{2}}$ ${\displaystyle L}$ ${\displaystyle c}$ ${\displaystyle c\geq {\frac {\lambda _{2}}{n}}}$ ${\displaystyle V_{2}}$ ${\displaystyle \lambda _{2}}$

Figura 1: Se analiza el gráfico G  = (5,4) para determinar la bisección espectral. La combinación lineal de los dos vectores propios más pequeños da como resultado que [1 1 1 1 1]' tenga un valor propio = 0.

Figura 2: El gráfico G  = (5,5) ilustra que el vector de Fiedler en rojo divide el gráfico en dos comunidades, una con vértices {1,2,3} con entradas positivas en el espacio vectorial, y la otra comunidad tiene vértices {4,5} con entradas negativas en el espacio vectorial.

Modularidad y ratio-corte

Sin embargo, la partición de corte mínimo falla cuando se desconoce el número de comunidades a dividir o los tamaños de partición. Por ejemplo, optimizar el tamaño de corte para tamaños de grupos libres coloca todos los vértices en la misma comunidad. Además, el tamaño de corte puede ser lo incorrecto para minimizar, ya que una buena división no es solo una con un pequeño número de aristas entre comunidades. Esto motivó el uso de Modularidad (Q) ^[13] como una métrica para optimizar una partición de grafos balanceada. El ejemplo en la Figura 3 ilustra 2 instancias del mismo grafo de manera que en (a) la modularidad (Q) es la métrica de partición y en (b) , el corte de proporción es la métrica de partición.

Figura 3: El gráfico ponderado G puede dividirse para maximizar Q en (a) o para minimizar el corte de proporción en (b). Vemos que (a) es una partición mejor equilibrada, lo que justifica la importancia de la modularidad en los problemas de división de gráficos.

Aplicaciones

Conductancia

Otra función objetivo utilizada para la partición de grafos es la conductancia , que es la relación entre el número de aristas cortadas y el volumen de la parte más pequeña. La conductancia está relacionada con los flujos eléctricos y los recorridos aleatorios. El límite de Cheeger garantiza que la bisección espectral proporcione particiones con una conductancia casi óptima. La calidad de esta aproximación depende del segundo valor propio más pequeño del laplaciano λ ₂ .

Inmunización

La partición de gráficos puede ser útil para identificar el conjunto mínimo de nodos o enlaces que deben inmunizarse para detener epidemias. ^[14]

Otros métodos de partición de gráficos

Los modelos de espín se han utilizado para la agrupación de datos multivariados en los que las similitudes se traducen en fortalezas de acoplamiento. ^[15] Las propiedades de la configuración de espín del estado fundamental se pueden interpretar directamente como comunidades. Por lo tanto, un gráfico se particiona para minimizar el hamiltoniano del gráfico particionado. El hamiltoniano (H) se deriva asignando las siguientes recompensas y penalizaciones de partición.

• Recompensar los bordes internos entre nodos del mismo grupo (mismo giro)
• Penalizar los bordes faltantes en el mismo grupo
• Penalizar los bordes existentes entre diferentes grupos
• Recompensar los vínculos no establecidos entre diferentes grupos.

Además, la agrupación espectral basada en Kernel-PCA adopta una forma de marco de máquina de vectores de soporte de mínimos cuadrados y, por lo tanto, se hace posible proyectar las entradas de datos a un espacio de características inducido por kernel que tiene una varianza máxima, lo que implica una alta separación entre las comunidades proyectadas. ^[16]

Algunos métodos expresan la partición de gráficos como un problema de optimización de múltiples criterios que puede resolverse utilizando métodos locales expresados ​​en un marco de teoría de juegos donde cada nodo toma una decisión sobre la partición que elige. ^[17]

Para gráficos distribuidos de escala muy grande, los métodos de partición clásicos podrían no ser aplicables (por ejemplo, partición espectral, Metis ^[7] ) ya que requieren acceso total a los datos del gráfico para realizar operaciones globales. Para estos escenarios de gran escala, la partición de gráficos distribuidos se utiliza para realizar la partición solo a través de operaciones locales asincrónicas.

Herramientas de software

scikit-learn implementa agrupamiento espectral con la partición determinada a partir de vectores propios de la matriz laplaciana del gráfico para el gráfico original calculado por ARPACK o por el solucionador LOBPCG con preacondicionamiento de múltiples cuadrículas . ^[9]

METIS ^[7] es una familia de particionamiento de grafos de Karypis y Kumar. Entre esta familia, kMetis apunta a una mayor velocidad de particionamiento, hMetis ^[8] se aplica a hipergrafos y apunta a la calidad de la partición, y ParMetis ^[7] es una implementación paralela del algoritmo de particionamiento de grafos Metis.

KaHyPar ^{[18] [19] [20]} es un marco de trabajo de partición de hipergrafos multinivel que proporciona algoritmos de partición basados ​​en k-way directos y bisección recursiva. Instancia el enfoque multinivel en su versión más extrema, eliminando solo un vértice en cada nivel de la jerarquía. Al utilizar este enfoque de n niveles de grano muy fino combinado con heurísticas de búsqueda local sólidas, calcula soluciones de muy alta calidad.

Scotch ^[21] es un marco de trabajo de particionamiento de grafos de Pellegrini. Utiliza bisección recursiva de múltiples niveles e incluye técnicas de particionamiento secuencial y paralelo.

Jostle ^[22] es un solucionador de particionamiento de grafos secuenciales y paralelos desarrollado por Chris Walshaw. La versión comercializada de este particionador se conoce como NetWorks.

Party ^[23] implementa el marco optimizado para burbujas y formas y el algoritmo Helpful Sets.

Los paquetes de software DibaP ^[24] y su variante paralela MPI PDibaP ^[25] de Meyerhenke implementan el marco Bubble usando difusión; DibaP también utiliza técnicas basadas en AMG para engrosar y resolver sistemas lineales que surgen en el enfoque difusivo.

Sanders y Schulz lanzaron un paquete de particionamiento de gráficos KaHIP ^[26] (Karlsruhe High Quality Partitioning) que implementa, por ejemplo, métodos basados ​​en flujo, búsquedas locales más localizadas y varias metaheurísticas paralelas y secuenciales.

Las herramientas Parkway ^[27] de Trifunovic y Knottenbelt, así como Zoltan ^[28] de Devine et al., se centran en la partición de hipergrafos.

Referencias

1. Andreev, Konstantin; Räcke, Harald (2004). "Particionamiento de grafos equilibrados". Actas del decimosexto simposio anual de la ACM sobre paralelismo en algoritmos y arquitecturas . Barcelona, ​​España. pp. 120–124. CiteSeerX 10.1.1.417.8592 . doi :10.1145/1007912.1007931. ISBN .  978-1-58113-840-5.{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
2. Buluc, Aydin; Meyerhenke, Henning; Safro, Ilya; Sanders, Peter ; Schulz, Christian (2013). "Avances recientes en particionamiento de grafos". arXiv : 1311.3144 [cs.DS].
3. Feldmann, Andreas Emil; Foschini, Luca (2012). "Particiones equilibradas de árboles y aplicaciones". Actas del 29.º Simposio internacional sobre aspectos teóricos de la informática : 100-111.
4. Feldmann, Andreas Emil (2012). "El particionamiento rápido y equilibrado es difícil, incluso en cuadrículas y árboles". Actas del 37.º Simposio internacional sobre fundamentos matemáticos de la informática . arXiv : 1111.6745 . Código Bibliográfico :2011arXiv1111.6745F.
5. Garey, Michael R.; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la completitud NP . WH Freeman & Co. ISBN 978-0-7167-1044-8.
6. Hendrickson, B.; Leland, R. (1995). Un algoritmo multinivel para particionar grafos . Actas de la conferencia ACM/IEEE de 1995 sobre supercomputación. ACM. pág. 28.
7. Karypis, G.; Kumar, V. (1999). "Un esquema multinivel rápido y de alta calidad para particionar grafos irregulares". Revista SIAM de Computación Científica . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi :10.1137/S1064827595287997. S2CID  3628209. 
8. Karypis, G.; Aggarwal, R.; Kumar, V.; Shekhar, S. (1997). Particionamiento de hipergrafos multinivel: aplicación en el dominio VLSI . Actas de la 34.ª Conferencia anual sobre automatización del diseño. págs. 526–529.
9. Knyazev, Andrew V. (2006). Partición de gráficos espectrales multiescala y segmentación de imágenes . Taller sobre algoritmos para conjuntos de datos masivos modernos, Universidad de Stanford y Yahoo! Research.
10. J. Demmel, [1], CS267: Notas para la lección 23, 9 de abril de 1999, Particionado de gráficos, parte 2
11. Knyazev, Andrew (2018). Sobre la partición espectral de grafos con signo . Octavo taller SIAM sobre computación científica combinatoria, CSC 2018, Bergen, Noruega, 6 al 8 de junio. arXiv : 1701.01394 . doi : 10.1137/1.9781611975215.2 .
12. Naumov, M.; Moon, T. (2016). "Particionamiento de gráficos espectrales paralelos". Informe técnico de NVIDIA . nvr-2016-001.
13. Newman, MEJ (2006). "Modularidad y estructura comunitaria en redes". PNAS . 103 (23): 8577–8696. arXiv : physics/0602124 . Bibcode :2006PNAS..103.8577N. doi : 10.1073/pnas.0601602103 . PMC 1482622 . PMID  16723398. 
14. Y. Chen, G. Paul, S. Havlin, F. Liljeros, HE Stanley (2009). "Encontrar una mejor estrategia de inmunización". Phys. Rev. Lett . 101 (5): 058701. doi :10.1103/PhysRevLett.101.058701. PMID  18764435.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
15. Reichardt, Jörg; Bornholdt, Stefan (julio de 2006). "Mecánica estadística de la detección de comunidades". Phys. Rev. E . 74 (1): 016110. arXiv : cond-mat/0603718 . Bibcode :2006PhRvE..74a6110R. doi :10.1103/PhysRevE.74.016110. PMID  16907154. S2CID  792965.
16. Alzate, Carlos; Suykens, Johan AK (2010). "Agrupamiento espectral multidireccional con extensiones fuera de muestra mediante PCA de núcleo ponderado". IEEE Transactions on Pattern Analysis and Machine Intelligence . 32 (2): 335–347. doi :10.1109/TPAMI.2008.292. ISSN  0162-8828. PMID  20075462. S2CID  200488.
17. Kurve, A.; Griffin, C.; Kesidis G. (2011) "Un juego de particionamiento de gráficos para simulación distribuida de redes", Actas del Taller internacional de 2011 sobre modelado, análisis y control de redes complejas : 9–16
18. Schlag, S.; Henne, V.; Heuer, T.; Meyerhenke, H.; Sanders, P.; Schulz, C. (30 de diciembre de 2015). "Particionamiento de hipergrafos de K-way mediante bisección recursiva de n niveles". Actas de 2016 del Decimoctavo Taller sobre Ingeniería de Algoritmos y Experimentos (ALENEX) . Sociedad de Matemáticas Industriales y Aplicadas. págs. 53–67. arXiv : 1511.03137 . doi :10.1137/1.9781611974317.5. ISBN . 978-1-61197-431-7.S2CID1674598  .​
19. Akhremtsev, Y.; Heuer, T.; Sanders, P.; Schlag, S. (1 de enero de 2017). "Ingeniería de un algoritmo de partición de hipergrafos de k vías directas". Actas de 2017 del decimonoveno taller sobre ingeniería de algoritmos y experimentos (ALENEX) . Sociedad de Matemáticas Industriales y Aplicadas. págs. 28–42. doi :10.1137/1.9781611974768.3. ISBN 978-1-61197-476-8.
20. Heuer, Tobias; Schlag, Sebastian (2017). "Mejora de los esquemas de engrosamiento para la partición de hipergrafos mediante la explotación de la estructura de la comunidad". En Iliopoulos, Costas S.; Pissis, Solon P.; Puglisi, Simon J.; Raman, Rajeev (eds.). 16.° Simposio internacional sobre algoritmos experimentales (SEA 2017) . Leibniz International Proceedings in Informatics (LIPIcs). Vol. 75. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. págs. 21:1–21:19. doi : 10.4230/LIPIcs.SEA.2017.21 . ISBN . 978-3-95977-036-1.
21. Chevalier, C.; Pellegrini, F. (2008). "PT-Scotch: una herramienta para ordenar de forma eficiente gráficos paralelos". Computación paralela . 34 (6): 318–331. arXiv : 0907.1375 . doi :10.1016/j.parco.2007.12.001. S2CID  10433524.
22. Walshaw, C.; Cross, M. (2000). "Particionamiento de malla: un algoritmo de refinamiento y balanceo multinivel". Revista de computación científica . 22 (1): 63–80. Bibcode :2000SJSC...22...63W. CiteSeerX 10.1.1.19.1836 . doi :10.1137/s1064827598337373. 
23. Diekmann, R.; Preis, R.; Schlimbach, F.; Walshaw, C. (2000). "Particionamiento de malla optimizado por forma y balanceo de carga para FEM adaptativo paralelo". Computación paralela . 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687 . doi :10.1016/s0167-8191(00)00043-0. 
24. Meyerhenke, H.; Monien, B.; Sauerwald, T. (2008). "Un nuevo algoritmo multinivel basado en difusión para calcular particiones de grafos". Journal of Parallel Computing and Distributed Computing . 69 (9): 750–761. CiteSeerX 10.1.1.702.7275 . doi :10.1016/j.jpdc.2009.04.005. S2CID  9755877. 
25. Meyerhenke, H. (2013). Balanceo de carga con optimización de forma para simulaciones numéricas adaptativas paralelas MPI . Décimo desafío de implementación de DIMACS sobre particionamiento y agrupamiento de gráficos. págs. 67–82.
26. Sanders, P. ; Schulz, C. (2011). Algoritmos de particionamiento de grafos multinivel de ingeniería . Actas del 19.º Simposio Europeo sobre Algoritmos (ESA). Vol. 6942. págs. 469–480.
27. Trifunovic, A.; Knottenbelt, WJ (2008). "Algoritmos multinivel paralelos para particionamiento de hipergrafos". Revista de computación paralela y distribuida . 68 (5): 563–581. CiteSeerX 10.1.1.641.7796 . doi :10.1016/j.jpdc.2007.11.002. 
28. Devine, K.; Boman, E.; Heaphy, R.; Bisseling, R.; Catalyurek, Ü. (2006). Particionamiento de hipergrafos paralelos para computación científica . Actas de la 20.ª Conferencia internacional sobre procesamiento paralelo y distribuido. pág. 124.

Lectura adicional

• Bichot, Charles-Edmond; Siarry, Patrick (2011). Particionamiento de grafos: optimización y aplicaciones . ISTE – Wiley. ISBN 978-1-84821-233-6.