User:Cycrax/sandbox

The multi-level technique is a heuristic to efficiently generate a high quality solution for the graph partitioning problem. The procedure is summarized in 3 phases.

1. Coarsening: The graph is reduced in size using edge contractions.
2. Initial Partitioning: An interim partition on the smaller graph is generated using computationally expensive algorithms.
3. Refinement: The original graph is restored and the partition is improved by reassigning nodes to different blocks.

A depiction of the multilevel technique for graph partitioning showing contractions as larger nodes, partitions as

Problem

Graph partitioning

A graph $G:=(V,E)$ with nodes $V$ and edges $E$

Partition

A partition $p$ seperates the graph into $k$ blocks $V_{1},V_{2},...V_{k}$ so that every node $v$ is assigned to exactly one block $V_{i}$.

Balance

A partition is balanced if the blocks $V_{1},V_{2},...V_{k}$ are about equal in size. $\max |V_{i}|$

Cut

The cut is the weight of edges which connect nodes in different blocks. $cut(p):=\sum _{e\in E'}w(e')$

Finding a balanced partition is NP-hard.

Coarsening

During the coarsening phase the original graph $G_{0}$ is iteratively reduced to smaller graphs $G_{1},G_{2},...,G_{n}$. Coarsening reduces pairs of nodes $(u,v)$ in $G_{i}$ to a single node $u'$ in $G_{i+1}$. The size of $u'$ is increased to maintain the balance ratio and structure of the original graph. Heavier edges are intuitive contraction candidates as they are most likely in the same partition block in a good cut. Special care must be taken to not violate the balance constraint by contracting too many nodes into one representative node. The following techniques are commonly used to determine good contraction candidates:

An example for edge contractions. In the first step node $x$ and $u$ are contracted. Since v has a connection to x as well as u the weight of the edge (u',v) increases in $G_{1}$.

Matching

Main article: Matching_(graph_theory)

On each $G_{i}$ a matching algorithm can determine multiple reasonable contraction targets. By contracting all matched nodes the graph $G_{i+1}$ is reduced in size. No need for maximum matching, maximal matching or "reasonable" matching sufficient. Heavy weight matching. Parallel: Splitting modes into groups can cause communication issues, do collision reduction. Restricted matching (ParMetis); probabilistic matching (Folding can help; reduce the number of processes if your graph gets too small)

Label Propagation

Main article: Label_propagation_algorithm

Clustering $O(n+m)$. Parallel Clustering $O(n+m)$ work, and $O(n+m/p+logp)$ span. The nodes of the cluster are contracted to one supernode. Parallelization gives each processor a subgraph of contigous nodes a..b. Nodes change their blocks (Ghostnodes).

Flow Networks

Main article: Flow network

Initial Partitioning

Initial Partitioning will generate a partition on the coarsest graph G_p. Due to the size reduction by the coarsening phase, the graph is sufficiently small to utilize a runtime expensive algorithm to generate a good quality partition. This can be parallelized by running multiple intances with different randomizers.

Flow network

Setting a source and sink allows a flow to be put on the graph. Max-Flow-min-cut theroremMax-flow_min-cut_theorem. Max-flow estimated runtime $O(smt.)$

Refinement

In order to produce a solution for the original problem G_0 the graph is coarsening steps are reversed. Uncoarsening alone does induce a valid solution for G_0. However, by applying a heuristic during each iteration of the uncoarsening, the solution can be improved. Important to note, the balance must be maintained. Usual algorithms include FM, hillclimber(TODO: parallel. there are good methods to parallelize this).

Multitry k-way Local Search

Parallelizeable

Wallshaw-Cross

Parallel Refinement (refuses to be good under parallelizing the sequential algorithm citation needed) Refinement Diffusion(Book)

parmetis.pdf 2high_quality_shared_graph_partitioning.pdf 3graph partitioning book

4Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs 5Parallel graph parttiioning for complex networks 6 Graph partitioning is NP-hard 7 8 9 10 The multi-level technique has shown to significantly improve the results, in terms of both quality and running time. Especially when used on heuristics considering the graph only locally, as the multi-level technique constitutes a more global view on the graph.

Literature

Category:Graph theory