Dissertation/Thesis Abstract

Graph diffusions and matrix functions: Fast algorithms and localization results
by Kloster, Kyle, Ph.D., Purdue University, 2016, 114; 10149739
Abstract (Summary)

Network analysis provides tools for addressing fundamental applications in graphs such as webpage ranking, protein-function prediction, and product categorization and recommendation. As real-world networks grow to have millions of nodes and billions of edges, the scalability of network analysis algorithms becomes increasingly important. Whereas many standard graph algorithms rely on matrix-vector operations that require exploring the entire graph, this thesis is concerned with graph algorithms that are local (that explore only the graph region near the nodes of interest) as well as the localized behavior of global algorithms. We prove that two well-studied matrix functions for graph analysis, PageRank and the matrix exponential, stay localized on networks that have a skewed degree sequence related to the power-law degree distribution common to many real-world networks. Our results give the first theoretical explanation of a localization phenomenon that has long been observed in real-world networks. We prove our novel method for the matrix exponential converges in sublinear work on graphs with the specified degree sequence, and we adapt our method to produce the first deterministic algorithm for computing the related heat kernel diffusion in constant-time. Finally, we generalize this framework to compute any graph diffusion in constant time.

Indexing (document details)
Advisor: Gleich, David F.
Commitee: Buzzard, Greg, Shen, Jie, Xia, Jianlin
School: Purdue University
Department: Mathematics
School Location: United States -- Indiana
Source: DAI-B 77/12(E), Dissertation Abstracts International
Subjects: Applied Mathematics, Mathematics, Computer science
Keywords: Community detection, Graph diffusions, Knapsack problem, Localization, Matrix exponential, Pagerank
Publication Number: 10149739
ISBN: 9781369048353