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: h56ac4436780c4cd6
Venue: VLDB
Year: 2018
Pagerank: 8.3274854e-05
Overall Rank: 2,540 | 82.93%
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,451	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.5946218e-05
4,527	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.5602226e-05
6,466	Efficient Progressive Minimum k-Core Search	2020	VLDB	5.7751978e-05
7,076	Querying Structural Diversity in Streaming Graphs	2024	VLDB	5.6061365e-05
7,290	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB	5.5643066e-05
7,997	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	5.4105956e-05
9,571	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	5.1571823e-05
9,623	An Efficient Algorithm for Distance-based Structural Graph Clustering	2023	SIGMOD	5.1493609e-05
9,867	Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks	2025	VLDB	5.1176637e-05
10,636	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.9793485e-05
10,712	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.9793485e-05
10,749	FB*: A Compact Index for Efficient and Exact Density-based Clustering	2026	VLDB	4.9793485e-05
11,452	The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering	2025	VLDB	4.9793485e-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
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
265	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00022748633
375	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00019628745
645	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015213733
2,836	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB	7.9547269e-05

Semantically Similar Papers

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