Em matemática, o problema de partição de grafos é definido com seus dados na forma de um grafo G = (V,A), com V vértices e A arestas, de tal modo que é possível particionar G em componentes menores com propriedades específicas. Por exemplo, uma partição de k-vias divide o conjunto de vértices em k componentes menores. Uma boa partição é definida como uma em que o número de arestas entre componentes menores é pequeno. Partição Uniforme de um Grafo é um tipo de problema de particionamento de grafo que consiste em dividir um grafo em componentes, no qual os componentes são quase do mesmo tamanho e existem algumas conexões entre esses componentes. Importantes aplicações de particionamento de grafos incluem computação específica, particionando vários estágios de um circuito feito em VSLI e agendamento de tarefas em sistemas com multi-processadores. Recentemente, o problema de partição de grafo ganhou importância devido à suas aplicações para clustering e detecção de associações em redes sociais, patológicas e biológicas. Uma pesquisa sobre as recentes tendências em métodos e aplicações computacionais podem ser encontrados em.
Problema da Complexidade
Geralmente, problemas de partição de grafos estão dentro da categoria dos problemas NP-Difíceis. Soluções para esses problemas são geralmente derivadas usando algoritmos de heurísticas de aproximação. Entretanto, o particionamento uniforme de um grafo ou particionamento equilibrado pode ser mostrado com uma aproximação NP-Completa com qualquer fator finito. Até para classes especiais de grafos como árvores e redes, não existem algoritmos de aproximação razoáveis a menos que P=NP. Redes são uma particularidade interessante visto que modelam um grafo resultante de simulações do Método dos elementos finitos (MEF). Quando não apenas o número de áreas entre componentes é próximo, mas também o tamanho dos componentes, é mostrado que não existe nenhum algoritmo polinomial razoável para estes tipos de grafos.
Problema Considere um grafo G = (V, A), onde V é o conjunto de n vértices e A o conjunto de arestas. Para um problema (k,v) de partição balanceada, o objetivo é particionar G em k componentes de tamanho máximo v·(n/k), enquanto minimiza a capacidade das arestas entre elementos separados. Também, dado o G e um inteiro k > 1, divida V em k partes (subconjuntos) V1, V2, ..., Vk sendo que essas partes devem ser disjuntas e ter o mesmo tamanho, e o número de arestas com pontos finais em diferentes partes é minimizado. Tais problemas de partições foram discutidos na literatura como aproximação de duplo critério ou abordagem de aproximação de recursos. Uma extensão comum são os hipergrafos, onde uma aresta pode conectar mais de dois vértices. Uma hiperaresta não é cortada se todos os vértices estão na mesma partição, e cortadas exatamente uma vez caso contrário, não importando quantos vértices estão em cada lado. Esse tipo de uso é comum em automação de design eletrônico.
Análise Para um problema específico balanceado (k, 1 + ε), procuramos encontrar o custo mínimo da partição de G em k elementos com cada componente contendo o máximo de (1 + ε)·(n/k) nós. Comparamos os custos desse algoritmo de aproximação ao custo de (k,1) cortes, em que cada um dos k componentes devem ter exatamente o mesmo tamanho de (n/k) nós cada, sendo, assim, um problema mais restrito. Todavia,
Já sabemos que o corte (2,1) é o corte mínimo do problema da bisseção e este é NP-Completo. Em seguida, avaliamos um problema 3-partições no qual n = 3k, que também é limitado em tempo polinomial. Agora, se assumirmos que temos um algoritmo de aproximação finita para (k, 1)-partições equilibradas, então, cada uma das instancias da 3-partição pode ser resolvida usando a partição balanceada (k,1) em G ou não pode ser resolvida. Se a instância de 3-partição pode ser resolvida então o problema do (k, 1)-particionamento balanceado em G pode ser resolvido sem cortar nenhuma aresta. Entretanto, se a instância 3-partição não pode ser resolvida, o (k, 1)-paticionamento balanceado ideal em G vai cortar pelo menos uma aresta. Um algoritmo de aproximação com fator de aproximação finito tem de diferenciar entre estes dois casos. Assim, pode-se resolver o problema da 3-partição no qual há uma contradição quando assume-se que P = NP. Entretanto, é evidente que um problema de (k,1)-particionamento balanceados não tem algoritmo de aproximação em tempo polinomial com fator de aproximação finito a menos que P = NP.
O teorema separador de planos diz que qualquer n-vértice do grafo planar pode ser particionado em partes aproximadamente iguais com a remoção de O(√n) vértices. Esta não é uma partição no sentido descrito anteriormente, porque a partição é nos vértices e não nas arestas. Porém, o mesmo resultado implica que cada grafo planar de of grau limitado tem um equilíbrio de corte com O(√n) arestas.
Métodos de partição de Grafos Visto que o problema de particionamento de grafos é um problema difícil, soluções práticas são baseadas em heurísticas. Existem duas heurísticas principais, local e global. Métodos locais bem conhecidos são os algoritmos de Kernighan–Lin, e algoritmos de Fiduccia-Mattheyses, que são os primeiros algoritmos 2-vias de corte que são eficientes usando estratégias de busca locais. A sua principal desvantagem é o particionamento inicial arbitrário do conjunto vértice, que pode afetar a qualidade final da solução. A aproximação global dependem de propriedades do grafo inteiro e não só de uma partição arbitrária inicial. O exemplo mais conhecido é o espectro de partição, onde uma partição é derivada de um espectro de matrizes de adjacência.
Métodos de multi-nível Um algoritmo de particionamento de grafos multi-nível funciona aplicando um ou mais estágios. Cada estágio reduz o tamanho de um grafo por pela eliminação de vértices e arestas, divisórias no grafo menor, em seguida, mapeia novamente e refina esta partição do grafo original. Uma grande variedade de métodos de particionamento e refinamento pode ser aplicado no conjunto do sistema multi-nível. Em muitos casos, esta aproximação pode nos dar tempo de execução mais rápido e resultados de alta qualidade. Um exemplo que é muito utilizado dessa aproximação é o METIS, um particionador de grafos, e o hMETIS, o mesmo particionador mas para hipergrafos.
Particionamento de espectro e espectro de bisseção Dado um grafo com a matriz de adjacência A, onde uma entrada Aij implica uma aresta entre os nós i e j, e a matriz de nível D, que é uma matriz diagonal, onde cada entrada na diagonal de uma linha i, dii, representa o grau/nível de um nó i. A Matriz de Laplace L é definida como L = D − A. Agora, uma partição na proporção de corte de G = (V, E) é definida como uma partição de V na disjunção U, e W, de tal modo que o custo de corte (U,W)/(|U|·|W|) é minimizado.
Em tal cenário, o segundo menor autovalor (λ) de L, produz um limite inferior para o custo ótimo (c) de partição de corte com relação c ≥ λ/n. O autovetor (V) correspondente à λ, chamado de vetor de Fiedler, bissecciona o grafo em apenas duas comunidades baseadas no sinal da entrada do vetor correspondente. Dividindo em um número maior de comunidades é geralmente atingido ao fazendo bisseções repetidas, mas nem sempre isso dá resultados satisfatórios. Os exemplos nas figuras 1 e 2 mostram o espectro de bisseção.
thumb|Figura 2: O grafo G = (5,5) ilustra que o vetor de Fiedler em vermelho corta o grafo em duas comunidades, uma com vértices {1,2,3} com entradas positivas no espaço vetorial, e outra comunidade tem vértices {4,5} com entradas de espaço de vetor negativos.
Particionamento mínimo corte no entanto falha quando o número de comunidades a ser particionado, ou o tamanho das partições são desconhecidas. Por exemplo, otimizando o tamanho do corte para grupos de tamanho qualquer coloca todos os vértices na mesma comunidade. Além disso, o tamanho do corte pode ser a coisa errada a minimizar uma vez que uma boa divisão não é apenas aquele com pequeno número de arestas entre as comunidades. Isso motivou o uso da Modularidade (Q) como uma métrica para otimizar e balancear uma partição de grafo. O exemplo na figura 3 ilustra 2 instâncias do mesmo grafo de modo que em (a) modularidade (Q) representa a métrica de particionamento e em (b), proporção de corte representa a métrica de particionamento. Entretanto, sabe-se que Q sofre um limite de resolução, produzindo resultados duvidosos quando está lidando com comunidades pequenas. Neste contexto, Surprise foi proposta como uma alternativa de aproximação para a avaliação de qualidade de uma partição.
thumb|Figura 3: Grafo ponderado G pode ser particionado para maximizar Q em (a) ou para minimizar a proporção de corte em (b). Nós vemos que (a) é uma melhor partição balanceada, motivando, assim, a importância da modularidade em problemas de particionamento de grafos.
Outros métodos de partição Modelos de spin têm sido usados para o agrupamento de dados multivariados que similaridades são convertidas em forças de acoplamento. As propriedades de configuração de spin do estado fundamental pode ser diretamente interpretado como comunidades. Entretanto, um grafo é particionado para minimizar o Hamiltoniano do grafo particionado. O Hamiltoniano (H) é derivado por atribuindo as seguintes recompensas partição e penalidades. Recompensas para arestas internas entre nós do mesmo grupo (mesmo spin) Penaliza arestas que faltam no mesmo grupo Penaliza arestas existentes entre diferentes grupos Recompensar a falta de ligações entre os diferentes grupos.
Adicionalmente, clusterings baseados em Kernel PCA tomam a forma de mínimos quadrados com suporte ao framework Vector Machine, e, portanto, torna-se possível projetar as entradas de dados para um espaço de características do kernel induzida que tem variação máxima, implicando, assim, uma alta de separação entre as comunidades projetadas
Alguns métodos expressam o particionamento de grafo como um problema de otimização multi-critérios que podem ser resolvidos através de métodos locais expressos em um framework teórico de jogo onde cada nó faz uma decisão sobre a partição que ele escolhe.Kurve, Griffin, Kesidis (2011) "A graph partitioning game for distributed simulation of networks" Proceedings of the 2011 International Workshop on Modeling, Analysis, and Control of Complex Networks: 9 -16
Ferramentas de Software
Um dos primeiros pacotes de software disponibilizados ao público é chamado Chaco devido à Hendrickson e Leland. Como a maioria dos pacotes de software disponíveis publicamente, Chaco implementa a abordagem a vários níveis descritos acima e básicos algoritmos de busca local. Além disso, implementar técnicas de separação espectral.
METIS é um grafo de particionamento conhecido, criado por Karypis and Kumar. kMetis é focado em particionamento rápido e hMetis, que é um particionador de hipergrafos, visa a qualidade de particionamento. ParMetis é uma implementação paralela do algoritmo de particionamento de grafos Metis.
PaToH é também largamente utilizado como particionador de hipergrafos que produz partições de alta qualidade.
Scotch é um framework de grafos criado por Pellegrini. Ele usa bisseção recursiva multinível e inclui sequencial, bem como técnicas de separação paralelas.
Jostle é um particionamento grafo sequencial e paralelo solver desenvolvido por Chris Walshaw. a versão comercializada dele é conhecida como NetWorks.
Se um modelo de rede de comunicação está disponível, então Jostle e Scotch são capazes de construir este modelo levando em consideração o processo de particionamento.
Party implementa a o framework Bubble/shape-optimized e o algoritmo de Conjuntos Úteis.
O pacote de software DibaP e seu variante MPI-parallelo PDibaP por Meyerhenke implementar o framework Bubble usando difusão; DibaP também usa técnicas baseadas em AMG para fortalicer e resolver sistemas lineares que surgem na abordagem difusiva.