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 particionado. Si el número de aristas resultantes es pequeño en comparación con el gráfico original, entonces el gráfico 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 gráficos es un problema difícil, pero tiene aplicaciones en computación 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 una encuesta sobre tendencias recientes en métodos y aplicaciones computacionales, ver Buluc et al. (2013) .
Complejidad del problema [ editar ]
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 generalmente se derivan utilizando algoritmos de heurística y aproximación. [3] Sin embargo, se puede mostrar que el particionamiento gráfico uniforme o un problema de partición gráfica equilibrado son NP completos para aproximarse dentro de cualquier factor finito. [1] Incluso para clases especiales de gráficos 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 las gráficas resultantes del Modelo de elementos finitos (FEM)simulaciones 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 razonables completamente polinómicos para estos gráficos. [4]
Problema [ editar ]
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 componentes k 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, partición V en k partes (subconjuntos) V1 , V 2 , ..., V k tal que las partes son disjuntas y tienen 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 aproximaciones de bicriteria o enfoques de aumento de recursos. Una extensión común es a las hipergrafías , donde un borde puede conectar más de dos vértices. No se corta una hiperedificación si todos los vértices están en una partición, y se corta exactamente una vez de lo 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 [ editar ]
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 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 componentes k debe tener el mismo tamaño de nodos ( n / k ) cada uno, por lo que es un problema más restringido. Así,
Ya sabemos que el corte (2,1) es el problema mínimo de bisección y es NP completo. [5] A continuación, evaluamos un problema de 3 particiones en el que n = 3 k , que también está limitado en el tiempo polinómico. [1] Ahora, si asumimos que tenemos un algoritmo de aproximación finita para ( k , 1) partición -balanced, a continuación, ya sea la instancia 3-partición puede ser resuelto mediante el equilibrada ( k , 1) de partición en G o no se puede 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, lo óptimo (k , 1) la partición equilibrada 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 3 particiones, lo cual es una contradicción bajo el supuesto de que P = NP . Por lo tanto, es evidente que el problema de particionamiento equilibrado ( k , 1) no tiene un algoritmo de aproximación de tiempo polinómico con un factor de aproximación finito a menos que P = NP . [1]
El teorema del separador plano establece que cualquier gráfico plano n- vértice puede dividirse en partes más o menos iguales mediante la eliminación de vértices O ( √ n ). Esto no es una partición en el sentido descrito anteriormente, porque el conjunto de particiones consiste en 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 grafos [ editar ]
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 categorías amplias de métodos, local y global. 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 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 los vectores propios aproximados de la matriz de adyacencia, o la agrupación espectral que agrupa los vértices del gráfico utilizandodescomposición propia de la matriz matriz laplaciana .
Métodos multinivel [ editar ]
Un algoritmo de partición de gráficos de niveles múltiples funciona aplicando una o más etapas. Cada etapa reduce el tamaño del gráfico al contraer los vértices y los 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 partición 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 divisor de gráficos, y hMETIS, el divisor correspondiente para hipergrafías. [8] Un enfoque alternativo originado en [9] e implementado, por ejemplo, en scikit-learn esagrupamiento espectral con la partición determina a partir de los vectores propios de la Laplaciano gráfico matriz para el gráfico original calculado por LOBPCG solver con multigrid preacondicionamiento .
Particionamiento espectral y bisección espectral [ editar ]
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 del nodo . La matriz laplaciana Se define como . Ahora, una partición de corte proporcional para gráfico se define como una partición de en disjunto y , minimizando la relación
del número de bordes que realmente cruzan este corte al número de pares de vértices que podrían soportar dichos bordes. La división de gráficos espectrales puede motivarse [10] por analogía con la división de una cuerda vibrante o un sistema de resorte de masa.
Valor propio de Fiedler y vector propio [ editar ]
En tal escenario, el segundo valor propio más pequeño () de , produce un límite inferior en el costo óptimo () de partición de corte proporcional con . El vector propio () correspondiente a , llamado el 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 la bisección repetida o mediante el uso de múltiples vectores propios correspondientes a los valores propios más pequeños. [11] Los ejemplos en las Figuras 1,2 ilustran el enfoque de bisección espectral.
Modularidad y relación de corte [ editar ]
Sin embargo, la partición mínima de corte falla cuando se desconoce el número de comunidades que se van a particionar o los tamaños de partición. Por ejemplo, la optimización del tamaño de corte para los tamaños de grupo libres pone todos los vértices en la misma comunidad. Además, el tamaño de corte puede ser incorrecto para minimizar, ya que una buena división no es solo una con un pequeño número de bordes entre las comunidades. Esto motivó el uso de Modularidad (Q) [12] como una métrica para optimizar una partición gráfica 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) , la relación de corte es la métrica de partición.
Conductancia [ editar ]
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 flujos eléctricos y caminatas aleatorias. El límite Cheeger garantiza que la bisección espectral proporciona particiones con una conductancia casi óptima. La calidad de esta aproximación depende del segundo valor propio más pequeño del Laplaciano λ 2 .
Otros métodos de partición de gráficos [ editar ]
Los modelos de centrifugado se han utilizado para la agrupación de datos multivariados en los que las similitudes se traducen en fuerzas de acoplamiento. [13] Las propiedades de la configuración de rotación del estado fundamental se pueden interpretar directamente como comunidades. Por lo tanto, se divide un gráfico para minimizar el hamiltoniano del gráfico dividido. El Hamiltoniano (H) se deriva asignando las siguientes recompensas y penalizaciones de partición.
- Recompense los bordes internos entre nodos del mismo grupo (mismo giro)
- Penalizar los bordes faltantes en el mismo grupo
- Penalizar los bordes existentes entre los diferentes grupos.
- Recompense los no enlaces entre diferentes grupos.
Además, la agrupación espectral basada en Kernel-PCA toma 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 en un espacio de características inducido por el kernel que tiene una varianza máxima, lo que implica una alta separación entre las comunidades proyectadas . [14]
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 teórico de juego en el que cada nodo toma una decisión sobre la partición que elige. [15]
Para gráficos distribuidos a gran escala, los métodos de partición clásicos podrían no aplicarse (por ejemplo, particionamiento espectral , Metis [7] ) ya que requieren acceso total a los datos del gráfico para realizar operaciones globales. Para tales escenarios a gran escala, la partición de gráficos distribuidos se usa para realizar la partición solo a través de operaciones locales asincrónicas (por ejemplo, algoritmos Ja-be-ja, [16] Stad [17] basados en el protocolo Gossip ).
Herramientas de software [ editar ]
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 algoritmos básicos de búsqueda local. Además, implementan técnicas de partición espectral.
METIS [7] es una familia de particiones gráficas de Karypis y Kumar. Entre esta familia, kMetis apunta a una mayor velocidad de partición, hMetis, [8] se aplica a las hipergrafías 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 Metis.
KaHyPar [20] [21] [22] es un marco de partición de hipergrafía multinivel que proporciona algoritmos de partición basados en bisección recursiva y k-way directo. Instancia el enfoque multinivel en su versión más extrema, eliminando solo un vértice en cada nivel de la jerarquía. Mediante el uso de este enfoque de nivel n de grano muy fino combinado con una fuerte heurística de búsqueda local, calcula soluciones de muy alta calidad.
Scotch [23] es el marco de partición de gráficos de Pellegrini. Utiliza bisección recursiva multinivel e incluye técnicas de particionamiento secuenciales y paralelas.
Jostle [24] es un solucionador de particiones de gráficos secuenciales y paralelos desarrollado por Chris Walshaw. La versión comercializada de este particionador se conoce como NetWorks.
Los paquetes de software DibaP [26] y su variante MPiba paralela PDibaP [27] 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 particiones gráficas 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 informacion |
|---|---|---|
| Scikit-learn | BSD | particionamiento espectral con preacondicionamiento algebraico de múltiples cuadrículas |
| Chaco | GPL | paquete de software que implementa técnicas espectrales y el enfoque multinivel |
| DiBaP | * * | particionamiento de grafos basado en técnicas multinivel, multigrid algebraico así como difusión basada en grafos |
| Empujar | * * | técnicas de partición multinivel y balanceo de carga difusivo, secuencial y paralelo |
| KaHIP | MIT | varias metaheurísticas paralelas y secuenciales, garantizan la restricción del equilibrio |
| KaHyPar | GPL | marco de particionamiento de hipergrafía multinivel basado en bisección recursiva y directa |
| kMetis | Apache 2.0 | paquete de particionamiento gráfico basado en técnicas multinivel y búsqueda local k-way |
| Mondriaan | LGPL | divisor de matriz para particionar matrices dispersas rectangulares |
| PaToH | BSD | particionamiento de hipergrafía multinivel |
| Parkway | * * | partición paralela de hipergramas multinivel |
| escocés | CeCILL-C | implementa bisección recursiva multinivel, así como técnicas de difusión, secuenciales y paralelas |
| Zoltan | BSD | particionamiento de hipergrafía |
El problema de finalización de Hamilton es encontrar el número mínimo de aristas para agregar a un gráfico para que sea Hamiltoniano .
El problema es claramente NP-difícil en el caso general (ya que su solución da una respuesta al problema NP-completo de determinar si un gráfico dado tiene un ciclo hamiltoniano ). El problema de decisión asociado de determinar si se pueden agregar K bordes a un gráfico dado para producir un gráfico hamiltoniano es NP completo.
Además, la finalización de Hamilton pertenece a la clase de complejidad APX , es decir, es poco probable que existan algoritmos de aproximación de relación constante eficientes para este problema. [1]
El problema puede resolverse en tiempo polinómico para ciertas clases de gráficos, incluidos los gráficos en serie-paralelos [2] y sus generalizaciones, [3] que incluyen gráficos de plano exterior , así como para un gráfico lineal de un árbol [4] [5] o un gráfico de cactus . [6]
Gamarnik y col. use un algoritmo de tiempo lineal para resolver el problema en los árboles para estudiar el número asintótico de aristas que se deben agregar para gráficos aleatorios dispersos para hacerlos hamiltonianos.
No hay comentarios:
Publicar un comentario