An Efficient Algorithm for Distance-based Structural Graph Clustering

Summary: Proposes distance-based SCAN: similarity = ratio of neighbors within d; non-neighbors and edge weights influence clustering. Uses bottom-k sketches (ADS) for O(k) similarity estimates, with histogram pruning for scalable, approximate clustering. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6610
Venue: SIGMOD
Year: 2023
Pagerank: 5.2675506e-05
Overall Rank: 9,444 | 35.21%
DOI: 10.1145/3588725

Incoming Non-self Citations Over Time

Authors

1. Kaixin Liu (Tsinghua University)
2. Sibo Wang (Chinese University of Hong Kong)
3. Yong Zhang (Tsinghua University)
4. Chunxiao Xing (Tsinghua University)

BibTeX Citation

@inproceedings{liu_sigmod23,
        title = {{An Efficient Algorithm for Distance-based Structural Graph Clustering}},
        author = {Liu, Kaixin and Wang, Sibo and Zhang, Yong and Xing, Chunxiao},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588725},
        url = {https://dl.acm.org/doi/10.1145/3588725},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,448	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	5.093636e-05
10,528	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
291	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00022264197
2,482	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.5183361e-05
2,792	All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis	2014	PODS	8.1191853e-05
2,839	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB	8.066541e-05
4,358	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.7459836e-05
4,423	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.7107949e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,061	Efficient Top-K SimRank-based Similarity Join	2015	VLDB
2	3,522	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
3	4,216	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
4	1,365	Scalable Similarity Search for SimRank	2014	SIGMOD
5	4,423	Dynamic Structural Clustering on Graphs	2021	SIGMOD
6	4,358	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD
7	364	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB
8	2,839	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB
9	2,482	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB
10	7,141	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB