Back to papers
Hierarchical Core Maintenance on Large Dynamic Graphs
Summary: Hierarchical k-core maintenance for dynamic graphs; incrementally updates the k-core hierarchy by exploiting inter-core relations. Local update techniques target affected areas via structural properties, achieving up to 1,000× speedups on 10 real-world graphs.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 12593
- Venue
- VLDB
- Year
- 2021
- Pagerank
- 7.2170169e-05
- Overall Rank
- 3,323 | 76.91%
- DOI
-
10.14778/3446095.3446099
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 13 of 13 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 4,843 |
Butterfly-Core Community Search over Labeled Graphs |
2021 |
VLDB |
5.8767265e-05 |
| 6,185 |
Efficient Core Maintenance in Large Bipartite Graphs |
2023 |
SIGMOD |
5.1618114e-05 |
| 6,729 |
Maximal D-truss Search in Dynamic Directed Graphs |
2023 |
VLDB |
4.943658e-05 |
| 6,882 |
Theoretically and Practically Efficient Parallel Nucleus Decomposition |
2022 |
VLDB |
4.8923998e-05 |
| 7,430 |
DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs |
2022 |
VLDB |
4.7275494e-05 |
| 8,171 |
Efficient Triangle-Connected Truss Community Search In Dynamic Graphs |
2023 |
VLDB |
4.5655127e-05 |
| 9,484 |
MCR-Tree: An Efficient Index for Multi-dimensional Core Search |
2024 |
SIGMOD |
4.3300131e-05 |
| 9,950 |
Parallel Colorful h-star Core Maintenance in Dynamic Graphs |
2023 |
VLDB |
4.236537e-05 |
| 10,159 |
Efficient Influential Community Search over Dynamic Graphs |
2026 |
SIGMOD |
4.1905499e-05 |
| 10,246 |
Anchored Maximum Communities over Large Directed Graphs |
2026 |
VLDB |
4.1905499e-05 |
| 10,375 |
A Local Search Approach to Efficient (k, p)-Core Maintenance |
2025 |
SIGMOD |
4.1905499e-05 |
| 10,950 |
Parallel Algorithms for Hierarchical Nucleus Decomposition |
2024 |
SIGMOD |
4.1905499e-05 |
| 11,047 |
Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation |
2024 |
VLDB |
4.1905499e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 23 of 23 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 106 |
Truss Decomposition in Massive Networks |
2012 |
VLDB |
0.00048373761 |
| 284 |
Querying K-Truss Community in Large and Dynamic Graphs |
2014 |
SIGMOD |
0.00029014359 |
| 327 |
The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing |
2018 |
VLDB |
0.00027312381 |
| 682 |
Finding Maximal Cliques in Massive Networks by H*-graph |
2010 |
SIGMOD |
0.0001816451 |
| 734 |
Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis |
2013 |
VLDB |
0.00017419528 |
| 966 |
Streaming Algorithms for k-core Decomposition |
2013 |
VLDB |
0.00014947141 |
| 1,150 |
K-Core Decomposition of Large Networks on a Single PC |
2016 |
VLDB |
0.00013647447 |
| 1,256 |
Influential Community Search in Large Networks |
2015 |
VLDB |
0.00013009097 |
| 1,776 |
Reachability Queries on Large Dynamic Graphs: A Total Order Approach |
2014 |
SIGMOD |
0.0001058029 |
| 1,806 |
Incremental Graph Pattern Matching |
2011 |
SIGMOD |
0.00010478244 |
| 1,848 |
Effective Community Search over Large Spatial Graphs |
2017 |
VLDB |
0.00010331574 |
| 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 |
| 2,913 |
Efficient Algorithms for Densest Subgraph Discovery |
2019 |
VLDB |
7.9229304e-05 |
| 3,188 |
Scalable Big Graph Processing in MapReduce |
2014 |
SIGMOD |
7.4142307e-05 |
| 3,274 |
Global Reinforcement of Social Networks: The Anchored Coreness Problem |
2020 |
SIGMOD |
7.2886717e-05 |
| 3,608 |
Skyline Community Search in Multi-valued Networks |
2018 |
SIGMOD |
6.9241653e-05 |
| 4,391 |
When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks |
2017 |
VLDB |
6.2190075e-05 |
| 4,727 |
OLAK: An Efficient Algorithm to Prevent Unraveling in Social Networks |
2017 |
VLDB |
5.9628488e-05 |
| 4,927 |
Efficient Cohesive Subgraphs Detection in Parallel |
2014 |
SIGMOD |
5.8181623e-05 |
| 6,206 |
Efficiently Computing k-Edge Connected Components via Graph Decomposition |
2013 |
SIGMOD |
5.1522897e-05 |
| 6,588 |
Efficient Progressive Minimum k-Core Search |
2020 |
VLDB |
4.9972607e-05 |
| 7,343 |
I/O Efficient ECC Graph Decomposition via Graph Reduction |
2016 |
VLDB |
4.7511136e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,516 |
Fast Hierarchy Construction for Dense Subgraphs |
2017 |
VLDB |
8.6114467e-05 |
| 8,540 |
Fully Dynamic Betweenness Centrality Maintenance on Massive Networks |
2016 |
VLDB |
4.4893996e-05 |
| 10,189 |
Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs |
2026 |
SIGMOD |
4.1905499e-05 |
| 6,185 |
Efficient Core Maintenance in Large Bipartite Graphs |
2023 |
SIGMOD |
5.1618114e-05 |
| 10,375 |
A Local Search Approach to Efficient (k, p)-Core Maintenance |
2025 |
SIGMOD |
4.1905499e-05 |
| 9,146 |
Accelerating Core Decomposition in Billion-Scale Hypergraphs |
2025 |
SIGMOD |
4.380727e-05 |
| 966 |
Streaming Algorithms for k-core Decomposition |
2013 |
VLDB |
0.00014947141 |
| 10,134 |
A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs |
2026 |
SIGMOD |
4.1905499e-05 |
| 9,950 |
Parallel Colorful h-star Core Maintenance in Dynamic Graphs |
2023 |
VLDB |
4.236537e-05 |
| 6,145 |
Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs |
2021 |
VLDB |
5.1853422e-05 |