K-Core Decomposition of Large Networks on a Single PC

Summary: Demonstrates k-core decomposition on billions of edges on a consumer PC using vertex-centric GraphChi/Webgraph and exact Batagelj–Zaversnik. Also evaluates EMcore and shows practical performance and memory budgeting, with larger graphs than prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11240
Venue: VLDB
Year: 2016
Pagerank: 0.00013647447
Overall Rank: 1,150 | 92.01%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,484	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011705344
1,529	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011484853
1,837	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010355705
2,043	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.6970812e-05
2,516	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6114467e-05
2,608	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.4587487e-05
3,274	Global Reinforcement of Social Networks: The Anchored Coreness Problem	2020	SIGMOD	7.2886717e-05
3,323	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.2170169e-05
4,133	On Querying Historical K-Cores	2021	VLDB	6.4185206e-05
4,146	Accelerating Triangle Counting on GPU	2021	SIGMOD	6.4065776e-05
5,302	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	5.5746393e-05
5,483	Efficient Load-Balanced Butterfly Counting on GPU	2022	VLDB	5.4829054e-05
5,599	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	5.4164926e-05
6,005	GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra	2021	VLDB	5.2365238e-05
6,145	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1853422e-05
6,509	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.0273291e-05
6,882	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	4.8923998e-05
7,806	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	4.6421951e-05
8,171	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5655127e-05
8,920	Time-Topology Analysis	2021	VLDB	4.4229886e-05
9,146	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD	4.380727e-05
10,484	Community Detection in Heterogeneous Information Networks Without Materialization	2025	SIGMOD	4.1905499e-05
10,505	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	4.1905499e-05
10,539	Most Similar Biclique Search at Scale	2025	VLDB	4.1905499e-05
10,556	On More Efficiently and Versatilely Querying Historical k-Cores	2025	VLDB	4.1905499e-05
10,950	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019040811
39	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00075263552

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,323	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.2170169e-05
7,343	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	4.7511136e-05
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761
6,145	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1853422e-05
1,837	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010355705
5,302	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	5.5746393e-05
9,146	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD	4.380727e-05
6,509	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.0273291e-05
10,505	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	4.1905499e-05
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014947141