Efficient Structural Graph Clustering: An Index-Based Approach

Summary: Index-based SCAN for structural graph clustering, delivering clusters, hubs, and outliers without full-graph scans. Time O(sum_C |E_C|) proportional to the result size, space O(m), supports dynamic updates, with strong gains on real networks up to >1B edges. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11739
Venue: VLDB
Year: 2018
Pagerank: 8.8252104e-05
Overall Rank: 2,436 | 83.06%
DOI: 10.14778/3157794.3157795

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,485	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.1458149e-05
4,657	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.0187213e-05
6,588	Efficient Progressive Minimum k-Core Search	2020	VLDB	5.0020648e-05
6,989	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB	4.8716197e-05
7,576	Querying Structural Diversity in Streaming Graphs	2024	VLDB	4.7064285e-05
7,871	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	4.6308128e-05
9,239	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	4.3690661e-05
9,368	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD	4.3481263e-05
10,159	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.1945683e-05
10,240	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.1945683e-05
10,553	Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks	2025	VLDB	4.1945683e-05
10,879	The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163
110	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00047892924
313	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00028097557
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029
2,898	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB	7.9445129e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05
9,552	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	4.3254416e-05
10,159	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.1945683e-05
2,542	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB	8.5794502e-05
3,854	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD	6.6988744e-05
2,898	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB	7.9445129e-05
4,657	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.0187213e-05
4,485	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.1458149e-05
9,368	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD	4.3481263e-05
6,989	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB	4.8716197e-05