Database Paper Browser

Back to papers

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
10492
Venue
VLDB
Year
2012
Pagerank
0.00018748988
Overall Rank
644 | 95.53%
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.00025415479
1,013 Robust Local Community Detection: On Free Rider Effect and Its Elimination 2015 VLDB 0.00014645542
1,570 KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs 2020 VLDB 0.00011322927
1,645 Attribute-Driven Community Search 2017 VLDB 0.00011037459
2,093 Scalable K-Means++ 2012 VLDB 9.5588104e-05
2,674 Minimal MapReduce Algorithms 2013 SIGMOD 8.3328645e-05
2,909 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 7.9305767e-05
3,129 Scalable Big Graph Processing in MapReduce 2014 SIGMOD 7.5008242e-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,344 Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs 2020 SIGMOD 6.2744553e-05
5,265 A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery 2022 SIGMOD 5.5972878e-05
5,355 Anchored Densest Subgraph 2022 SIGMOD 5.5517073e-05
8,431 Spade: A Real-Time Fraud Detection Framework on Evolving Graphs 2023 VLDB 4.5154339e-05
9,039 RUSH: Real-time Burst Subgraph Detection in Dynamic Graphs 2024 VLDB 4.4039656e-05
9,403 A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3441378e-05
9,557 An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3254416e-05
9,651 Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery 2023 SIGMOD 4.3109001e-05
10,072 Efficient and Scalable Directed Densest Subgraph Discovery 2026 SIGMOD 4.1945683e-05
10,479 Dupin: A Parallel Framework for Densest Subgraph Discovery in Fraud Detection on Massive Graphs 2025 SIGMOD 4.1945683e-05
10,490 Integral Densest Subgraph Search on Directed Graphs 2025 SIGMOD 4.1945683e-05
10,535 In-depth Analysis of Densest Subgraph Discovery in a Unified Framework 2025 VLDB 4.1945683e-05
10,681 Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory 2025 VLDB 4.1945683e-05
10,865 Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs 2025 VLDB 4.1945683e-05
11,410 Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques 2022 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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.00065491112
279 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029113513
1,886 Social Content Matching in MapReduce 2011 VLDB 0.00010208945
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,472 Space Efficient Mining of Multigraph Streams 2005 PODS 0.00011828662
966 Streaming Algorithms for k-core Decomposition 2013 VLDB 0.00014960672
10,072 Efficient and Scalable Directed Densest Subgraph Discovery 2026 SIGMOD 4.1945683e-05
10,490 Integral Densest Subgraph Search on Directed Graphs 2025 SIGMOD 4.1945683e-05
5,355 Anchored Densest Subgraph 2022 SIGMOD 5.5517073e-05
4,089 On Dense Pattern Mining in Graph Streams [Extended Abstract] 2010 VLDB 6.4587806e-05
3,575 Finding Locally Densest Subgraphs: A Convex Programming Approach 2022 VLDB 6.9528126e-05
11,048 Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs 2024 VLDB 4.1945683e-05
4,344 Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs 2020 SIGMOD 6.2744553e-05
2,909 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 7.9305767e-05