Densest Subgraph in Streaming and MapReduce

Summary: Introduces streaming and MapReduce algorithms for finding the densest subgraph, with O(log_{1+epsilon} n) streaming passes and a 2(1+epsilon)-approximation to the optimum. Demonstrates easy parallelization in MapReduce and validates performance and scalability via extensive experiments on massive real-world graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10493
Venue: VLDB
Year: 2012
Pagerank: 0.00018727714
Overall Rank: 645 | 95.52%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
370	Online Search of Overlapping Communities	2013	SIGMOD	0.00025391823
1,014	Robust Local Community Detection: On Free Rider Effect and Its Elimination	2015	VLDB	0.00014631717
1,570	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB	0.00011311977
1,645	Attribute-Driven Community Search	2017	VLDB	0.00011027616
2,146	Scalable K-Means++	2012	VLDB	9.4341455e-05
2,714	Minimal MapReduce Algorithms	2013	SIGMOD	8.2426646e-05
2,913	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9229304e-05
3,188	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.4142307e-05
3,579	Finding Locally Densest Subgraphs: A Convex Programming Approach	2022	VLDB	6.9461197e-05
4,147	Scaling Up k-Clique Densest Subgraph Detection	2023	SIGMOD	6.4060893e-05
4,341	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	6.268429e-05
5,274	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	5.5919087e-05
5,365	Anchored Densest Subgraph	2022	SIGMOD	5.5463723e-05
8,425	Spade: A Real-Time Fraud Detection Framework on Evolving Graphs	2023	VLDB	4.5111051e-05
9,040	RUSH: Real-time Burst Subgraph Detection in Dynamic Graphs	2024	VLDB	4.3997447e-05
9,409	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD	4.3399748e-05
9,557	An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery	2024	SIGMOD	4.3212967e-05
9,652	Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery	2023	SIGMOD	4.3067693e-05
10,072	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD	4.1905499e-05
10,489	Dupin: A Parallel Framework for Densest Subgraph Discovery in Fraud Detection on Massive Graphs	2025	SIGMOD	4.1905499e-05
10,500	Integral Densest Subgraph Search on Directed Graphs	2025	SIGMOD	4.1905499e-05
10,544	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	4.1905499e-05
10,689	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.1905499e-05
10,869	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	4.1905499e-05
11,413	Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques	2022	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
57	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00065421423
280	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029092277
1,888	Social Content Matching in MapReduce	2011	VLDB	0.00010196528

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,466	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011838607
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014947141
10,072	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD	4.1905499e-05
10,500	Integral Densest Subgraph Search on Directed Graphs	2025	SIGMOD	4.1905499e-05
5,365	Anchored Densest Subgraph	2022	SIGMOD	5.5463723e-05
4,092	On Dense Pattern Mining in Graph Streams [Extended Abstract]	2010	VLDB	6.4525563e-05
3,579	Finding Locally Densest Subgraphs: A Convex Programming Approach	2022	VLDB	6.9461197e-05
11,051	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1905499e-05
4,341	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	6.268429e-05
2,913	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9229304e-05