Parallel Colorful h-star Core Maintenance in Dynamic Graphs

Summary: Introduces a parallel local colorful h-star core algorithm using a novel n-order H-index, replacing sequential peeling. Bounds identify unaffected nodes, enabling dynamic maintenance with up to 10× faster convergence and 1,000× faster update handling on billion-edge graphs. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13288
Venue: VLDB
Year: 2023
Pagerank: 5.1488731e-05
Overall Rank: 10,100 | 30.71%
DOI: 10.14778/3603581.3603593

Incoming Non-self Citations Over Time

Authors

1. Sen Gao (National University of Singapore)
2. Hongchao Qin (Beijing Institute of Technology)
3. Rong-Hua Li (Beijing Institute of Technology)
4. Bingsheng He (National University of Singapore)

BibTeX Citation

@article{gao_vldb23,
        title = {{Parallel Colorful h-star Core Maintenance in Dynamic Graphs}},
        author = {Gao, Sen and Qin, Hongchao and Li, Rong-Hua and He, Bingsheng},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {10},
        pages = {2538--2550},
        doi = {10.14778/3603581.3603593},
        url = {https://doi.org/10.14778/3603581.3603593},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,504	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	5.4132367e-05
11,256	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.093636e-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
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
20	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056944564
189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026114928
487	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00017645653
793	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00013978774
937	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013091546
1,307	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB	0.00011232263
1,640	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010153865
2,024	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2907829e-05
2,083	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.1976617e-05
2,826	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	8.0865974e-05
3,855	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	7.0712144e-05
5,697	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	6.1174514e-05
5,797	Effective and Efficient Dynamic Graph Coloring	2018	VLDB	6.0859157e-05
6,066	GRAPE: Parallelizing Sequential Graph Computations	2017	VLDB	5.9890886e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	793	Streaming Algorithms for k-core Decomposition	2013	VLDB
2	10,772	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
3	1,416	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
4	10,423	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD
5	6,617	Efficient Parallel D-core Decomposition at Scale	2024	VLDB
6	3,855	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB
7	9,301	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD
8	1,640	Distance-generalized Core Decomposition	2019	SIGMOD
9	2,826	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB
10	5,697	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB