Parallel Colorful h-star Core Maintenance in Dynamic Graphs

Summary: Introduces highly-parallel local algorithms for colorful h-star core decomposition using a novel colorful h-star n-order H-index to avoid sequential peeling. Adds three optimizations and dynamic maintenance with lower/upper bounds to skip unaffected nodes, yielding ~10× faster convergence and ~1000× speedups on large real-world graphs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13101
Venue: VLDB
Year: 2023
Pagerank: 4.236537e-05
Overall Rank: 9,950 | 30.85%
DOI: 10.14778/3603581.3603593

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,486	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3300131e-05
11,051	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 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
284	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029014359
570	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019895021
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014947141
1,170	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013526297
1,570	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB	0.00011311977
1,837	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010355705
2,516	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6114467e-05
2,913	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9229304e-05
3,323	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.2170169e-05
5,302	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	5.5746393e-05
5,764	Effective and Efficient Dynamic Graph Coloring	2018	VLDB	5.3358197e-05
6,097	GRAPE: Parallelizing Sequential Graph Computations	2017	VLDB	5.2078413e-05
6,145	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1853422e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014947141
10,505	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	4.1905499e-05
2,043	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.6970812e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1905499e-05
6,509	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.0273291e-05
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
1,837	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010355705
3,323	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.2170169e-05
6,145	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1853422e-05