Date of Award


Document Type


Degree Name

Master of Science (MS)

Legacy Department

Computer Science

Committee Member

Dr. Ilya Safro, Committee Chair

Committee Member

Dr. Amy Apon

Committee Member

Dr. Brian Dean

Committee Member

Dr. Hongxin Hu


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.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.