We study the design of local algorithms for massive graphs. A local algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster-a subset of vertices whose internal connections are significantly richer than its external connectionsnear a given vertex. The running time of our algorithm, when it finds a non-empty local cluster, is nearly linear in the size of the cluster it outputs. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly-linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearlylinear time algorithm for solving linear systems in symmetric, diagonally-dominant matrices. The linear system solver also leads to a nearly linear-time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers. * This paper is the first in a sequence of three papers expanding on material that appeared first under the title "Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems" [ST03]. The second paper, "Spectral Sparsification of Graphs" [ST08b] contains further results on partitioning graphs, and applies them to producing spectral sparsifiers of graphs. The third paper, "Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems" [ST08a] contains the results on solving linear equations and approximating eigenvalues and eigenvectors.
Some graph partitioning algorithms REF partition the graph to minimize its conductance.
A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
ArXiv
ArXiv
Computer Science Mathematics