Maintaining Connectivity in Parallel Graph Partitioning
Motivation
Partitioning graphs is an important task inparallel scientific computing and graph analysis
applications to balance work per-task and minimize
communication. For large graphs and meshes, parallelizing the partitioning process is heavily desired.
If parts within a partition remain connected,
they can allow simpler computations and reduce
the number of very small components that aredisconnected from the rest of their part.
Applications for partitioning:• Parallel graph analysis using clusters• Scientific computing of fine meshes, which
desires connectivity and multi-weight vertices• Problem solving in biology, power grids, image
processing, and many more [3]• Redistricting, which requires connectivity,and can reduce gerrymandering issues [2]Christopher I. Jones
Ian Bogle
jonesc10@rpi.edu
boglei@rpi.edu
Methods for Maintaining Connectivity
We are building upon an existing PuLP [1] algorithm, adding features and functionality toaid connectivity. The original algorithm has 2
inner iterations:

Merge Small Components

Restrict Vertex Movement

Additional Metrics
Add a new metric to the gain equation
by 2 methods:(1)
gain(P ) = (nP + aP ) · wPaP(2)gain(P ) = nP · wP /a• Balance focuses on balancing thevertices between parts. Each vertex considers the gain to being inpart P :gain(P ) = nP · wP

X children(u)aP =d(u)u∈N (v)u∈P

Ideally, each part has one component. Calculate BFS trees on each component,
Every some number of iterations, merge and only allow the leaves to move. Or,
Where N (v) is the neighborhood of v,
allcomponents
thatarenotthelargest
everysomanyvertex
movements,
calcuchildren(u) is the number of children u has in• Refine works on minimizing theintheirpart
intoaneighboring
compolatebi-connectivity,
andprevent
articthe component’s BFS tree, and d(u) is the deedge cut relative to each vertex.
nent.
ulation points from moving.
gree of u.
nP is the number of neighbors in P .
wP is how underweight P is.

Results
Restrict Vertex Movement

Additional Metrics

CVertex
OverweightEdge
Cut

Small Comp.
CountVertex
OverweightEdgeCut012∞

1.5-2.5
1.1-1.2≤ 1.1<1.1>1,000K
800K650K150K0
4,000
5,000
5,500

1.039
1.040
1.057

125.4K
125.5K434.4K

Merge Small Components
Social Network Metrics During Merge Iterations

Background
Graph partitioning typically is the process of creating vertex-disjoint sets on a graph that minimize
edge cut and constrain weight per-part. This projectfocuses on adding an additional constraint: connectivity. It is common for partitioning algorithms to
not guarantee connected partitions, but it can be ahighly desired feature.
Several categories of graph partitioning algorithms exist. Global algorithms work with theentire graph and compute a direct solution, andthey’re mainly used for smaller graphs. Iterativeimprovement heuristics gradually improve partitions from an initial starting position. These take asmall set of vertices at a time and move them to thebest suited part. Multilevel algorithms condense
the graph small enough to do an initial partitioning,then work back and uncondense the graph [3].
The work done in this project is built on an existing algorithm: Partitioning using Label Propagation (PuLP) [1]. PuLP has achieved good vertex
balancing and edge cut, while obtaining greatly improved runtime and memory usage over other partitioning algorithms. The results of this will be integrated into PuLP to address connectivity issues.

George M. Slota
slotag@rpi.edu

Normal alg.
Method (1)Method (2)Leaves Only Method: Results are from a web-crawl graphwhere only vertices with C or less children are allowed to move.
R

10K

2.5K

1,250

320

80Comp. Count

2,000

1,500

1,400

1,275

1,200

Merging works decently for some graphs, such as a road network, while sacrificing some of the vertex balancing and edge Articulation Point Method: Running on a road network
cut. But for other complex graphs, like a social network, ver- graph, biconnectivity is recalculated every R vertex updates.
tices are thrown way off balance.
The original algorithm outputs only around 130 components.

Application: Political Redistricting
Gerrymandering is the issue ofpoliticians manipulating districts
based on where voters live. Translating the redistricting problem tograph partitioning, census blocks
Gerrymandering: North Carolina
are vertices, districts are parts,districts from 2013-2016.
and edges represent shared borders.
Previous work includes
PEAR [2], which is an evolutionary
algorithm. We’ve applied PuLP tocounties in North Carolina, using
population demographics as vertex
weights and border lengths as edge PuLP: A redistricting using PuLP withsmall component merging.
weights.

Small Components
Count
Size
6,100
5,800
14,400

22.17
22.53
13.94

Add Merging as a Final Step:
Normal alg.
Method (1)Method (2)

1.182
1.174
1.081

94.5K
95.3K
356K

000

N/A
N/A
N/A

Using an Additional Metric: These numbers are from a
web-crawl graph when adding the Average Number of Childrenmetric, aP . Method (2) produces many components that arerelatively small, allowing those components to be easily merged.

Acknowledgements
Redistricting introduces new metrics that can be taken into consideration, such as compactness andcompetitiveness, as defined in [2].
Compactness is related to how
well connected a district is andis defined as the area divided byperimeter squared. Competitiveness takes the numbers of votersin opposing parties to measure how
evenly they’re distributed in thedistricts. Other demographic data
can also be considered.

This work was supported in part by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Scientific Discovery through Advanced Computing (SciDAC)
program through the FASTMath Institute under Contract No. DEAC02-05CH11231 at Rensselaer Polytechnic Institute and Sandia National Laboratories. Sandia National Laboratories is a multimission
laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy’s NationalNuclear Security Administration under contract DE-NA-0003525.

References[1] G. Slota, K. Madduri, S. Rajamanickam PULP: Scalable MultiObjective Multi-Constraint Partitioning for Small-World Networks
In Proc. IEEE BigData Conf., 2014.
[2] Y. Y. Liu, W. K. T. Cho, S. Wang PEAR: a massively parallel
evolutionary computation approach for political redistricting optimization and analysis. In Swarm and Evolutionary Computation,
30, 78-92, 2016.
[3] A. Buluc, H. Meyerhenke, I. Safro, P. Sanders, C. Schulz Recent
Advances in Graph Partitioning In Algorithm Engineering, 2016.