Back to search

Clemson University

Multilevel Methods for Sparsification and Linear Arrangement Problems on Networks

Abstract

dc:description.abstract

The computation of network properties such as diameter, centrality indices, and paths on networks may become a major bottleneck in the analysis of network if the network is large. Scalable approximation algorithms, heuristics and structure preserving network sparsification methods play an important role in modern network analysis. In the first part of this thesis, we develop a robust network sparsification method that enables filtering of either, so called, long- and short-range edges or both. Edges are first ranked by their algebraic distances and then sampled. Furthermore, we also combine this method with a multilevel framework to provide a multilevel sparsification framework that can control the sparsification process at different coarse-grained resolutions. Experimental results demonstrate an effectiveness of the proposed methods without significant loss in a quality of computed network properties. In the second part of the thesis, we introduce asymmetric coarsening schemes for multilevel algorithms developed for linear arrangement problems. Effectiveness of the set of coarse variables, and the corresponding interpolation matrix is the central problem in any multigrid algorithm. We are pushing the boundaries of fast maximum weighted matching algorithms for coarsening schemes on graphs by introducing novel ideas for asymmetric coupling between coarse and fine variables of the problem.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • John, Emmanuel
Contributors dc:contributor
  • Dr. Ilya Safro, Committee Chair
  • Dr. Amy Apon
  • Dr. Brian Dean
  • Dr. Hongxin Hu

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/2398

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

John, Emmanuel. Multilevel Methods for Sparsification and Linear Arrangement Problems on Networks. Thesis thesis, https://open.clemson.edu/all_theses/2398