Parallel Local Graph Clustering

Summary: Parallelizes local graph clustering for shared-memory multicore systems, yielding work proportional to cluster size rather than the whole graph. Parallel complexity analysis and large-scale experiments show speedups, enabling local clustering for big graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11403
Venue: VLDB
Year: 2016
Pagerank: 7.2559471e-05
Overall Rank: 3,616 | 75.20%
DOI: 10.14778/2994509.2994522

Incoming Non-self Citations Over Time

Authors

1. Julian Shun (University of California Berkeley)
2. Farbod Roosta-Khorasani (International Computer Science Institute; University of California Berkeley)
3. Kimon Fountoulakis (International Computer Science Institute; University of California Berkeley)
4. Michael W. Mahoney (International Computer Science Institute; University of California Berkeley)

BibTeX Citation

@article{shun_vldb16,
        title = {{Parallel Local Graph Clustering}},
        author = {Shun, Julian and Roosta-Khorasani, Farbod and Fountoulakis, Kimon and Mahoney, Michael W.},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {12},
        pages = {1041--1052},
        doi = {10.14778/2994509.2994522},
        url = {https://doi.org/10.14778/2994509.2994522},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,778	Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs	2021	SIGMOD	7.1334329e-05
4,358	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.7459836e-05
5,250	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	6.2992176e-05
5,612	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	6.1501992e-05
5,913	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD	6.0439971e-05
6,284	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.927015e-05
6,368	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	5.8975125e-05
8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.4949527e-05
9,046	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	5.3251649e-05
10,011	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.1772034e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
804	Robust Local Community Detection: On Free Rider Effect and Its Elimination	2015	VLDB	0.0001389717

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,697	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB
2	4,365	Application Driven Graph Partitioning	2020	SIGMOD
3	1,036	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD
4	1,875	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB
5	4,358	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD
6	10,558	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB
7	13,454	Scalable Community Detection via Parallel Correlation Clustering	2021	VLDB
8	3,511	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB
9	10,772	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
10	1,163	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD