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: 13100
Venue: VLDB
Year: 2023
Pagerank: 4.2405999e-05
Overall Rank: 9,951 | 30.78%
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,484	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3341665e-05
11,048	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1945683e-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.0019005923
37	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.0007522744
283	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029041257
574	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019883211
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014960672
1,171	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013511313
1,570	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB	0.00011322927
1,836	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010365753
2,512	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6196023e-05
2,909	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9305767e-05
3,321	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.223972e-05
5,298	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	5.5799987e-05
5,751	Effective and Efficient Dynamic Graph Coloring	2018	VLDB	5.3409543e-05
6,105	GRAPE: Parallelizing Sequential Graph Computations	2017	VLDB	5.2078702e-05
6,141	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1903263e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014960672
10,495	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	4.1945683e-05
2,039	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.7061003e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1945683e-05
6,513	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.0321577e-05
5,298	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	5.5799987e-05
9,146	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD	4.3849295e-05
1,836	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010365753
3,321	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.223972e-05
6,141	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1903263e-05