Efficient Structural Graph Clustering: An Index-Based Approach

Summary: Introduces an index-based SCAN algorithm supporting arbitrary ε and μ with output-sensitive clustering time, avoiding full-graph scans. Maintains the O(m)-space index under updates and substantially outperforms prior methods, including on billion-edge graphs. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11927
Venue: VLDB
Year: 2018
Pagerank: 8.5183361e-05
Overall Rank: 2,482 | 82.98%
DOI: 10.14778/3157794.3157795

Incoming Non-self Citations Over Time

Authors

1. Dong Wen (University of Technology Sydney)
2. Lu Qin (University of Technology Sydney)
3. Ying Zhang (University of Technology Sydney)
4. Lijun Chang (University of Sydney)
5. Xuemin Lin (University of New South Wales)

BibTeX Citation

@article{wen_vldb18,
        title = {{Efficient Structural Graph Clustering: An Index-Based Approach}},
        author = {Wen, Dong and Qin, Lu and Zhang, Ying and Chang, Lijun and Lin, Xuemin},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {3},
        pages = {243--255},
        doi = {10.14778/3157794.3157795},
        url = {https://doi.org/10.14778/3157794.3157795},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
6,342	Efficient Progressive Minimum k-Core Search	2020	VLDB	5.9068493e-05
6,937	Querying Structural Diversity in Streaming Graphs	2024	VLDB	5.7348103e-05
7,141	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB	5.6920203e-05
7,862	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	5.5302333e-05
9,387	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	5.2755515e-05
9,444	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD	5.2675506e-05
9,690	Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks	2025	VLDB	5.2351259e-05
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
10,567	FB*: A Compact Index for Efficient and Exact Density-based Clustering	2026	VLDB	5.093636e-05
11,102	The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering	2025	VLDB	5.093636e-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
102	Truss Decomposition in Massive Networks	2012	VLDB	0.00034255289
262	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00023084332
364	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00020054172
674	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015081844
2,839	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB	8.066541e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,540	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
2	8,477	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD
3	10,448	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD
4	3,511	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB
5	3,261	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD
6	2,839	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB
7	4,423	Dynamic Structural Clustering on Graphs	2021	SIGMOD
8	4,358	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD
9	9,444	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD
10	7,141	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB