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)
Incoming Non-self Citations Over Time
Authors
- 1. David Gibson (IBM)
- 2. Ravi Kumar (IBM)
- 3. Andrew Tomkins (IBM)
BibTeX Citation
@article{gibson_vldb05,
title = {{Discovering Large Dense Subgraphs in Massive Graphs}},
author = {Gibson, David and Kumar, Ravi and Tomkins, Andrew},
journal = {PVLDB},
series = {{VLDB} '05},
pages = {721--732},
year = {2005}
}Incoming Citations (Sorted by Pagerank)
Showing 41 of 41 citing papers.
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 |
|---|---|---|---|---|
| 6,103 | Extracting large-scale knowledge bases from the web | 1999 | VLDB | 5.8864128e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,974 | Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery | 2023 | SIGMOD |
| 2 | 443 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB |
| 3 | 5,123 | Link Spam Detection Based on Mass Estimation | 2006 | VLDB |
| 4 | 11,220 | In-depth Analysis of Densest Subgraph Discovery in a Unified Framework | 2025 | VLDB |
| 5 | 11,916 | Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques | 2022 | VLDB |
| 6 | 10,256 | Integral Densest Subgraph Search on Directed Graphs | 2025 | SIGMOD |
| 7 | 2,042 | Efficient Algorithms for Densest Subgraph Discovery | 2019 | VLDB |
| 8 | 4,320 | On Dense Pattern Mining in Graph Streams | 2010 | VLDB |
| 9 | 561 | Densest Subgraph in Streaming and MapReduce | 2012 | VLDB |
| 10 | 3,789 | Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs | 2020 | SIGMOD |