Partição de grafos

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) V₁, V₂, ..., V_k 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,

$\max _{i}|V_{i}|\leq (1+\varepsilon )\left\lceil {\frac {|V|}{k}}\right\rceil .$

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 A_ij 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, d_ii, 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.

Figura 1: O grafo G = (5,4) é analisado com bisseção espectral. A combinação linear dos dois menores autovetores leva a [1 1 1 1 1]' possuindo um autovalor = 0.

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.

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.

Ferramentas de Software

Um dos primeiros^{[carece de fontes]} pacotes de software disponibilizados ao público é chamado Chaco devido à Hendrickson e Leland. Como a maioria dos pacotes de software disponíveis publicamente,^{[carece de fontes]} 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 é focadoPredefinição:Weasel-inline em particionamento rápido e hMetis, que é um particionador de hipergrafos, visa a qualidade de particionamento. Predefinição:Weasel-inline ParMetis é uma implementação paralela do algoritmo de particionamento de grafos Metis.

PaToH é também largamente utilizado ^{[carece de fontes]} como particionador de hipergrafos que produz partições de alta qualidade^{[carece de fontes]}.

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.^{[carece de fontes]}

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.

Sanders e Schulz divulgou um pacote de particionamento de grafos chamado KaHIP (Karlsruhe High Quality Partitioning) forcando em soluções da qualidade.Predefinição:Peacock-term Ele implementa por exemplo métodos baseados em fluxos, pesquisas locais mais localizada, e várias meta-heurísticas paralelas e sequenciais.

Para resolver o problema de balanceamento de carga em aplicações paralelas, versões distribuídas dos particionadores sequenciais Metis, Jostle e Scotch têm sido desenvolvidos. ^{[carece de fontes]}

As ferramentas Parkway por Trifunovic e Knottenbelt e também Zoltan por Devine et al. focam em particionamento de hipergrafos.

Lista de frameworks de código aberto grátis:

Npme	Licença	Breve Descrição
Chaco	GPL	pacote de software da implementação de técnicas espectrais e a abordagem multinível
DiBaP	*	particionamento gráfico baseado em técnicas de vários níveis, algébrica multigrid, bem como gráfico baseado difusão
Jostle	*	técnicas multinível de separação e difusão de balanceamento de carga, seqüencial e paralelo
KaHIP	GPL	várias meta-heurísticas paralelas e seqüenciais, garante a limitação de equilíbrio
kMetis	Apache 2.0	pacote de particionamento de grafos com base em técnicas de vários níveis e k-vias de busca local
Mondriaan	LGPL	particionador de matriz para particionar matrizes esparsas retangulares
PaToH	BSD	particionamento multi-nível de hipergrafos
Parkway	*	particionamento hipergrafo multinível paralelo
Scotch	CeCILL-C	implementa bisseção recursiva multinível, bem como técnicas de difusão, seqüencial e paralelo
Zoltan	BSD	particionamento de hipergrafo

Ligações externas

• Chamberlain, Bradford L. (1998). "Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations"

Bibliografia

• Charles-Edmond Bichot, Patrick Siarry (2011). Graph Partitioning: Optimisation and Applications. [S.l.]: ISTE – Wiley. 384 páginas. ISBN 978-1848212336 
• Feldmann, Andreas Emil (2012). Balanced Partitioning of Grids and Related Graphs: A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations (PDF). Goettingen, Germany: Cuvillier Verlag. 218 páginas. ISBN 978-3954041251 ^{[ligação inativa]} An exhaustive analysis of the problem from a theoretical point of view.
• BW Kernighan, S Lin (1970). «An efficient heuristic procedure for partitioning graphs» (PDF). Bell System Technical Journal. Consultado em 9 de agosto de 2014. Arquivado do original (PDF) em 2 de março de 2012  One of the early fundamental works in the field. However, performance is O(n²), so it is no longer commonly used.
• CM Fiduccia, RM Mattheyses (1982). «A Linear-Time Heuristic for Improving Network Partitions». Design Automation Conference  A later variant that is linear time, very commonly used, both by itself and as part of multilevel partitioning, see below.
• G Karypis, V Kumar (1999). «A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs». Siam Journal on Scientific Computing  Multi-level partitioning is the current state of the art. This paper also has good explanations of many other methods, and comparisons of the various methods on a wide variety of problems.
• Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. (março de 1999). «Multilevel hypergraph partitioning: applications in VLSI domain». IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 7 (1): 69–79. doi:10.1109/92.748202  !CS1 manut: Nomes múltiplos: lista de autores (link) Graph partitioning (and in particular, hypergraph partitioning) has many applications to IC design.
• S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi (13 de maio de 1983). «Optimization by Simulated Annealing». Science. 220 (4598): 671–680. PMID 17813860. doi:10.1126/science.220.4598.671  !CS1 manut: Nomes múltiplos: lista de autores (link) Simulated annealing can be used as well.
• Hagen, L. and Kahng, A.B. (setembro de 1992). «New spectral methods for ratio cut partitioning and clustering». IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 11,  (9): 1074–1085. doi:10.1109/43.159993  !CS1 manut: Nomes múltiplos: lista de autores (link). There is a whole class of spectral partitioning methods, which use the Eigenvectors of the Laplacian of the connectivity graph. You can see a demo of this, using Matlab.