Scalable Discovery of Best Clusters on Large Graphs

Summary: Top Graph Clusters (TopGC) probabilistically searches large edge-weighted directed graphs for their best clusters in linear time. Parallelizable, supports variable-size overlapping clusters, with a tunable memory parameter; up to 70% speedups and better scores on real-world benchmarks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10308
Venue: VLDB
Year: 2010
Pagerank: 7.3556982e-05
Overall Rank: 3,511 | 75.92%
DOI: 10.14778/1920841.1920929

Incoming Non-self Citations Over Time

Authors

1. Kathy Macropol (University of California)
2. Ambuj Singh (University of California)

BibTeX Citation

@article{macropol_vldb10,
        title = {{Scalable Discovery of Best Clusters on Large Graphs}},
        author = {Macropol, Kathy and Singh, Ambuj},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {693--702},
        doi = {10.14778/1920841.1920929},
        url = {https://doi.org/10.14778/1920841.1920929},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
276	Local Search of Communities in Large Graphs	2014	SIGMOD	0.00022620623

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,737	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD
2	1,875	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB
3	5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
4	5,540	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
5	11,163	Efficient High-Quality Clustering for Large Bipartite Graphs	2024	SIGMOD
6	2,482	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB
7	5,149	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB
8	3,616	Parallel Local Graph Clustering	2016	VLDB
9	13,454	Scalable Community Detection via Parallel Correlation Clustering	2021	VLDB
10	1,163	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD