### Tree-Based Coarsening and Partitioning of Complex NetworksTree-Based Coarsening and Partitioning of Complex Networks

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

Source: ACM Digital Library