Streaming Algorithms for k-core Decomposition

Summary: First incremental k-core decomposition for streaming graphs. Locates a small update-subgraph containing all affected vertices; shows up to 1e6x speedup over non-incremental on large real/synthetic networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10709
Venue: VLDB
Year: 2013
Pagerank: 0.00014947141
Overall Rank: 966 | 93.29%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
284	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029014359
1,256	Influential Community Search in Large Networks	2015	VLDB	0.00013009097
1,837	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010355705
2,516	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6114467e-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,727	OLAK: An Efficient Algorithm to Prevent Unraveling in Social Networks	2017	VLDB	5.9628488e-05
5,302	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	5.5746393e-05
5,599	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	5.4164926e-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,528	Fast Algorithms for Core Maximization on Large Graphs	2022	VLDB	5.0198578e-05
8,017	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	4.6014683e-05
9,146	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD	4.380727e-05
9,950	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	4.236537e-05
10,189	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.1905499e-05
10,323	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	4.1905499e-05
10,375	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	4.1905499e-05
10,505	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	4.1905499e-05
10,865	Finding Time-Proximity Communities in Temporal Heterogeneous Information Networks	2025	VLDB	4.1905499e-05
11,051	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1905499e-05
11,634	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
645	Densest Subgraph in Streaming and MapReduce	2012	VLDB	0.00018727714
1,837	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010355705
7,343	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	4.7511136e-05
6,206	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1522897e-05
10,505	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	4.1905499e-05
1,150	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013647447
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
9,146	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD	4.380727e-05
3,323	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.2170169e-05