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 al dividir 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 que tiene aplicaciones para 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 el agrupamiento y detección de camarillas en redes sociales, patológicas y biológicas. Para obtener una encuesta sobre las tendencias recientes en los 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
Por lo general, los problemas de partición de gráficos se incluyen en la categoría de problemas NP-hard . Las soluciones a estos problemas se derivan generalmente mediante heurística y algoritmos de aproximación. [3] Sin embargo, se puede demostrar que la partición uniforme de gráficos o un problema de partición de gráficos equilibrada 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 las simulaciones del Modelo de Elementos Finitos (FEM) . Cuando no solo se aproxima el número de bordes entre los componentes, sino también los tamaños de los componentes, se puede demostrar que no existen algoritmos completamente polinomiales razonables para estos gráficos. [4]
Problema
Considere una gráfica 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 dividir G en k componentes de tamaño máximo v · ( n / k ), mientras se minimiza la capacidad de los bordes entre componentes separados. [1] Además, dado G y un entero k > 1, divida V en k partes (subconjuntos) V 1 , V 2 , ..., V k de modo que las partes estén disjuntas y tengan el mismo tamaño, y el número de aristas con puntos finales en diferentes partes se minimiza. Tales problemas de partición se han discutido en la literatura como aproximación de bicriterio o enfoques de aumento de recursos. Una extensión común son los hipergráficos , donde un borde puede conectar más de dos vértices. Un hiperredge no se corta si todos los vértices están en una partición, y de lo 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 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 que 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), en el que cada uno de los k componentes debe tener el mismo tamaño de ( n / k ) nodos cada uno, por lo que es un problema más restringido. Por lo tanto,
Ya sabemos que (2,1) corte 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 polinómico. [1] Ahora, si asumimos que tenemos un algoritmo de aproximación finito para la partición balanceada ( k , 1), entonces, la instancia de 3 particiones puede resolverse usando la partición balanceada ( k , 1) en G o no puede estar solucionado. Si se puede resolver la instancia de 3 particiones, entonces el problema de particiones balanceadas ( 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 balanceada óptima ( k , 1) en G cortará al menos un borde. 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 las 3 particiones, que 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 de tiempo polinomial con un factor de aproximación finito a menos que P = NP . [1]
El teorema del separador plano establece que cualquier grafo plano de n - vértices puede dividirse 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 bordes. Sin embargo, el mismo resultado también implica que cada gráfico plano de grado acotado tiene un corte equilibrado con bordes O ( √ n ).
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 la heurística. Hay dos amplias categorías de métodos, locales y globales. Métodos locales conocidos son el algoritmo de Kernighan-Lin , y Fiduccia-Mattheyses algoritmos , que fueron los primeros recortes efectivos de 2 vías por las estrategias de búsqueda local. Su mayor 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 los 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 al contraer vértices y bordes, divide 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 particionamiento y refinamiento dentro del esquema general de niveles múltiples. En muchos casos, este enfoque puede proporcionar 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 grafos, y hMETIS, el particionador correspondiente para hipergrafos. [8] Un enfoque alternativo originó a partir de [9] y aplicarse, por ejemplo, en scikit-learn es agrupamiento espectral con la partición determinada a partir de los vectores propios de la Laplaciano gráfico matriz para el gráfico original calculado por LOBPCG solver con multigrid preacondicionamiento .
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 matriz de grados , que es una matriz diagonal, donde cada entrada diagonal de una fila , , representa el grado de nodo de nodo . La matriz laplaciana Se define como . Ahora, una partición de corte de relación para el gráfico se define como una partición de en disjunto , y , minimizando la relación
del número de aristas que realmente cruzan este corte al número de pares de vértices que podrían soportar tales aristas. La partición del gráfico espectral puede estar motivada [10] por analogía con la partición de una cuerda vibrante o un sistema masa-resorte y de manera similar se extiende al caso de pesos negativos del gráfico. [11]
Autovalor y autovector 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 relación con . El vector propio () correspondiente a , llamado vector de Fiedler , divide 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 autovectores correspondientes a los autovalores más pequeños. [12] Los ejemplos de las Figuras 1, 2 ilustran el método de bisección espectral.
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 particionar o los tamaños de las particiones. Por ejemplo, la optimización del 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 no ser lo correcto para minimizar, ya que una buena división no es solo una con una pequeña cantidad de bordes entre comunidades. Esto motivó el uso de Modularidad (Q) [13] como métrica para optimizar una partición de gráficos equilibrada. 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.
Aplicaciones
Conductancia
Otra función objetivo utilizada para la divisió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 proporcione particiones con una conductancia casi óptima. La calidad de esta aproximación depende del segundo valor propio más pequeño del laplaciano λ 2 .
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 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 se pueden interpretar directamente como comunidades. Por lo 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 los bordes existentes entre diferentes grupos.
- Recompense los no 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 a un espacio de características inducidas por el kernel que tiene la varianza 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 varios criterios que se puede resolver utilizando métodos locales expresados en un marco teórico de juegos donde cada nodo toma una decisión sobre la partición que elige. [17]
Para gráficos distribuidos a 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 realizar operaciones globales. Para estos escenarios a gran escala, la partición de gráficos distribuidos se utiliza para realizar la partición a través de operaciones locales asincrónicas únicamente.
Herramientas de software
Scikit-learn implementos agrupamiento espectral con la partición determinadas a partir de los vectores propios de la Laplaciano gráfico matriz para el gráfico original calculado por ARPACK , o por LOBPCG solver con multigrid preacondicionamiento . [9]
Chaco, [18] debido a Hendrickson y Leland, implementa el enfoque multinivel descrito anteriormente y los algoritmos básicos de búsqueda local. Además, implementan técnicas de partición espectral.
METIS [7] es una familia de particiones de gráficos de Karypis y Kumar. Entre esta familia, kMetis apunta a una mayor velocidad de partición, hMetis, [8] se aplica a los 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 grafos de Metis.
PaToH [19] es otro particionador hipergráfico .
KaHyPar [20] [21] [22] es un marco de partición hipergráfico multinivel que proporciona algoritmos de partición basados en bisecciones recursivas y k-way directos. Crea una instancia del 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 muy fino combinado con una sólida heurística de búsqueda local, calcula soluciones de muy alta calidad.
Scotch [23] es un marco de particionamiento de grafos de Pellegrini. Utiliza bisección multinivel recursiva e incluye técnicas de partición secuenciales y paralelas.
Jostle [24] es un solucionador de particiones de gráficos secuenciales y paralelos desarrollado por Chris Walshaw. La versión comercial de este particionador se conoce como NetWorks.
Party [25] implementa el marco optimizado de forma / burbuja y el algoritmo de Conjuntos útiles.
Los paquetes de software DibaP [26] y su variante en paralelo MPI PDibaP [27] de Meyerhenke implementan el framework 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 particionamiento gráfico KaHIP [28] (Particionamiento de alta calidad de Karlsruhe) 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 [29] de Trifunovic y Knottenbelt, así como Zoltan [30] de Devine et al. centrarse en la partición hipergráfica.
Lista de marcos de código abierto gratuitos:
Nombre | Licencia | Breve información |
---|---|---|
Scikit-aprender | BSD | Partición espectral con preacondicionamiento algebraico de redes múltiples |
Chaco | GPL | paquete de software que implementa técnicas espectrales y el enfoque multinivel |
DiBaP | * | Partición de gráficos basada en técnicas multinivel, multirredes algebraicas y difusión basada en gráficos. |
Empujar | * | Técnicas de particionamiento multinivel y equilibrio de carga difusivo, secuencial y paralelo. |
KaHIP | MIT | Varias metaheurísticas paralelas y secuenciales, garantiza la restricción del equilibrio |
KaHyPar | GPL | Marco de partición hipergráfico multinivel basado en k-way directo y bisección recursiva |
kMetis | Apache 2.0 | paquete de particionamiento de gráficos basado en técnicas multinivel y búsqueda local k-way |
Mondriaan | LGPL | particionador de matriz para particionar matrices dispersas rectangulares |
PaToH | BSD | particionamiento hipergráfico multinivel |
Parkway | * | particiones hipergráficas multinivel en paralelo |
escocés | CeCILL-C | Implementa bisección recursiva multinivel, así como técnicas de difusión, secuenciales y paralelas. |
Zoltan | BSD | particionamiento hipergrafico |
Referencias
- ^ a b c d e 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.
- ^ Buluc, Aydin; Meyerhenke, Henning; Safro, Ilya; Sanders, Peter ; Schulz, Christian (2013). "Avances recientes en la partición de gráficos". arXiv : 1311,3144 [ cs.DS ].
- ^ 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.
- ^ a b 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 .
- ^ Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de NP-completitud . WH Freeman & Co. ISBN 978-0-7167-1044-8.
- ^ 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.
- ^ a b c d 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 . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi : 10.1137 / S1064827595287997 .
- ^ a b Karypis, G .; Aggarwal, R .; Kumar, V .; Shekhar, S. (1997). Particionamiento hipergráfico multinivel: aplicación en dominio VLSI . Actas de la 34ª Conferencia anual de automatización del diseño. págs. 526–529.
- ^ a b Knyazev, Andrew V. (2006). Partición y segmentación de imágenes de gráficos espectrales multiescala . Taller sobre algoritmos para conjuntos de datos masivos modernos Stanford University y Yahoo! Investigar.
- ^ J. Demmel, [1] , CS267: Notas para la Conferencia 23, 9 de abril de 1999, Partición de gráficos, Parte 2
- ^ Knyazev, Andrew (2018). Sobre la partición espectral de gráficos firmados . Octavo Taller SIAM sobre Computación Científica Combinatoria, CSC 2018, Bergen, Noruega, 6-8 de junio. doi : 10.1137 / 1.9781611975215.2 .
- ^ Naumov, M .; Luna, T. (2016). "Particionamiento de gráfico espectral paralelo" . Informe técnico de NVIDIA . nvr-2016-001.
- ^ 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 .
- ^ 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 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Reichardt, Jörg; Bornholdt, Stefan (julio de 2006). "Mecánica estadística de detección de comunidades". Phys. 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 .
- ^ Alzate, Carlos; Suykens, Johan AK (2010). "Agrupación espectral de múltiples vías con extensiones fuera de muestra a través de PCA de núcleo ponderado". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 32 (2): 335–347. doi : 10.1109 / TPAMI.2008.292 . ISSN 0162-8828 . PMID 20075462 . S2CID 200488 .
- ^ Kurve, A .; Griffin, C .; Kesidis G. (2011) "Un juego de particiones gráficas para la simulación distribuida de redes", Actas del Taller internacional de 2011 sobre modelado, análisis y control de redes complejas : 9–16
- ^ Hendrickson, Bruce. "Chaco: Software para particionamiento de gráficos". Cite journal requiere
|journal=
( ayuda ) - ^ Catalyürek, Ü .; Aykanat, C. (2011). PaToH: herramienta de particionamiento para hipergrafos .
- ^ Schlag, S .; Henne, V .; Heuer, T .; Meyerhenke, H .; Sanders, P .; Schulz, C. (30 de diciembre de 2015). "Partición de Hypergraph de K-way a través de bisección recursiva de n niveles". 2016 Actas del Decimoctavo Taller de Ingeniería de Algoritmos y Experimentos (ALENEX) . Actas. Sociedad de Matemáticas Industriales y Aplicadas. págs. 53–67. doi : 10.1137 / 1.9781611974317.5 . ISBN 978-1-61197-431-7. S2CID 1674598 .
- ^ Akhremtsev, Y .; Heuer, T .; Sanders, P .; Schlag, S. (1 de enero de 2017). "Ingeniería de un algoritmo de particionamiento de Hypergraph de k-way directo". 2017 Actas del Decimonoveno Taller de Ingeniería de Algoritmos y Experimentos (ALENEX) . Actas. Sociedad de Matemáticas Industriales y Aplicadas. págs. 28–42. doi : 10.1137 / 1.9781611974768.3 . ISBN 978-1-61197-476-8.
- ^ Heuer, Tobías; Schlag, Sebastián (2017). Iliopoulos, Costas S .; Pissis, Solon P .; Puglisi, Simon J .; Raman, Rajeev (eds.). Mejora de los esquemas de engrosamiento para particiones hipergráficas mediante la explotación de la estructura de la comunidad . XVI Simposio Internacional de Algoritmos Experimentales (SEA 2017) . Leibniz International Proceedings in Informatics (LIPIcs). 75 . Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. págs. 21: 1–21: 19. doi : 10.4230 / LIPIcs.SEA.2017.21 . ISBN 9783959770361.
- ^ Chevalier, C .; Pellegrini, F. (2008). "PT-Scotch: una herramienta para la ordenación de gráficos paralelos eficiente". Computación paralela . 34 (6): 318–331. arXiv : 0907.1375 . doi : 10.1016 / j.parco.2007.12.001 . S2CID 10433524 .
- ^ 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. CiteSeerX 10.1.1.19.1836 . doi : 10.1137 / s1064827598337373 .
- ^ Diekmann, R .; Preis, R .; Schlimbach, F .; Walshaw, C. (2000). "Partición de malla de forma optimizada y equilibrio de carga para FEM adaptativa paralela". Computación paralela . 26 (12): 1555-1581. CiteSeerX 10.1.1.46.5687 . doi : 10.1016 / s0167-8191 (00) 00043-0 .
- ^ 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. doi : 10.1016 / j.jpdc.2009.04.005 . S2CID 9755877 .
- ^ Meyerhenke, H. (2013). Equilibrio de carga de optimización de formas para simulaciones numéricas adaptativas paralelas de MPI . Décimo desafío de implementación de DIMACS sobre particionamiento y agrupamiento de gráficos. págs. 67–82.
- ^ Sanders, P .; Schulz, C. (2011). Ingeniería de algoritmos de particionamiento de gráficos multinivel . Actas del XIX Simposio Europeo de Algoritmos (ESA). 6942 . págs. 469–480.
- ^ Trifunovic, A .; Knottenbelt, WJ (2008). "Algoritmos multinivel en paralelo para particiones Hypergraph". 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 .
- ^ Devine, K .; Boman, E .; Heaphy, R .; Bisseling, R .; Catalyurek, Ü. (2006). Partición de hipergráficos paralelos para la informática científica . Actas de la 20ª Conferencia Internacional sobre Procesamiento En Paralelo y Distribuido. pag. 124.
enlaces externos
- Chamberlain, Bradford L. (1998). "Algoritmos de particionamiento de gráficos para distribuir cargas de trabajo de cálculos paralelos" [ enlace muerto permanente ]
Bibliografía
- Bichot, Charles-Edmond; Siarry, Patrick (2011). Particionamiento de gráficos: optimización y aplicaciones . ISTE - Wiley. pag. 384. ISBN 978-1848212336.
- 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 en paralelo . Goettingen, Alemania: Cuvillier Verlag. pag. 218. ISBN 978-3954041251. 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 de Bell System . 49 (2): 291-307. doi : 10.1002 / j.1538-7305.1970.tb01770.x .Uno de los primeros trabajos fundamentales en el campo. Sin embargo, el rendimiento es O (n 2 ), por lo que ya no se usa comúnmente.
- Fiduccia, CM; Mattheyses, RM (1982). Una heurística de tiempo lineal para mejorar las particiones de red . Conferencia 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 multinivel es el estado actual de la técnica. Este documento también tiene buenas explicaciones de muchos otros métodos y comparaciones de los diversos métodos en una amplia variedad de problemas.
- Karypis, G .; Aggarwal, R .; Kumar, V .; Shekhar, S. (marzo de 1999). "Particionamiento hipergráfico multinivel: aplicaciones en dominio VLSI". Transacciones IEEE en sistemas de integración a 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 para el diseño de circuitos integrados.
- Kirkpatrick, S .; Gelatt, CD, Jr .; Vecchi, MP (13 de mayo de 1983). "Optimización por recocido simulado". Ciencia . 220 (4598): 671–680. Código Bibliográfico : 1983Sci ... 220..671K . CiteSeerX 10.1.1.123.7607 . doi : 10.1126 / science.220.4598.671 . PMID 17813860 . S2CID 205939 . También se puede utilizar el recocido simulado.
- Hagen, L .; Kahng, AB (septiembre de 1992). "Nuevos métodos espectrales para partición y agrupamiento de corte de relación". 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. Puede ver una demostración de esto , usando Matlab.