Hispanopedia Wiki
Articulo de referencia

Partición de grafos

En matemáticas, una partición de grafos es la reducción de un grafo a uno más pequeño mediante la partición de su conjunto de nodos en grupos mutuamente excluyentes. Las aristas...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas, una partición de grafos es la reducción de un grafo a uno más pequeño mediante la partición de su conjunto de nodos en grupos mutuamente excluyentes. Las aristas del grafo original que cruzan entre los grupos producirán aristas en el grafo particionado. Si el número de aristas 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 computación científica, diseño de circuitos VLSI y planificación de tareas en computadoras multiprocesador, entre otras. [ 1 ] Recientemente, el problema de 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 revisión de las tendencias recientes en métodos y aplicaciones computacionales, véase Buluc et al. (2013) . [ 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 se clasifican como problemas NP-difíciles . Las soluciones a estos problemas se suelen obtener mediante 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 equilibrada de grafos es NP-completo para aproximarlo con cualquier factor finito. [ 1 ] Incluso para clases especiales de grafos, como árboles y cuadrículas, no existen algoritmos de aproximación razonables, [ 4 ] a menos que P=NP . Las cuadrículas constituyen un caso particularmente interesante, ya que modelan los grafos resultantes de simulaciones de elementos finitos (FEM) . Cuando se aproxima no solo el número de aristas entre los componentes, sino también sus tamaños, se puede demostrar que no existen algoritmos completamente polinomiales razonables para estos grafos. [ 4 ]

Problema

Consideremos 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 máximo v · ( n / k ), minimizando 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 1 , V 2 , ..., V k tales que las partes sean disjuntas y tengan el mismo tamaño, y se minimice el número de aristas con extremos en diferentes partes. Estos problemas de partición se han discutido en la literatura como enfoques de aproximación bicriterio o de aumento de recursos. Una extensión común es a 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 equilibrada ( k , 1  + ε ), buscamos encontrar una partición de costo mínimo de G en k componentes, donde cada componente contiene 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, siendo así un problema más restringido. Por lo tanto,   

máximoi|Vi|≤(1+ε)⌈|V|k⌉.{\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-partición donde n  =  3 k , que también está acotado en tiempo polinomial. [ 1 ] Ahora, si asumimos que tenemos un algoritmo de aproximación finito para la partición ( k ,  1)-equilibrada, entonces, o bien la instancia de 3-partición puede resolverse usando la partición ( k ,1) equilibrada en G o no puede resolverse. Si la instancia de 3-partición puede resolverse, entonces el problema de partición ( k ,  1)-equilibrada en G puede resolverse sin cortar ninguna arista. De lo contrario, si la instancia de 3-partición no puede resolverse, la partición ( k , 1)-equilibrada ó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-partición, lo cual es una contradicción bajo el supuesto de que P  = NP . Por lo tanto, es evidente que el problema de partición ( k ,1)-equilibrada 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 puede dividirse en partes aproximadamente iguales eliminando O( √n ) vértices. Esto no constituye una partición en el sentido descrito anteriormente, ya que el conjunto de partición está formado por vértices en lugar de aristas. Sin embargo , este 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 grafos

Dado que la partición de grafos es un problema complejo, las soluciones prácticas se basan en heurísticas. Existen dos grandes categorías de métodos: locales y globales. Entre los métodos locales más conocidos se encuentran el algoritmo de Kernighan-Lin y el algoritmo de Fiduccia-Mattheyses , que fueron los primeros en realizar cortes bidireccionales efectivos mediante estrategias de búsqueda local. Su principal inconveniente es la partición inicial arbitraria del conjunto de vértices, lo 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 autovectores aproximados de la matriz de adyacencia, o el agrupamiento espectral, que agrupa los vértices del grafo mediante la descomposición en autovalores de la matriz laplaciana del grafo .

Métodos multinivel

Un algoritmo de partición de grafos multinivel funciona aplicando una o más etapas. Cada etapa reduce el tamaño del grafo colapsando vértices y aristas, particiona el grafo más pequeño, luego mapea y refina esta partición del grafo 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 proporcionar tiempos de ejecución rápidos y resultados de muy alta calidad. Un ejemplo ampliamente utilizado de tal enfoque es METIS , [ 7 ] un particionador de grafos, 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 los vectores propios de la matriz laplaciana del grafo para el grafo original calculado por el solucionador LOBPCG con precondicionamiento multigrid .

Particionamiento espectral y bisección espectral

Dado un gráficoGRAMO=(V,mi){\displaystyle G=(V,E)}con matriz de adyacenciaA{\displaystyle A}, donde una entradaAij{\displaystyle A_{ij}}implica una arista entre nodosi{\displaystyle i}yj{\displaystyle j}y matriz de gradosD{\displaystyle D}, que es una matriz diagonal , donde cada entrada diagonal de una filai{\displaystyle i},dii{\displaystyle d_{ii}}, representa el grado del nodoi{\displaystyle i}La matriz laplacianaL{\displaystyle L}se define comoL=D−A{\displaystyle L=DA}Ahora, una partición de corte de razón para el grafoGRAMO=(V,mi){\displaystyle G=(V,E)}se define como una partición deV{\displaystyle V}en disjuntosU{\displaystyle U}, yW{\displaystyle W}minimizando la relación

|mi(GRAMO)∩(U×W)||U|⋅|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 espectral de grafos puede motivarse [ 10 ] por analogía con la partición de una cuerda vibrante o un sistema masa-resorte y extenderse de manera similar al caso de pesos negativos del grafo. [ 11 ]

Autovalor y autovector de Fiedler

En tal escenario, el segundo valor propio más pequeño (λ2{\displaystyle \lambda _{2}}) deL{\displaystyle L}, proporciona un límite inferior para el costo óptimo (do{\displaystyle c}) de partición de corte de razón condo≥λ2norte{\displaystyle c\geq {\frac {\lambda _{2}}{n}}}. El vector propio (V2{\displaystyle V_{2}}) correspondiente aλ2{\displaystyle \lambda _{2}}El vector de Fiedler divide el grafo en dos comunidades según el signo de la entrada correspondiente . La división en un mayor número de comunidades se puede lograr mediante bisección repetida o utilizando múltiples autovectores correspondientes a los autovalores más pequeños. [ 12 ] Los ejemplos de las figuras 1 y 2 ilustran el método de bisección espectral.

Figura 1: Se analiza el gráfico G  =  (5,4) para la bisección espectral. La combinación lineal de los dos autovectores más pequeños conduce a [1 1 1 1 1]' con un autovalor  =  0.
Figura 2: El gráfico G  =  (5,5) ilustra que el vector de Fiedler en rojo biseca 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 corte de relación

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

Figura 3: El grafo ponderado G puede particionarse para maximizar Q en (a) o para minimizar el corte de razón en (b). Observamos que (a) es una partición mejor equilibrada, lo que subraya la importancia de la modularidad en los problemas de partición de grafos.

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 paseos aleatorios. La cota de Cheeger garantiza que la bisección espectral proporciona particiones con una conductancia casi óptima. La calidad de esta aproximación depende del segundo autovalor más pequeño del laplaciano λ² .

Inmunización

La partición de grafos puede ser útil para identificar el conjunto mínimo de nodos o enlaces que deben ser inmunizados para detener las epidemias. [ 14 ]

Otros métodos de partición de grafos

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

  • Recompensar las aristas internas entre nodos del mismo grupo (mismo giro)
  • Penalizar los bordes faltantes en el mismo grupo
  • Penalizar las relaciones existentes entre diferentes grupos
  • Recompensar la falta de vínculos entre diferentes grupos.

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

Algunos métodos expresan la partición de grafos como un problema de optimización multicriterio 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 grafos distribuidos de gran escala, los métodos de partición clásicos podrían no ser aplicables (por ejemplo, partición espectral , Metis [ 7 ] ), ya que requieren acceso completo a los datos del grafo para realizar operaciones globales. En tales escenarios de gran escala, la partición de grafos distribuidos se utiliza para realizar la partición únicamente mediante operaciones locales asíncronas.

Herramientas de software

scikit-learn implementa la agrupación espectral con la partición determinada a partir de los autovectores de la matriz laplaciana del grafo para el grafo original calculado por ARPACK o por el solucionador LOBPCG con precondicionamiento multigrid . [ 9 ]

METIS [ 7 ] es una familia de particionamiento de grafos de Karypis y Kumar. Dentro de esta familia, kMetis busca una mayor velocidad de particionamiento, hMetis [ 8 ] se aplica a hipergrafos y busca 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 particionamiento de hipergrafos multinivel que proporciona algoritmos de particionamiento directos basados ​​en k vías y bisección recursiva. Implementa el enfoque multinivel en su versión más extrema, eliminando un único vértice en cada nivel de la jerarquía. Mediante este enfoque de n niveles de grano fino, combinado con heurísticas de búsqueda local robustas, calcula soluciones de muy alta calidad.

Scotch [ 21 ] es un marco de particionamiento de grafos de Pellegrini. Utiliza bisección multinivel recursiva e incluye técnicas de particionamiento secuenciales y paralelas.

Jostle [ 22 ] es un solucionador de particionamiento de grafos secuencial y paralelo desarrollado por Chris Walshaw. La versión comercial de este particionador se conoce como NetWorks.

Party [ 23 ] implementa el marco optimizado de burbuja/forma y el algoritmo de conjuntos útiles.

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 el engrosamiento y la resolución de sistemas lineales que surgen en el enfoque difusivo.

Sanders y Schulz publicaron un paquete de partición de grafos 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. 1 2 3 4 5 Andreev, Konstantin; Räcke, Harald (2004). "Particionamiento equilibrado de grafos". 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}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  2. ↑ Buluc, Aydin; Meyerhenke, Henning; Safro, Ilya; Sanders, Peter ; Schulz, Christian (2013). "Avances recientes en la partición 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. 1 2 Feldmann, Andreas Emil (2012). "La partición equilibrada rápida 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 . Bibcode : 2011arXiv1111.6745F .
  5. ↑ Garey, Michael R.; Johnson, David S. (1979). Computadoras e intratabilidad: Una guía a la teoría de la NP-completitud . WH Freeman & Co. ISBN 978-0-7167-1044-8.
  6. ↑ Hendrickson, B.; Leland, R. (1995). Un algoritmo multinivel para la partición de grafos . Actas de la conferencia ACM/IEEE de 1995 sobre supercomputación. ACM. pág. 28. 
  7. 1 2 3 4 Karypis, G.; Kumar, V. (1999). "Un esquema multinivel rápido y de alta calidad para la partición de grafos irregulares". SIAM Journal on Scientific Computing . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi : 10.1137/S1064827595287997 . S2CID 3628209 .  
  8. 1 2 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 de Automatización del Diseño. págs. 526–529 . 
  9. 1 2 Knyazev, Andrew V. (2006). Particionamiento de grafos 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,Archivado el 6 de mayo de 2018 en Wayback Machine , CS267: Apuntes de la clase 23, 9 de abril de 1999, Particionamiento de grafos, 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-8 de junio. arXiv : 1701.01394 . doi : 10.1137/1.9781611975215.2 .
  12. ↑ Naumov, M.; Moon, T. (2016). "Particionamiento espectral paralelo de grafos" . Informe técnico de NVIDIA . nvr-2016-001. Archivado del original el 5 de mayo de 2016. Consultado el 20 de abril de 2016 .
  13. ↑ Newman, MEJ (2006). " Modularidad y estructura de la comunidad 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). "Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA". IEEE Transactions on Pattern Analysis and Machine Intelligence . 32 (2): 335– 347. Bibcode : 2010ITPAM..32..335A . doi : 10.1109/TPAMI.2008.292 . ISSN 0162-8828 . PMID 20075462 . S2CID 200488 .   
  17. ↑ Kurve, A.; Griffin, C.; Kesidis G. (2011) "Un juego de partición de grafos para la 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 K-way mediante bisección recursiva de n niveles». Actas del decimoctavo taller sobre ingeniería y experimentos de algoritmos (ALENEX) de 2016. 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. S2CID 1674598 . 
  19. ↑ Akhremtsev, Y.; Heuer, T.; Sanders, P.; Schlag, S. (1 de enero de 2017). «Ingeniería de un algoritmo directo de partición de hipergrafos k-way». Actas del decimonoveno taller sobre ingeniería y experimentos de algoritmos (ALENEX) de 2017. 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 agrupamiento 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) . Actas Internacionales Leibniz en Informática (LIPIcs). Vol. 75. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 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 la ordenación eficiente de grafos 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 equilibrio y refinamiento multinivel". SIAM Journal on Scientific Computing . 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). "Shape-optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM". Parallel Computing . 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 el cálculo de 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). Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations . 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering. pp. 67– 82. 
  26. ↑ Sanders, P. ; Schulz, C. (2011). Ingeniería de algoritmos de particionamiento de grafos multinivel . Actas del 19.º Simposio Europeo sobre Algoritmos (ESA). Vol. 6942. pp. 469–480 .  
  27. ↑ Trifunovic, A.; Knottenbelt, WJ (2008). "Algoritmos multinivel paralelos para la partición de hipergrafos". Journal of Parallel and Distributed Computing . 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 paralelo de hipergrafos para computación científica . Actas de la 20.ª Conferencia Internacional sobre Procesamiento Paralelo y Distribuido. pág. 124. 

Lecturas adicionales

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