UC San Diego

This thesis is concerned with a new type of approximation algorithm for the fundamental problems of partitioning a graph and identifying its dense subgraphs. We develop em local approximation algorithms for these two key problems, which search for a small set of vertices near a specified seed vertex, have a running time that is independent of the size of the graph, and for which we can prove a em local approximation guarantee. In the first part, we develop a local algorithm for graph partitioning that finds a cut with small conductance near a specified seed vertex, and has a running time that is nearly linear in the number of vertices in the small side of the cut. Within any cut S with conductance [Phi], we prove there are a significant number of starting vertices for which the algorithm produces a cut with conductance O(\ sqrt[Phi]log n)$. By combining many small cuts found by this algorithm we can find a balanced cut quickly, producing in time O(m \log³ m/[Phi] a cut with conductance O(\sqrt[Phi]log n)$ that is nearly as large as any cut with conductance [Phi], where m is the number of edges in the graph. The local algorithm finds its cut by computing a variation of PageRank with a specified starting vertex, and ordering the vertices of the graph according to that ranking. In the second part, we develop a local algorithm for finding dense subgraphs of bipartite graphs. This algorithm takes as input a bipartite graph with a specified seed vertex, and attempts to find a subgraph near the seed vertex that is dense according to the definition proposed by Kannan and Vinay. For any subgraph S with k vertices and density $\theta$, there are a significant number of starting vertices within $S$ for which the algorithm produces a subgraph with density $[Omega]([theta] / \log [Delta]), where [Delta] is the maximum degree in the graph. This local algorithm finds a dense subgraph by computing a sequence of vectors, which are similar to the vectors produced by the power method for computing the largest eigenvector of A, but which are pruned at each step to keep their support small