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
9351
Venue
VLDB
Year
2005
Pagerank
0.00065421423
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.00047955011
284 Querying K-Truss Community in Large and Dynamic Graphs 2014 SIGMOD 0.00029014359
370 Online Search of Overlapping Communities 2013 SIGMOD 0.00025391823
387 Graph Summarization with Bounded Error 2008 SIGMOD 0.00024682268
645 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018727714
773 Local Graph Sparsification for Scalable Clustering 2011 SIGMOD 0.00016788213
865 Finding the Maximum Clique in Massive Graphs 2017 VLDB 0.00015775653
942 Framework for Evaluating Clustering Algorithms in Duplicate Detection 2009 VLDB 0.00015143877
1,029 Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification 2012 VLDB 0.00014568714
1,837 Distance-generalized Core Decomposition 2019 SIGMOD 0.00010355705
2,043 Local Algorithms for Hierarchical Dense Subgraph Discovery 2019 VLDB 9.6970812e-05
2,054 Graph Cube: On Warehousing and OLAP Multidimensional Networks 2011 SIGMOD 9.682102e-05
2,055 Community Detection in Social Networks: An In-depth Benchmarking Study with a Procedure-Oriented Framework 2015 VLDB 9.680119e-05
2,516 Fast Hierarchy Construction for Dense Subgraphs 2017 VLDB 8.6114467e-05
2,930 Assessing and Ranking Structural Correlations in Graphs 2011 SIGMOD 7.8790753e-05
3,024 GConnect: A Connectivity Index for Massive Disk-Resident Graphs 2009 VLDB 7.691835e-05
4,092 On Dense Pattern Mining in Graph Streams [Extended Abstract] 2010 VLDB 6.4525563e-05
4,147 Scaling Up k-Clique Densest Subgraph Detection 2023 SIGMOD 6.4060893e-05
4,955 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 5.8057282e-05
5,230 Link Spam Detection Based on Mass Estimation 2006 VLDB 5.6133889e-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
5,483 Efficient Load-Balanced Butterfly Counting on GPU 2022 VLDB 5.4829054e-05
5,782 I/O-Efficient Butterfly Counting at Scale 2023 SIGMOD 5.3268721e-05
6,882 Theoretically and Practically Efficient Parallel Nucleus Decomposition 2022 VLDB 4.8923998e-05
7,615 Mining Attribute-structure Correlated Patterns in Large Attributed Graphs 2012 VLDB 4.6902598e-05
7,806 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 4.6421951e-05
8,425 Spade: A Real-Time Fraud Detection Framework on Evolving Graphs 2023 VLDB 4.5111051e-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,037 The Power of Core Clique Removal for Exact Clique Enumeration 2026 SIGMOD 4.1905499e-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,526 Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum 2025 SIGMOD 4.1905499e-05
10,689 Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory 2025 VLDB 4.1905499e-05
10,950 Parallel Algorithms for Hierarchical Nucleus Decomposition 2024 SIGMOD 4.1905499e-05
11,413 Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques 2022 VLDB 4.1905499e-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,671 Extracting large-scale knowledge bases from the web 1999 VLDB 6.0023843e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
9,652 Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery 2023 SIGMOD 4.3067693e-05
648 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018688754
5,230 Link Spam Detection Based on Mass Estimation 2006 VLDB 5.6133889e-05
10,544 In-depth Analysis of Densest Subgraph Discovery in a Unified Framework 2025 VLDB 4.1905499e-05
11,413 Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques 2022 VLDB 4.1905499e-05
10,500 Integral Densest Subgraph Search on Directed Graphs 2025 SIGMOD 4.1905499e-05
2,913 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 7.9229304e-05
4,092 On Dense Pattern Mining in Graph Streams [Extended Abstract] 2010 VLDB 6.4525563e-05
645 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018727714
4,341 Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs 2020 SIGMOD 6.268429e-05