A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning

Abstract

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 connections--near 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 nearly-linear 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.

References in corpus (1)

• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

Cited by in corpus (16)

• Divide and Conquer: Partitioning Online Social Networks
• Hitting and commute times in large graphs are often misleading
• Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving
• Spectral Sparsification of Graphs
• Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
• An Agent-Based Algorithm exploiting Multiple Local Dissimilarities for Clusters Mining and Knowledge Discovery
• Streaming Balanced Graph Partitioning for Random Graphs
• Finite Volume Spaces and Sparsification
• Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time
• Partitioning Graph Databases - A Quantitative Evaluation
• The Power of Local Information in Social Networks
• Finding Sparse Cuts Locally Using Evolving Sets
• Limited Random Walk Algorithm for Big Graph Data Clustering
• A linear k-fold Cheeger inequality
• Impact of Dynamic Interactions on Multi-Scale Analysis of Community Structure in Networks
• Testing Small Set Expansion in General Graphs