Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs

Summary: Links density decomposition to locally-densest-subgraph decomposition, enabling network-flow/divide-and-conquer algorithms. Reduces static complexity from O(m²) to O(m^(3/2) log p) and supports dynamic updates in O(m), yielding fewer, more meaningful dense layers. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hbf52f1e076cd6433
Venue: VLDB
Year: 2024
Pagerank: 5.1103839e-05
Overall Rank: 9,915 | 33.34%
DOI: 10.14778/3681954.3681974

Incoming Non-self Citations Over Time

Authors

1. Yalong Zhang (Beijing Institute of Technology)
2. Rong-Hua Li (Beijing Institute of Technology)
3. Qi Zhang (Beijing Institute of Technology)
4. Hongchao Qin (Beijing Institute of Technology)
5. Guoren Wang (Beijing Institute of Technology)

BibTeX Citation

@article{zhang_vldb24,
        title = {{Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs}},
        author = {Zhang, Yalong and Li, Rong-Hua and Zhang, Qi and Qin, Hongchao and Wang, Guoren},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {11},
        pages = {2933--2945},
        doi = {10.14778/3681954.3681974},
        url = {https://doi.org/10.14778/3681954.3681974},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,256	Integral Densest Subgraph Search on Directed Graphs	2025	SIGMOD	5.050482e-05
10,808	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 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
274	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022490994
589	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00015905948
758	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014188163
1,092	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012072382
1,209	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB	0.00011534572
1,443	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010635542
1,648	Distance-generalized Core Decomposition	2019	SIGMOD	9.9863775e-05
2,119	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.0102885e-05
3,064	Finding Locally Densest Subgraphs: A Convex Programming Approach	2022	VLDB	7.6898682e-05
3,412	Scaling Up k-Clique Densest Subgraph Detection	2023	SIGMOD	7.3251247e-05
4,091	When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks	2017	VLDB	6.8124092e-05
4,526	Maximal Defective Clique Enumeration	2023	SIGMOD	6.5606177e-05
4,923	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	6.3522796e-05
5,662	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	6.0472942e-05
5,976	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	5.9300103e-05
8,772	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	5.2806308e-05
8,974	Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery	2023	SIGMOD	5.2454233e-05
10,327	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	5.0333462e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,963	An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery	2024	SIGMOD
2	10,562	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD
3	10,442	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD
4	11,220	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB
5	2,042	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB
6	5,662	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
7	10,256	Integral Densest Subgraph Search on Directed Graphs	2025	SIGMOD
8	10,808	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB
9	9,865	Density Decomposition of Bipartite Graphs	2025	SIGMOD
10	3,789	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD