Thumbnail
Access Restriction
Subscribed

Author Glantz, Roland ♦ Meyerhenke, Henning ♦ Schulz, Christian
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Graph coarsening ♦ Complex networks ♦ Conductance ♦ Fundamental cuts ♦ Multilevel graph partitioning ♦ Spanning trees
Abstract A hierarchy of increasingly coarse versions of a network allows one to represent the network on multiple scales at the same time. Often, the elementary operation for generating a hierarchy on a network is merging adjacent vertices, an operation that can be realized through contracting the edge between the two vertices. Such a hierarchy is defined by the selection of the edges to be contracted between a level and the next coarser level. The selection may involve (i) rating the edges, (ii) constraining the selection (e.g., that the selected edges form a matching), as well as (iii) maximizing the total rate of the selected edges under the constraints. Hierarchies of this kind are, among others, involved in multilevel methods for partitioning networks—a prerequisite for processing in parallel with distributed memory. In this article, we propose a new edge rating by (i) defining weights for the edges of a network that express the edges’ importance for connectivity via shortest paths, (ii) computing a minimum weight spanning tree with respect to these weights, and (iii) rating the network edges based on the conductance values of the tree’s fundamental cuts. To make the computation of our new edge rating efficient, we develop the first optimal linear-time algorithm to compute the conductance values of $\textit{all}$ fundamental cuts of a given spanning tree. We integrate the new edge rating into a leading multilevel graph partitioner and equip the latter also with a new greedy postprocessing for optimizing the Maximum Communication Volume (MCV) of a partition. Our experiments, in which we bipartition frequently used benchmark networks, show that the postprocessing reduces MCV by 11.3%. Our new edge rating, here used for matching-based coarsening, further reduces MCV by 10.3% compared to the previously best rating with MCV postprocessing in place for both ratings. In total, with a modest increase in running time, our new approach reduces the MCV of complex network partitions by 20.4%.
Description Author Affiliation: Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany (Glantz, Roland; Meyerhenke, Henning; Schulz, Christian)
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-01-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 21
Page Count 20
Starting Page 1
Ending Page 20


Open content in new tab

   Open content in new tab
Source: ACM Digital Library