2 PETER SANDERS AND CHRISTIAN SCHULZ
input
graph
... ...
initial
contraction
phase
refinement
phase
local improvement
uncontract
partitioning
contract
match
output
partition
Figure 1. Multilevel graph partitioning.
(Karlsruhe Parallel Partitioner) with focus on scalable parallelization. Somewhat
astonishingly, we also obtained improved partitioning quality through rather simple
methods. This motivated us to make a fresh start putting all aspects of MGP on
trial. This paper gives an overview over our most recent work, KaFFPa [22] and
KaFFPaE [21]. KaFFPa is a classical matching based graph partitioning algorithm
with focus on local improvement methods and overall search strategies. It is a
system that can be configured to either achieve the best known partitions for many
standard benchmark instances or to be the fastest available system for large graphs
while still improving partitioning quality compared to the previous fastest system.
KaFFPaE is a technique which integrates an evolutionary search algorithm with
our multilevel graph partitioner KaFFPa and its scalable parallelization. It uses
novel mutation and combine operators which in contrast to previous evolutionary
methods that use a graph partitioner [8,23] do not need random perturbations of
edge weights. The combine operators enable us to combine individuals of different
kinds (see Section 5 for more details). Due to the parallelization our system is able
to compute partitions that have quality comparable or better than previous entries
in Walshaw’s well known partitioning benchmark within a few minutes for graphs
of moderate size. Previous methods of Soper et. al [23] required runtimes of up to
one week for graphs of that size. We therefore believe that in contrast to previous
methods, our method is very valuable in the area of high performance computing.
The paper is organized as follows. We begin in Section 2 by introducing basic
concepts which is followed by related work in Section 3. In Section 4 we present
the techniques used in the multilevel graph partitioner KaFFPa. We continue
describing the main components of our evolutionary algorithm KaFFPaE in Sec-
tion 5. A summary of extensive experiments to evaluate the performance of the
algorithm is presented in Section 6. We have implemented these techniques in the
graph partitioner KaFFPaE (Karlsruhe Fast Flow Partitioner Evolutionary) which
is written in C++. Experiments reported in Section 6 indicate that KaFFPaE is
able to compute partitions of very high quality and scales well to large networks
and machines.
2. Preliminaries
2.1. Basic concepts. Consider an undirected graph G = (V, E, c, ω) with
edge weights ω : E R 0, node weights c : V R≥0, n = |V |, and = |E|.
We extend c and ω to sets, i.e., c(V ) :=

v∈V
c(v) and ω(E ) :=
∑m
e∈E
ω(e).
Γ(v) := {u : {v, u} E} denotes the neighbors of v. We are looking for blocks
of nodes V1,...,Vk that partition V , i.e., V1 · · · Vk = V and Vi Vj = for
i = j. The balancing constraint demands that ∀i {1..k} : c(Vi) Lmax :=
Previous Page Next Page