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: h5b6bb6550ed145b6
Venue: VLDB
Year: 2021
Pagerank: 7.9235321e-05
Overall Rank: 2,869 | 80.72%
DOI: 10.14778/3446095.3446099

Incoming Non-self Citations Over Time

Authors

1. Zhe Lin (East China Normal University)
2. Fan Zhang (Guangdong University of Technology)
3. Xuemin Lin (East China Normal University; University of New South Wales)
4. Wenjie Zhang (University of New South Wales)
5. Zhihong Tian (Guangdong University of Technology)

BibTeX Citation

@article{lin_vldb21,
        title = {{Hierarchical Core Maintenance on Large Dynamic Graphs}},
        author = {Lin, Zhe and Zhang, Fan and Lin, Xuemin and Zhang, Wenjie and Tian, Zhihong},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {5},
        pages = {757--770},
        doi = {10.14778/3446095.3446099},
        url = {https://doi.org/10.14778/3446095.3446099},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,081	Butterfly-Core Community Search over Labeled Graphs	2021	VLDB	6.8178774e-05
5,629	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD	6.0592611e-05
5,976	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	5.9300103e-05
6,061	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	5.8988316e-05
6,765	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	5.6872079e-05
7,547	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	5.4981692e-05
8,853	MCR-Tree: An Efficient Index for Multi-dimensional Core Search	2024	SIGMOD	5.2641151e-05
8,880	Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation	2024	VLDB	5.2567693e-05
9,871	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.1176637e-05
10,327	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	5.0333462e-05
10,636	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.9793485e-05
10,718	Anchored Maximum Communities over Large Directed Graphs	2026	VLDB	4.9793485e-05
11,099	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	4.9793485e-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
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
184	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026100147
239	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.000235107
589	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00015905948
645	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015213733
758	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014188163
834	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013583208
1,007	Influential Community Search in Large Networks	2015	VLDB	0.00012556573
1,317	Incremental Graph Pattern Matching	2011	SIGMOD	0.00011050011
1,414	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.0001073756
1,849	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.5068688e-05
2,042	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.1416822e-05
2,119	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.0102885e-05
2,146	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.9595369e-05
3,066	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.6877117e-05
3,318	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	7.4324312e-05
4,091	When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks	2017	VLDB	6.8124092e-05
4,422	Global Reinforcement of Social Networks: The Anchored Coreness Problem	2020	SIGMOD	6.6060521e-05
4,578	OLAK: An Efficient Algorithm to Prevent Unraveling in Social Networks	2017	VLDB	6.5226071e-05
4,755	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD	6.4323525e-05
5,662	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	6.0472942e-05
6,211	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	5.8487355e-05
6,466	Efficient Progressive Minimum k-Core Search	2020	VLDB	5.7751978e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,909	Fully Dynamic Betweenness Centrality Maintenance on Massive Networks	2016	VLDB
2	10,665	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD
3	5,629	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD
4	10,485	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD
5	11,099	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD
6	9,474	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD
7	758	Streaming Algorithms for k-core Decomposition	2013	VLDB
8	10,612	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD
9	10,327	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB
10	5,720	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB