Multilevel Algorithms for Partitioning Power-Law Graphs

Abstract

Graph partitioning is an enabling technology for parallel processing as it allows for the effective decomposition of unstructured computations whose data dependencies correspond to a large sparse and irregular graph. Even though the problem of computing high-quality partitionings of graphs arising in scientific computations is to a large extent well understood, this is far from being true for emerging HPC applications whose underlying computation involves graphs whose degree distribution follows a power-law curve. This paper presents new multilevel graph partitioning algorithms that are specifically designed for partitioning such graphs. It presents new clustering-based coarsening schemes that identify and collapse together groups of vertices that are highly connected. An experimental evaluation of these schemes on 10 different graphs show that the proposed algorithms consistently and significantly

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 18, 2005
Accession Number
ADA439402

Entities

People

  • Amine Abou-rjeili
  • George Karypis

Organizations

  • University of Minnesota

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Clustering
  • Collapse
  • Computations
  • Computer Science
  • Computers
  • Engineering
  • Environment
  • Information Operations
  • Mathematics
  • Military Research
  • Motivation
  • Parallel Computing
  • Parallel Processing

Fields of Study

  • Computer science

Readers

  • Computational Fluid Dynamics (CFD)
  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.