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.[1] 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.[2]
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.[3] Entretanto, o particionamento uniforme de um grafo ou particionamento equilibrado pode ser mostrado com uma aproximação NP-Completa com qualquer fator finito.[1] Até para classes especiais de grafos como árvores e redes, não existem algoritmos de aproximação razoáveis[4] 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.[4]
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.[1] 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.[5] Em seguida, avaliamos um problema 3-partições no qual n = 3k, que também é limitado em tempo polinomial.[1] 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.[1]
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.[6] 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,[7] um particionador de grafos, e o hMETIS, o mesmo particionador mas para hipergrafos.[8]
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Bisected_network.jpg/220px-Bisected_network.jpg)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Connected_graph..jpg/220px-Connected_graph..jpg)
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) [9] 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[10] foi proposta como uma alternativa de aproximação para a avaliação de qualidade de uma partição.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/96/Graph_comparison.jpg/220px-Graph_comparison.jpg)
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.[11] 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 [12]
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.[13]
Ferramentas de Software
Um dos primeiros[carece de fontes?] pacotes de software disponibilizados ao público é chamado Chaco[14] 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[7] é um grafo de particionamento conhecido, criado por Karypis and Kumar. kMetis é focadoPredefinição:Weasel-inline em particionamento rápido e hMetis,[8] que é um particionador de hipergrafos, visa a qualidade de particionamento. Predefinição:Weasel-inline ParMetis[7] é uma implementação paralela do algoritmo de particionamento de grafos Metis.
PaToH[15] é também largamente utilizado [carece de fontes?] como particionador de hipergrafos que produz partições de alta qualidade[carece de fontes?].
Scotch[16] é 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[17] é 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[18] implementa a o framework Bubble/shape-optimized e o algoritmo de Conjuntos Úteis.
O pacote de software DibaP[19] e seu variante MPI-parallelo PDibaP[20] 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[21] (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[22] por Trifunovic e Knottenbelt e também Zoltan[23] 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 |
Referências
- ↑ a b c d e Andreev, Konstantin and Räcke, Harald, (2004). «Balanced Graph Partitioning». Barcelona, Spain. Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures: 120–124. ISBN 1-58113-840-7. doi:10.1145/1007912.1007931 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ Aydin Buluc and Henning Meyerhenke and Ilya Safro and Peter Sanders and Christian Schulz (2013). «Recent Advances in Graph Partitioning». 36 páginas
- ↑ Feldmann, Andreas Emil and Foschini, Luca (2012). «Balanced Partitions of Trees and Applications». Paris, France. Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science: 100–111 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ a b Feldmann, Andreas Emil (2012). «Fast Balanced Partitioning is Hard, Even on Grids and Trees». Bratislava, Slovakia. Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science
- ↑ Garey, Michael R. and Johnson, David S. (1979). Computers and intractability: A guide to the theory of NP-completeness. [S.l.]: W. H. Freeman & Co. ISBN 0-7167-1044-7 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ Hendrickson, B. and Leland, R. (1995). A multilevel algorithm for partitioning graphs. Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM. 28 páginas !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ a b c Karypis, G. and Kumar, V. (1999). «A fast and high quality multilevel scheme for partitioning irregular graphs». SIAM Journal on Scientific Computing. 20 (1). 359 páginas. doi:10.1137/S1064827595287997 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ a b Karypis, G. and Aggarwal, R. and Kumar, V. and Shekhar, S. (1997). «Multilevel hypergraph partitioning: application in VLSI domain». Proceedings of the 34th annual Design Automation Conference. pp. 526–529 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ Newman, M. E. J. (2006). «Modularity and community structure in networks». PNAS. 103 (23): 8577–8696. PMC 1482622
. PMID 16723398. doi:10.1073/pnas.0601602103
- ↑ Rodrigo Aldecoa and Ignacio Marín (2011). «Deciphering network community structure by Surprise». PLoS ONE. 6 (9): e24195. PMC 3164713
. PMID 21909420. doi:10.1371/journal.pone.0024195
- ↑ Reichardt, Jörg and Bornholdt, Stefan (julho de 2006). «Statistical mechanics of community detection». Phys. Rev. E. 74 (1). 016110 páginas. doi:10.1103/PhysRevE.74.016110 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ Carlos Alzate and Johan A.K. Suykens (2010). «Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA». IEEE Computer Society. IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (2): 335–347. ISSN 0162-8828. PMID 20075462. doi:10.1109/TPAMI.2008.292
- ↑ 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
- ↑ Bruce Hendrickson. «Chaco: Software for Partitioning Graphs»
- ↑ Ü. Catalyürek and C. Aykanat (2011). PaToH: Partitioning Tool for Hypergraphs
- ↑ C. Chevalier and F. Pellegrini (2008). «PT-Scotch: A Tool for Efficient Parallel Graph Ordering». Parallel Computing. 34 (6): 318–331. doi:10.1016/j.parco.2007.12.001
- ↑ C. Walshaw and M. Cross (2000). «Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm». Journal on Scientific Computing. 22 (1): 63–80. doi:10.1137/s1064827598337373
- ↑ R. Diekmann, R. Preis, F. Schlimbach and C. Walshaw (2000). «Shape-optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM». Parallel Computing. 26 (12): 1555–1581. doi:10.1016/s0167-8191(00)00043-0 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ H. Meyerhenke and B. Monien and T. Sauerwald (2008). «A New Diffusion-Based Multilevel Algorithm for Computing Graph Partitions». Journal of Parallel Computing and Distributed Computing. 69 (9): 750–761. doi:10.1016/j.jpdc.2009.04.005
- ↑ H. Meyerhenke (2013). «Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations.». 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering. pp. 67–82
- ↑ P. Sanders and C. Schulz (2011). «Engineering Multilevel Graph Partitioning Algorithms». Proceeings of the 19th European Symposium on Algorithms (ESA). 6942. pp. 469–480
- ↑ A. Trifunovic and W. J. Knottenbelt (2008). «Parallel Multilevel Algorithms for Hypergraph Partitioning». Journal of Parallel and Distributed Computing. 68 (5): 563–581. doi:10.1016/j.jpdc.2007.11.002
- ↑ K. Devine and E. Boman and R. Heaphy and R. Bisseling and Ü. Catalyurek (2006). «Parallel Hypergraph Partitioning for Scientific Computing». Proceedings of the 20th International Conference on Parallel and Distributed Processing. pp. 124–124
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(n2), 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.