I/O Efficient ECC Graph Decomposition via Graph Reduction

Summary: I/O efficient ECC decomposition for all k values achieved via two graph-reduction operators that shrink the in-memory graph while preserving k-edge connectivity. Bottom-Up, Top-Down, and Hybrid algorithms explore k-values in different orders to minimize redundant work, with experiments on graphs up to 1.95B edges demonstrating scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11530
Venue: VLDB
Year: 2016
Pagerank: 5.8486743e-05
Overall Rank: 6,535 | 55.17%
DOI: 10.14778/2904483.2904484

Incoming Non-self Citations Over Time

Authors

1. Long Yuan (University of New South Wales)
2. Lu Qin (University of Technology Sydney)
3. Xuemin Lin (University of New South Wales)
4. Lijun Chang (University of New South Wales)
5. Wenjie Zhang (University of New South Wales)

BibTeX Citation

@article{yuan_vldb16,
        title = {{I/O Efficient ECC Graph Decomposition via Graph Reduction}},
        author = {Yuan, Long and Qin, Lu and Lin, Xuemin and Chang, Lijun and Zhang, Wenjie},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {7},
        doi = {10.14778/2904483.2904484},
        url = {https://doi.org/10.14778/2904483.2904484},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,097	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	9.1725037e-05
2,826	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	8.0865974e-05
4,579	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.6203846e-05
8,623	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	5.3984824e-05
9,540	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.2528121e-05
9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.2434488e-05
9,691	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB	5.2351259e-05
10,226	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD	5.093636e-05
10,807	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	5.093636e-05
10,930	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
590	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.0001605572
594	Massive Graph Triangulation	2013	SIGMOD	0.00015979077
674	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015081844
3,119	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.7370163e-05
3,261	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD	7.5853837e-05
5,540	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	6.1809407e-05
9,759	Divide & Conquer: I/O Efficient Depth-First Search	2015	SIGMOD	5.2247222e-05
12,239	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,301	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD
2	10,448	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD
3	3,261	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD
4	11,256	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB
5	9,759	Divide & Conquer: I/O Efficient Depth-First Search	2015	SIGMOD
6	4,672	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
7	793	Streaming Algorithms for k-core Decomposition	2013	VLDB
8	12,239	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD
9	8,623	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB
10	5,540	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD