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

By Daniel A. Spielman, Shang-Hua Teng. SIAM journal on computing (Print), 2008

364 citations recorded by the source corpus.

We study the design of local algorithms for massive graphs. A local graph 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 nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. 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....

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/c996c17c72b8d526e3e0c9abb9f83c9acfc98a5d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Geometry and Topology

Citations in the corpus

Bootstrapped Graph Diffusions (2018, background): “Beyond their SSL application, spectral and social graph diffusions are the basis of graph mining tasks such as community detection and local clustering [37] and of popular definitions of centrality, influence, and similarity measures of a node or sets of nodes [4, 9, 12–14, 17, 19, 23, 30, 31].”
Handbook of Big Data (2016, background): “• The PageRank diffusion [16] • The Katz diffusion [42] • The heat kernel diffusion [29,43] • The truncated random walk diffusion [44]”
Random walks and diffusion on networks (2016, background): “covered set of nodes has a low conductance (see Eq. (47)) and is neither too small nor too large. Nibble can also be used as a building block for network-partitioning algorithms that run in O(M) time [365, 367]. (Recall that Mdenotes the number of edges (see Table 1).) In the \seed-set expansion pro”
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training (2020, methodology): “lassifier on a downstream task. More implementation details about fine-tuning are available in Section 4.2. GCC as a local algorithm. As a graph algorithm, GCC belongs to the local algorithm category [45, 49], in which the algorithms only involve local explorations of the input (large-scale) network”
Graph Learning From Data Under Laplacian and Structural Constraints (2016, methodology): “Furthermore, DDGLs are utilized in [27]–[29] to develop efficient algorithms for graph partitioning [27], graph sparsification [28] and solving linear systems [29].”
Handbook of Cluster Analysis (2015, background): “Spectral clustering has been extended to directed graphs [36, 2, 28] as well as finding the local cluster of a data point in a large graph [41]”
Learning with Partially Absorbing Random Walks (2012, methodology): “We remark that similar analyses have been conducted in [1, 2] on personalized PageRank, for the local clustering problem [15] whose goal is to ﬁnd a local cut of low conductance near a speciﬁed starting vertex.”
Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity (2017, background): “ese diusion models are the basis of centrality, inuence, and similarity measures of a node or sets of nodes in a network [3, 8, 11–13, 16, 18, 22, 29, 30] and also underline community detection and local clustering algorithms [36].”