Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs

Summary: Shows a novel link between density decomposition and LDS and develops static algorithms using network-flow + divide-and-conquer reducing worst-case time from O(m^2) to O(m^{3/2} log p) (p small in practice). Presents three dynamic algorithms with O(m) time complexity and validates efficiency, scalability, and effectiveness on large real-world graphs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13513
Venue: VLDB
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 11,048 | 23.15%
DOI: 10.14778/3681954.3681974

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,490	Integral Densest Subgraph Search on Directed Graphs	2025	SIGMOD	4.1945683e-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
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
283	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029041257
738	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017435236
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014960672
1,530	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011495611
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,039	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.7061003e-05
2,512	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6196023e-05
3,575	Finding Locally Densest Subgraphs: A Convex Programming Approach	2022	VLDB	6.9528126e-05
4,145	Scaling Up k-Clique Densest Subgraph Detection	2023	SIGMOD	6.4122551e-05
4,394	When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks	2017	VLDB	6.224902e-05
5,022	Maximal Defective Clique Enumeration	2023	SIGMOD	5.7536318e-05
5,265	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	5.5972878e-05
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05
6,880	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	4.8970985e-05
8,630	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	4.480887e-05
9,651	Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery	2023	SIGMOD	4.3109001e-05
9,951	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	4.2405999e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
644	Densest Subgraph in Streaming and MapReduce	2012	VLDB	0.00018748988
2,512	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6196023e-05
9,557	An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery	2024	SIGMOD	4.3254416e-05
10,072	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD	4.1945683e-05
10,535	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	4.1945683e-05
2,909	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9305767e-05
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05
10,490	Integral Densest Subgraph Search on Directed Graphs	2025	SIGMOD	4.1945683e-05
10,373	Density Decomposition of Bipartite Graphs	2025	SIGMOD	4.1945683e-05
4,344	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	6.2744553e-05