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

The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume

L. Lovasz and M. Simonovits · 1990

Earlier work this paper cites.

Random walks in a convex body and an improved volume algorithm

Lovasz and Simonovits · 1993

Earlier work this paper cites.

The pagerank citation ranking: Bringing order to the web

Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd · 1998

Earlier work this paper cites.

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

Tom Leighton and Satish Rao · 1999

Earlier work this paper cites.

Immersive and interactive exploration of billion-atom systems

Ashish Sharma, Xinlian Liu, Paul Miller, Aiichiro Nakano, Rajiv K. Kalia, Priya Vashishta, Wei Zhao, Timothy J. Campbell, and Andy Haas · 2002

Earlier work this paper cites.

Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

Daniel A. Spielman and Shang-Hua Teng · 2003

Earlier work this paper cites.

0(sqrt (log n)) approximation to Sparsest Cut in õ(n 2 ) time

Sanjeev Arora, Elad Hazan, and Satyen Kale · 2004

Earlier work this paper cites.

Expander flows, geometric embeddings and graph partitioning

Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2004

Earlier work this paper cites.

On clusterings: Good, bad and spectral

Ravi Kannan, Santosh Vempala, and Adrian Vetta · 2004

Cited alongside, same era.

Morre’s law

Intel Corporation · 2005

Cited alongside, same era.

The indexable web is more than 11.5 billion pages

A. Gulli and A. Signorini · 2005

Cited alongside, same era.

Local graph partitioning using pagerank vectors

Reid Andersen, Fan Chung, and Kevin Lang · 2006

Cited alongside, same era.

Graph partitioning using single commodity flows

Rohit Khandekar, Satish Rao, and Umesh Vazirani · 2006

Cited alongside, same era.

On the NP-completeness of some graph cluster measures

Jirí Síma and Satu Elisa Schaeffer · 2006

Cited alongside, same era.

Local computation of pagerank contributions

Local partitioning for directed graphs using pagerank

Reid Andersen, Fan R. K. Chung, and Kevin J. Lang · 2007

Later among the works it cites.

A combinatorial, primal-dual approach to semidefinite programs

Sanjeev Arora and Satyen Kale · 2007

Later among the works it cites.

A local algorithm for finding dense subgraphs

Reid Andersen · 2008

Closest in time.

Planetary-scale views on a large instant-messaging network

Jure Leskovec and Eric Horvitz · 2008

Closest in time.

On partitioning graphs via single commodity flows

Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, and Nisheeth K. Vishnoi · 2008

Closest in time.

Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems

Daniel A. Spielman and Shang-Hua Teng · 2008

Closest in time.