Date of Award

Spring 1-1-2015

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Applied Mathematics

First Advisor

Francois G. Meyer

Second Advisor

Bengt Fornberg

Third Advisor

Jem N. Corcoran

Fourth Advisor

Thomas Manteuffel

Fifth Advisor

Juan Restrepo

Abstract

In this thesis, we explore applications of spectral graph theory to the analysis of complex datasets and networks. We consider spectral embeddings of general graphs, as well as data sampled from smooth manifolds in high dimension. We specifically focus on the development of algorithms that require minimal user input. Given the inherent difficulty in parameterizing these types of complex datasets, an ideal algorithm should avoid poorly-defined user-selected parameters.

A significant limitation of nonlinear dimensionality reduction embeddings computed from datasets is the absence of a mechanism to compute the inverse map. We address the problem of computing a stable inverse using radial basis functions (RBFs) to interpolate the inverse map everywhere on the low-dimensional image of the forward map. We demonstrate that the scale-free cubic RBF kernel performs better than the Gaussian kernel: it does not suffer from ill-conditioning, and does not require the choice of a scale.

The definition of metrics to compare networks is an open research area. In this thesis, we define the resistance perturbation distance on the space of weighted connected undirected graphs with the same vertex set. This novel distance quantifies changes in the network connectivity, as measured by the respective effective resistance matrices in each graph. We introduce a fast algorithm to approximate this novel distance in linear time. We demonstrate on simple graph models and real networks that the resistance perturbation distance is able to ignore random fluctuation of edges that are irrelevant to the network connectivity, while remaining sensitive to changes triggered by edges that play a fundamental role in the graph connectivity.

Share

COinS