partición gráfica

Subdivisión de vértices en conjuntos disjuntos

En matemáticas, una partición de gráfico es la reducción de un gráfico a un gráfico más pequeño dividiendo su conjunto de nodos en grupos mutuamente excluyentes. Los bordes del gráfico original que se cruzan entre los grupos producirán bordes en el gráfico dividido. Si el número de aristas resultantes es pequeño en comparación con el gráfico original, entonces el gráfico dividido 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 gráficos es un problema difícil, pero tiene aplicaciones en informática científica, diseño de circuitos VLSI y programación de tareas en computadoras multiprocesador, entre otros. ^[1] Recientemente, el problema de la partición de gráficos 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 un estudio sobre las tendencias recientes en métodos y aplicaciones computacionales, consulte Buluc et al. (2013). ^[2] Dos ejemplos comunes de partición de gráficos son los problemas de corte mínimo y corte máximo .

Complejidad del problema

Normalmente, los problemas de partición de gráficos se incluyen en la categoría de problemas NP-difíciles . Las soluciones a estos problemas generalmente se obtienen mediante heurísticas y algoritmos de aproximación. ^[3] Sin embargo, se puede demostrar que la partición de gráficos uniforme o un problema de partición de gráficos equilibrado es NP-completo para aproximarse dentro de cualquier factor finito. ^[1] Incluso para clases de gráficos 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 gráficos resultantes de simulaciones del 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 totalmente polinomiales razonables para estos gráficos. ^[4]

Problema

Considere un gráfico G = ( V , E ), donde V denota el conjunto de n vértices y E el conjunto de aristas. Para un problema de partición equilibrada ( k , v ), el objetivo es dividir G en k componentes de como máximo tamaño v · ( n / k ), minimizando al mismo tiempo la capacidad de los bordes entre componentes separados. ^[1] Además, dado G y un número entero k > 1, divida V en k partes (subconjuntos) V ₁ , V ₂ , ..., V _k de modo que las partes sean disjuntas y tengan el mismo tamaño, y el número de aristas con puntos finales en diferentes partes se minimiza. 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 son los hipergrafos , donde una arista puede conectar más de dos vértices. Un hiperborde no se corta si todos los vértices están en una partición y, en caso contrario, se corta exactamente una vez, 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 de partición equilibrada ( k , 1 +  ε ) específico , buscamos encontrar una partición de costo mínimo de G en k componentes, donde cada componente contenga 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. De este modo,

${\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 en el que n  = 3 k , que también está acotado en tiempo polinomial. ^[1] Ahora, si asumimos que tenemos un algoritmo de aproximación finita para la partición balanceada ( k , 1), entonces, la instancia de 3 particiones se puede resolver usando la partición balanceada ( k , 1) en G o no estar solucionado. Si se puede resolver la instancia de 3 particiones, entonces el problema de partición equilibrada ( k , 1) en G se puede resolver sin cortar ningún borde. De lo contrario, si la instancia de 3 particiones no se puede resolver, la partición equilibrada óptima ( k , 1) en G cortará al menos un borde. Un algoritmo de aproximación con un factor de aproximación finito debe 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 balanceada ( k , 1) no tiene un algoritmo de aproximación en tiempo polinomial con un factor de aproximación finito a menos que P  =  NP . ^[1]

El teorema del separador plano establece que cualquier gráfico plano de n -vértices se puede dividir en partes aproximadamente iguales mediante la eliminación de O ( √ n ) vértices. Esta 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 gráfico plano 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 gráficos es un problema difícil, las soluciones prácticas se basan en heurísticas. Hay dos categorías amplias de métodos, locales y globales. Los métodos locales más conocidos son el algoritmo de Kernighan-Lin y los algoritmos de Fiduccia-Mattheyses , que fueron los primeros cortes bidireccionales 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 las propiedades de todo el gráfico y no se basan en 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 gráfico utilizando la descomposición propia de la matriz laplaciana del gráfico .

Métodos multinivel

Un algoritmo de partición de gráficos de varios niveles funciona aplicando una o más etapas. Cada etapa reduce el tamaño del gráfico colapsando vértices y aristas, divide el gráfico más pequeño, luego mapea 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 general multinivel. En muchos casos, este enfoque puede ofrecer tiempos de ejecución rápidos y resultados de muy alta calidad. Un ejemplo ampliamente utilizado de este enfoque es METIS , ^[7] un particionador de gráficos, y hMETIS, el particionador correspondiente para hipergráficos. ^[8] Un enfoque alternativo originado en ^[9] e implementado, por ejemplo, en scikit-learn, es la agrupación 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 precondicionamiento de redes múltiples .

Partición espectral y bisección espectral.

Dado un gráfico con matriz de adyacencia , donde una entrada implica un borde entre el nodo y , y una matriz de grados , que es una matriz diagonal, donde cada entrada diagonal de una fila , representa el grado del nodo . La matriz laplaciana se define como . Ahora, una partición de corte de proporción para un gráfico se define como una partición de en disjuntos y , minimizando la proporció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 del gráfico espectral 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 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 proporción con . El vector propio( ) correspondiente a , llamado vector de Fiedler , biseca el gráfico en sólo 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 bisección repetida o utilizando múltiples vectores propios correspondientes a los valores propios más pequeños. ^[12] Los ejemplos de las Figuras 1 y 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: El gráfico G  = (5,4) se analiza para determinar la bisección espectral. La combinación lineal de los dos vectores propios más pequeños conduce a 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 de espacio vectorial negativas.

Modularidad y ratio-cut

Sin embargo, la partición de corte mínimo falla cuando se desconoce el número de comunidades que se van 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, puede ser incorrecto minimizar el tamaño del corte, ya que una buena división no es sólo aquella con un pequeño número de bordes entre comunidades. Esto motivó el uso de Modularidad (Q) ^[13] como métrica para optimizar una partición gráfica balanceada. El ejemplo de la Figura 3 ilustra 2 instancias del mismo gráfico de modo que en (a) la modularidad (Q) es la métrica de partición y en (b) , el corte de relación es la métrica de partición.

Figura 3: El gráfico ponderado G se puede dividir para maximizar Q en (a) o para minimizar el corte de relación en (b). Vemos que (a) es una partición mejor equilibrada, lo que motiva 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 gráficos es la conductancia , que es la relación entre el número de bordes cortados y el volumen de la parte más pequeña. La conductancia está relacionada con los flujos eléctricos y los paseos aleatorios. El límite de Cheeger garantiza que la bisección espectral proporciona a las particiones 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 resultar útil para identificar el conjunto mínimo de nodos o enlaces que deben inmunizarse para detener las epidemias. ^[14]

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

Se han utilizado modelos de espín para agrupar datos multivariados en los que 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 tanto, un gráfico se divide para minimizar el hamiltoniano del gráfico dividido. El hamiltoniano (H) se obtiene asignando las siguientes recompensas y penalizaciones de partición.

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

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

Algunos métodos expresan la partición de gráficos como un problema de optimización de criterios múltiples que se puede resolver 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 a muy gran escala, es posible que los métodos de partición clásicos no se apliquen (por ejemplo, partición espectral, Metis ^[7] ), ya que requieren acceso completo a los datos del gráfico para poder realizar operaciones globales. Para escenarios de gran escala, la partición de gráficos distribuidos se utiliza para realizar la partición únicamente a través de operaciones locales asincrónicas.

Herramientas de software

scikit-learn implementa la agrupación 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 precondicionamiento multigrid . ^[9]

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

KaHyPar ^{[18] [19] [20]} es un marco de partición de hipergráficos multinivel que proporciona algoritmos de partición basados ​​en bisección recursiva y directa k-way. 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 nivel n muy detallado combinado con una sólida heurística de búsqueda local, calcula soluciones de muy alta calidad.

Scotch ^[21] es un marco de partición de gráficos de Pellegrini. Utiliza bisección recursiva multinivel e incluye técnicas de partición secuencial y paralela.

Jostle ^[22] es un solucionador de partición de gráficos 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/formas y el algoritmo Conjuntos útiles.

Los paquetes de software DibaP ^[24] y su variante MPI paralela PDibaP ^[25] de Meyerhenke implementan el marco Bubble mediante 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 partición 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. centrarse en la partición de hipergrafos.

Referencias

1. Andreev, Konstantin; Räcke, Harald (2004). "Partición de gráficos equilibrados". Actas del decimosexto simposio anual de ACM sobre paralelismo en algoritmos y arquitecturas . Barcelona, ​​España. págs. 120-124. CiteSeerX 10.1.1.417.8592 . doi :10.1145/1007912.1007931. ISBN  978-1-58113-840-5.{{cite book}}: CS1 maint: location missing publisher (link)
2. Buluc, Aydin; Meyerhenke, Henning; Safro, Ilya; Lijadoras, Pedro ; Schulz, cristiano (2013). "Avances recientes en la partición de gráficos". 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). "La partición rápida y equilibrada 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 Bib : 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 gráficos . Actas de la conferencia ACM/IEEE de 1995 sobre supercomputación. ACM. pag. 28.
7. , G.; Kumar, V. (1999). "Un esquema multinivel rápido y de alta calidad para particionar gráficos 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). Partición 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. 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! Investigación.
10. J. Demmel, [1], CS267: Notas para la conferencia 23, 9 de abril de 1999, Partición de gráficos, Parte 2
11. Knyazev, Andrés (2018). Sobre la partición espectral de gráficos firmados . 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.; Luna, T. (2016). "Partición 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 : física/0602124 . Código bibliográfico : 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". Física. Rev. Lett . 101 (5): 058701. doi : 10.1103/PhysRevLett.101.058701. PMID  18764435.{{cite journal}}: CS1 maint: multiple names: authors list (link)
15. Reichardt, Jörg; Bornholdt, Stefan (julio de 2006). "Mecánica estadística de detección comunitaria". Física. Rev. E. 74 (1): 016110. arXiv : cond-mat/0603718 . Código bibliográfico : 2006PhRvE..74a6110R. doi : 10.1103/PhysRevE.74.016110. PMID  16907154. S2CID  792965.
16. Alzate, Carlos; Suykens, Johan AK (2010). "Agrupación espectral multidireccional con extensiones fuera de muestra a través de PCA de kernel ponderado". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 32 (2): 335–347. doi :10.1109/TPAMI.2008.292. ISSN  0162-8828. PMID  20075462. S2CID  200488.
17. Kurve, A.; Grifo, C.; Kesidis G. (2011) "Un juego de partición de gráficos 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.; Lijadoras, P.; Schulz, C. (30 de diciembre de 2015). "Partición de hipergrafo K-way mediante bisección recursiva de n niveles". 2016 Actas del decimoctavo taller sobre experimentos e ingeniería de algoritmos (ALENEX) . Sociedad de Matemática Industrial y Aplicada. 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.; Lijadoras, P.; Schlag, S. (1 de enero de 2017). "Diseñar un algoritmo de partición de hipergrafo directo de k-way". 2017 Actas del decimonoveno taller sobre experimentos e ingeniería de algoritmos (ALENEX) . Sociedad de Matemática Industrial y Aplicada. págs. 28–42. doi :10.1137/1.9781611974768.3. ISBN 978-1-61197-476-8.
20. Heuer, Tobías; Schlag, Sebastián (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, Simón J.; Raman, Rajeev (eds.). XVI Simposio Internacional sobre Algoritmos Experimentales (SEA 2017) . Procedimientos internacionales de informática de Leibniz (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. Caballero, C.; Pellegrini, F. (2008). "PT-Scotch: una herramienta para el ordenamiento eficiente de 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.; Cruz, M. (2000). "Partición de malla: un algoritmo de refinamiento y equilibrio multinivel". Revista de Computación Científica . 22 (1): 63–80. Código Bib : 2000SJSC...22...63W. CiteSeerX 10.1.1.19.1836 . doi :10.1137/s1064827598337373. 
23. Diekmann, R.; Preis, R.; Schlimbach, F.; Walshaw, C. (2000). "Partición de malla con forma optimizada y equilibrio 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 gráficos". Revista de Computación Paralela y Computación Distribuida . 69 (9): 750–761. CiteSeerX 10.1.1.702.7275 . doi : 10.1016/j.jpdc.2009.04.005. S2CID  9755877. 
25. Meyerhenke, H. (2013). Equilibrio de carga de optimización de forma para simulaciones numéricas adaptativas paralelas MPI . Décimo desafío de implementación de DIMACS sobre partición de gráficos y agrupación de gráficos. págs. 67–82.
26. Lijadoras, P .; Schulz, C. (2011). Ingeniería de algoritmos de partición de gráficos multinivel . Actas del XIX Simposio Europeo sobre Algoritmos (ESA). vol. 6942, págs. 469–480.
27. Trifunovic, A.; Knottenbelt, WJ (2008). "Algoritmos paralelos multinivel 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. Divino, K.; Boman, E.; Heaphy, R.; Bisseling, R.; Catalyurek, Ü. (2006). Partición de hipergrafos paralelos para informática científica . Actas de la XX Conferencia Internacional sobre Procesamiento Paralelo y Distribuido. pag. 124.

Bibliografía

• Bichot, Charles-Edmond; Siarry, Patricio (2011). Partición de gráficos: optimización y aplicaciones. ISTE – Wiley. pag. 384.ISBN​ 978-1-84821-233-6.
• Feldmann, Andreas Emil (2012). Partición equilibrada de cuadrículas y gráficos relacionados: un estudio teórico de la distribución de datos en simulaciones de modelos de elementos finitos paralelos. Goettingen, Alemania: Cuvillier Verlag. pag. 218.ISBN​ 978-3-95404-125-1.Un análisis exhaustivo del problema desde un punto de vista teórico.
• Kernighan, BW; Lin, S. (1970). "Un procedimiento heurístico eficiente para particionar gráficos" (PDF) . Revista técnica del sistema Bell . 49 (2): 291–307. doi :10.1002/j.1538-7305.1970.tb01770.x. Uno de los primeros trabajos fundamentales en este campo. Sin embargo, el rendimiento es O(n ² ), por lo que ya no se utiliza habitualmente.
• Fiduccia, CM; Mattheyses, RM (1982). "Una heurística de tiempo lineal para mejorar las particiones de la red ". Jornada de Automatización del Diseño. doi :10.1109/DAC.1982.1585498. Una variante posterior que es el tiempo lineal, muy comúnmente utilizada, tanto por sí misma como como parte de la partición multinivel, ver más abajo.
• Karypis, G.; Kumar, V. (1999). "Un esquema multinivel rápido y de alta calidad para particionar gráficos irregulares". Revista SIAM de Computación Científica . La partición de varios niveles es el estado actual de la técnica. Este artículo también tiene buenas explicaciones de muchos otros métodos y comparaciones de los distintos métodos en una amplia variedad de problemas.
• Karypis, G.; Aggarwal, R.; Kumar, V.; Shekhar, S. (marzo de 1999). "Partición de hipergráficos multinivel: aplicaciones en el dominio VLSI". Transacciones IEEE en sistemas de integración a muy gran escala (VLSI) . 7 (1): 69–79. CiteSeerX  10.1.1.553.2367 . doi : 10.1109/92.748202. La partición de gráficos (y en particular, la partición de hipergráficos) tiene muchas aplicaciones en el diseño de circuitos integrados.
• Kirkpatrick, S.; Gelatt, CD Jr.; Vecchi, diputado (13 de mayo de 1983). "Optimización mediante recocido simulado". Ciencia . 220 (4598): 671–680. Código Bib : 1983 Ciencia... 220..671K. CiteSeerX  10.1.1.123.7607 . doi : 10.1126/ciencia.220.4598.671. PMID  17813860. S2CID  205939. También se puede utilizar recocido simulado.
• Hagen, L.; Kahng, AB (septiembre de 1992). "Nuevos métodos espectrales para la agrupación y partición por corte de proporciones". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 11 (9): 1074–1085. doi :10.1109/43.159993.. Existe toda una clase de métodos de partición espectral , que utilizan los vectores propios del laplaciano del gráfico de conectividad. Puedes ver una demostración de esto, usando Matlab.