Pre-processing Road Networks for Graph Partitioning Using Edge-Betweenness Centrality

Abstract

We propose a new pre-processing heuristic for partitioning road networks using multilevel graph partitioning (MGP) implementations. This heuristic is based on the notion that in road networks, edges with high betweenness centralities are often excellent cut-edge candidates. We pre-process the network in such a way that edges with low-betweenness centralities are contracted in the coarsening phase of an MGP algorithm, such that initial partitionings are formed along edges with high betweenness centralities. We find that our implementation of this pre-processing method significantly improves the edgecut when applied to national road networks partitioned using METIS.