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 vertices 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-modos 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 parathe graph partition problem has gained importance due to its application for 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. Entretando, 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 à 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 areas 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 areastas com pontos finais em diferentes partes é minimizado. Tais problemas de partições foram discutidos na literatura como aproximação-bicriteria ou abordagem de aproximação de recursos. Uma extensão comum são os hypergrafos, onde uma areas pode conectar mais de dois vértices. Uma hyperaresta 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 + ε) , nós procuramos encontrar o custo mínimo da partição de G emk elementos com cada componente contendo o máximo de (1 + ε)·(n/k) nós. 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 .$

nós já sabemos que o corte (2,1) é o corte minimo do problema da bisecçã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õa, 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 à menos que P = NP.

O teorema separador de planos diz que qualquer n-vértice do grafo planar pode ser particionado em can be partitioned into 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 equilibrio 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. There are two broad categories of methods, local e global. Métodos locais bem conhecidos são os Kernighan–algoritmos de 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 espéctro 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 particionalmento de grafos multi-nível funciona aplicando um ou mais estágios. Cada estágio reduz o tamanho de um grafo por by collapsing vertices and edges, partitions the smaller graph, then maps back and refines this partition of the original graph. A wide variety of partitioning and refinement methods can be applied within the overall multi-level scheme. In many cases, this approach can give both fast execution times and very high quality results. One widely used example of such an approach is METIS, a graph partitioner, and hMETIS, the corresponding partitioner for hypergraphs.

Spectral partitioning and spectral bisection

Given a graph with adjacency matrix A, where an entry A_ij implies an edge between node i and j, and degree matrix D, which is a diagonal matrix, where each diagonal entry of a row i, d_ii, represents the node degree of node i. The Laplacian of the matrix L is defined as L = D − A. Now, a ratio-cut partition for graph G = (V, E) is defined as a partition of V into disjoint U, and W, such that cost of cut(U,W)/(|U|·|W|) is minimized.

In such a scenario, the second smallest eigenvalue (λ) of L, yields a lower bound on the optimal cost (c) of ratio-cut partition with c ≥ λ/n. The eigenvector (V) corresponding to λ, called the Fiedler vector, bisects the graph into only two communities based on the sign of the corresponding vector entry. Division into a larger number of communities is usually achieved by repeated bisection, but this does not always give satisfactory results. The examples in Figures 1,2 illustrate the spectral bisection approach.

Figure 1: The graph G = (5,4) is analysed for spectral bisection. The linear combination of the smallest two eigenvectors leads to [1 1 1 1 1]' having an eigen value = 0.

Figure 2: The graph G = (5,5) illustrates that the Fiedler vector in red bisects the graph into two communities, one with vertices {1,2,3} with positive entries in the vector space, and the other community has vertices {4,5} with negative vector space entries.

Minimum cut partitioning however fails when the number of communities to be partitioned, or the partition sizes are unknown. For instance, optimizing the cut size for free group sizes puts all vertices in the same community. Additionally, cut size may be the wrong thing to minimize since a good division is not just one with small number of edges between communities. This motivated the use of Modularity (Q) as a metric to optimize a balanced graph partition. The example in Figure 3 illustrates 2 instances of the same graph such that in (a) modularity (Q) is the partitioning metric and in (b), ratio-cut is the partitioning metric. However, it is well-known that Q suffers a resolution limit, producing unreliable results when dealing with small communities. In this context, Surprise has been proposed as an alternative approach for evaluating the quality of a partition.

Figure 3: Weighted graph G may be partitioned to maximize Q in (a) or to minimize the ratio-cut in (b). We see that (a) is a better balanced partition, thus motivating the importance of modularity in graph partitioning problems.

Other graph partition methods

Spin models have been used for clustering of multivariate data wherein similarities are translated into coupling strengths. The properties of ground state spin configuration can be directly interpreted as communities. Thus, a graph is partitioned to minimize the Hamiltonian of the partitioned graph. The Hamiltonian (H) is derived by assigning the following partition rewards and penalties.

• Reward internal edges between nodes of same group (same spin)
• Penalize missing edges in same group
• Penalize existing edges between different groups
• Reward non-links between different groups.

Additionally, Kernel PCA based Spectral clustering takes a form of least squares Support Vector Machine framework, and hence it becomes possible to project the data entries to a kernel induced feature space that has maximal variance, thus implying a high separation between the projected communities

Some methods express graph partitioning as a multi-criteria optimization problem which can be solved using local methods expressed in a game theoretic framework where each node makes a decision on the partition it chooses.

Software tools

One of the first^{[carece de fontes]} publicly available software packages called Chaco is due to Hendrickson and Leland. As most of the publicly available software packages,^{[carece de fontes]} Chaco implements the multilevel approach outlined above and basic local search algorithms. Moreover, they implement spectral partitioning techniques.

METIS is a graph partitioning family by Karypis and Kumar. kMetis is focusedPredefinição:Weasel-inline on partitioning speed and hMetis, which is a hypergraph partitioner, aims at partition quality.Predefinição:Weasel-inline ParMetis is a parallel implementation of the Metis graph partitioning algorithm.

PaToH is also a widely^{[carece de fontes]} used hypergraph partitioner that produces high quality^{[carece de fontes]} partitions.

Scotch is graph partitioning framework by Pellegrini. It uses recursive multilevel bisection and includes sequential as well as parallel partitioning techniques.

Jostle is a sequential and parallel graph partitioning solver developed by Chris Walshaw. The commercialized version of this partitioner is known as NetWorks.

If a model of the communication network is available, then Jostle and Scotch are able to take this model into account for the partitioning process.^{[carece de fontes]}

Party implements the Bubble/shape-optimized framework and the Helpful Sets algorithm.

The software packages DibaP and its MPI-parallel variant PDibaP by Meyerhenke implement the Bubble framework using diffusion; DibaP also uses AMG-based techniques for coarsening and solving linear systems arising in the diffusive approach.

Sanders and Schulz released a graph partitioning package KaHIP (Karlsruhe High Quality Partitioning) focusing on solution quality.Predefinição:Peacock-term It implements for example flow-based methods, more-localized local searches and several parallel and sequential meta-heuristics.

To address the load balancing problem in parallel applications, distributed versions of the sequential partitioners Metis, Jostle and Scotch have been developed. ^{[carece de fontes]}

The tools Parkway by Trifunovic and Knottenbelt as well as Zoltan by Devine et al. focus on hypergraph partitioning.

List of free open-source frameworks:

Name	License	Brief info
Chaco	GPL	software package implementing spectral techniques and the multilevel approach
DiBaP	*	graph partitioning based on multilevel techniques, algebraic multigrid as well as graph based diffusion
Jostle	*	multilevel partitioning techniques and diffusive load-balancing, sequential and parallel
KaHIP	GPL	several parallel and sequential meta-heuristics, guarantees the balance constraint
kMetis	Apache 2.0	graph partitioning package based on multilevel techniques and k-way local search
Mondriaan	LGPL	matrix partitioner to partition rectangular sparse matrices
PaToH	BSD	multilevel hypergraph partitioning
Parkway	*	parallel multilevel hypergraph partitioning
Scotch	CeCILL-C	implements multilevel recursive bisection as well as diffusion techniques, sequential and parallel
Zoltan	BSD	hypergraph partitioning

External links

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

Bibliography

• 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  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  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. (March 1999). «Multilevel hypergraph partitioning: applications in VLSI domain». IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 7 (1): pp. 69–79. doi:10.1109/92.748202  !CS1 manut: Texto extra (link) !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 May 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. (September 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.