Graphs are a powerful and expressive means for storing and working with data. As the demand for fast data analysis increases, data is simultaneously becoming intractably large. To address these space constraints, there is a need for graph algorithms which do not require access to the full graph. We consider such algorithms a number of computational settings. The first is local computation which does not require the state of the full graph, but rather uses the output of small, local queries. We then extend methods in this setting to solve problems for distributed computation, where a graph is stored across processors that can communicate via communication links in a number of rounds, and a dynamic setting in which the graph is changing over time.

A key tool for computation in each of these settings is random walks. Random walks identify vertices which are central in the graph, a critical subroutine for ranking or clustering algorithms. Random walks on a graph are simple to simulate with prescribed transition probabilities using lightweight, local queries, and have the added benefit of being robust to noisy data.

In this dissertation, we give a quantitative analysis of random walks for local computations on a static, centralized graph and introduce a random walk simulation method for computing a vertex ranking known as the heat kernel pagerank of the graph. We then show how to adapt this method to both the distributed and dynamic setting. With an efficient algorithm for simulating random walks in each of these computational settings, we design fast graph algorithms for modern, flexible computational paradigms.

We apply spectral theory to study random processes involving directed graphs. In the first half of this thesis, we examine random walks on directed graphs, which is rooted in the study of non-reversible Markov chains. We prove bounds on key spectral invariants which play a role in bounding the rate of convergence of the walk and capture isoperimetric properties of the directed graph. We first focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. Improving upon previous bounds, we give a sharp upper bound for this ratio over all strongly connected graphs on $n$ vertices. We characterize all graphs achieving the upper bound and give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We then turn our attention to the first nontrivial Laplacian eigenvalue of a strongly connected directed graph. We give a lower bound for this eigenvalue, extending an analogous result for undirected graphs to the directed case. Our results on the principal ratio imply this lower bound can be factorially small in the number of vertices, and we give a construction having this eigenvalue factorially small.

In the second half, we apply spectral tools to study orientations of graphs. We focus on counting orientations yielding strongly connected directed graphs, called strong orientations. Namely, we show that under a mild spectral and minimum degree condition, a possibly irregular, sparse graph $G$ has ``many" strong orientations. More precisely, given a graph $G$ on $n$ vertices, orient each edge in either direction with probability $1/2$ independently. We show that if $G$ satisfies a minimum degree condition of $(1+c_1)\log_2{n}$ and has Cheeger constant at least $c_2\frac{\log_2\log_2{n}}{\log_2{n}}$, then the resulting randomly oriented directed graph is strongly connected with high probability. This Cheeger constant bound can be replaced by an analogous spectral condition via the Cheeger inequality. Additionally, we provide an explicit construction to show our minimum degree condition is tight while the Cheeger constant bound is tight up to a $\log_2\log_2{n}$ factor. We conclude by exploring related future work.

We address several problems in spectral graph theory, with a common theme of optimizing or computing a spectral graph invariant, such as the spectral radius or spectral gap, over some family of graphs. In particular, we study measures of graph irregularity, we bound the adjacency spectral radius over all outerplanar and planar graphs, and finally we determine the spectral gap of reversal graphs and a family of graphs that generalize the prefix reversal graph.

Firstly we study two measures of graph irregularity, the principal ratio and the difference between the spectral radius of the adjacency matrix and the average degree. For the principal ratio, we show that the graphs which maximize this statistic are the kite graphs, which are a clique with a pendant path, when the number of vertices is sufficiently large. This answers a conjecture of Cioabă and Gregory. For the second graph irregularity measure, we show that the connected graphs which maximize it are pineapple graphs, answering a conjecture of Aouchiche et al.

Secondly we investigate the maximum spectral radius of the adjacency matrix over all graphs on n vertices within certain well-known graph families. Our main result is showing that the planar graph on n vertices with maximal adjacency spectral radius is the join P 2 + P n−2 , when n is sufficiently large. This was conjectured by Boots and Royle. Additionally, we identify the outerplanar graph with maximal spectral radius, answering a conjecture of Cvetkovic̀ and Rowlinson.

Finally, we determine the spectral gap of various Cayley graphs of the symmetric group Sn , which arise in the context of substring reversals. This includes an elementary proof that the prefix reversal (or pancake flipping graph) has spectral gap one, originally

proved via representation theory by Cesi. We generalize this by showing that a large family of related graphs all have unit spectral gap.