Iterative Methods and Partitioning Techniques for Large Sparse Problems in Network Analysis Pubblico

Abstract

The analysis of networks is an important aspect in many fields. Here we consider three different topics: the numerical solution of Markov chains, ranking of genes, and parallel computations with large scale-free graphs.
First, additive Schwarz methods are a class of domain decomposition methods that are suitable for the solution of large linear systems in serial as well as in parallel mode. We adapt the Restricted Additive Schwarz (RAS) method to the computation of the stationary probability distribution vector of large, sparse, irreducible stochastic matrices. The convergence properties are analyzed and extensive numerical experiments aimed at assessing the effect of varying the number of subdomains and the choice of overlap are discussed.
Next, the ranking of genes plays an important role in the identification of key genes for a specific disease. A modification of the PageRank algorithm that is used to rank web pages is the GeneRank algorithm. We assessed the performance of additive Schwarz methods as well as that of Chebyshev iteration for the solution of the GeneRank problem.
Finally, many large networks are scale-free. That is, the degree distribution follows a power-law. Currently available graph partitioners are not efficient for such an irregular degree distribution. The lack of a good partitioning leads to excessive inter-processor communication requirements during each matrix-vector product on parallel distributed-memory computers. We present an approach to alleviate this problem based on embedding the original irregular graph into a more regular one by disaggregating (splitting up) vertices in the original graph. Even though the latter graph is larger, we are able to decrease the communication requirements considerably and improve the performance of the matrix-vector product.

Table of Contents

1. Introduction and preliminaries
2. Restricted Additive Schwarz Methods for Markov Chains
3. Iterative solvers for the GeneRank problem
4. Disaggregation techniques for large scale-free graphs
5. Conclusions and suggestions for future work

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Math and Computer Science
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Mathematics
Parola chiave	Numerical Solution of Markov Chains Scale-free Graphs Preconditioning Techniques Schwarz Methods
Committee Chair / Thesis Advisor	Benzi, Michele, Emory University
Committee Members	Veneziani, Alessandro, Emory University Szyld, Daniel, Temple University Nagy, James, Emory University

Ultima modifica

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Iterative Methods and Partitioning Techniques for Large Sparse Problems in Network Analysis ()	2018-08-28 13:55:29 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions