Database Paper Browser

Back to papers

Discovering Large Dense Subgraphs in Massive Graphs

Summary: Shingles-based recursive fingerprinting for large dense subgraphs in massive graphs; scalable on a single machine to tens of billions of edges. On a 50M-host, 11B-edge Web graph, it finds hundreds of giant dense subgraphs and proposes dense-subgraph extraction for spam detection in search engines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9350
Venue
VLDB
Year
2005
Pagerank
0.00065491112
Overall Rank
57 | 99.61%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 38 of 38 citing papers.

Rank Citing Paper Year Venue Pagerank
110 On Triangulation-based Dense Neighborhood Graph Discovery 2011 VLDB 0.00047892924
283 Querying K-Truss Community in Large and Dynamic Graphs 2014 SIGMOD 0.00029041257
370 Online Search of Overlapping Communities 2013 SIGMOD 0.00025415479
388 Graph Summarization with Bounded Error 2008 SIGMOD 0.00024662272
644 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018748988
777 Local Graph Sparsification for Scalable Clustering 2011 SIGMOD 0.0001679862
847 Finding the Maximum Clique in Massive Graphs 2017 VLDB 0.00015993322
936 Framework for Evaluating Clustering Algorithms in Duplicate Detection 2009 VLDB 0.0001521549
1,029 Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification 2012 VLDB 0.00014582849
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,048 Graph Cube: On Warehousing and OLAP Multidimensional Networks 2011 SIGMOD 9.6914395e-05
2,049 Community Detection in Social Networks: An In-depth Benchmarking Study with a Procedure-Oriented Framework 2015 VLDB 9.6894639e-05
2,512 Fast Hierarchy Construction for Dense Subgraphs 2017 VLDB 8.6196023e-05
2,930 Assessing and Ranking Structural Correlations in Graphs 2011 SIGMOD 7.8723983e-05
3,020 GConnect: A Connectivity Index for Massive Disk-Resident Graphs 2009 VLDB 7.6992238e-05
4,089 On Dense Pattern Mining in Graph Streams [Extended Abstract] 2010 VLDB 6.4587806e-05
4,145 Scaling Up k-Clique Densest Subgraph Detection 2023 SIGMOD 6.4122551e-05
4,949 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 5.8113132e-05
5,226 Link Spam Detection Based on Mass Estimation 2006 VLDB 5.6187905e-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
5,474 Efficient Load-Balanced Butterfly Counting on GPU 2022 VLDB 5.4881807e-05
5,773 I/O-Efficient Butterfly Counting at Scale 2023 SIGMOD 5.3319911e-05
6,880 Theoretically and Practically Efficient Parallel Nucleus Decomposition 2022 VLDB 4.8970985e-05
7,614 Mining Attribute-structure Correlated Patterns in Large Attributed Graphs 2012 VLDB 4.6947636e-05
7,804 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 4.6466513e-05
8,431 Spade: A Real-Time Fraud Detection Framework on Evolving Graphs 2023 VLDB 4.5154339e-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,037 The Power of Core Clique Removal for Exact Clique Enumeration 2026 SIGMOD 4.1945683e-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,517 Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum 2025 SIGMOD 4.1945683e-05
10,681 Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory 2025 VLDB 4.1945683e-05
10,947 Parallel Algorithms for Hierarchical Nucleus Decomposition 2024 SIGMOD 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 1 of 1 cited papers.

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

Rank Cited Paper Year Venue Pagerank
4,676 Extracting large-scale knowledge bases from the web 1999 VLDB 6.0052781e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
9,651 Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery 2023 SIGMOD 4.3109001e-05
651 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018648572
5,226 Link Spam Detection Based on Mass Estimation 2006 VLDB 5.6187905e-05
10,535 In-depth Analysis of Densest Subgraph Discovery in a Unified Framework 2025 VLDB 4.1945683e-05
11,410 Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques 2022 VLDB 4.1945683e-05
10,490 Integral Densest Subgraph Search on Directed Graphs 2025 SIGMOD 4.1945683e-05
2,909 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 7.9305767e-05
4,089 On Dense Pattern Mining in Graph Streams [Extended Abstract] 2010 VLDB 6.4587806e-05
644 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018748988
4,344 Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs 2020 SIGMOD 6.2744553e-05