Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs
Summary: Introduces the [x, y]-core, a dense-subgraph primitive for directed graphs, enabling DDS discovery with guarantees. Exact and approximation DDS algorithms on the core yield up to six orders of magnitude speedups on real data, addressing scalability for fraud detection and community mining. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Chenhao Ma (University of Hong Kong)
- 2. Yixiang Fang (University of New South Wales)
- 3. Reynold Cheng (University of Hong Kong)
- 4. Laks V.S. Lakshmanan (University of British Columbia)
- 5. Wenjie Zhang (University of New South Wales)
- 6. Xuemin Lin (University of New South Wales)
BibTeX Citation
@inproceedings{ma_sigmod20,
title = {{Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs}},
author = {Ma, Chenhao and Fang, Yixiang and Cheng, Reynold and Lakshmanan, Laks V.S. and Zhang, Wenjie and Lin, Xuemin},
series = {{SIGMOD} '20},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3318464.3389697},
url = {https://dl.acm.org/doi/10.1145/3318464.3389697},
year = {2020}
}
Incoming Citations (Sorted by Pagerank)
Showing 25 of 25 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 564 | Densest Subgraph in Streaming and MapReduce | 2012 | VLDB | 0.00016485347 |
| 706 | Effective Community Search for Large Attributed Graphs | 2016 | VLDB | 0.00014789612 |
| 1,113 | Approximate Closest Community Search in Networks | 2016 | VLDB | 0.00012124571 |
| 1,328 | Truss-based Community Search over Large Directed Graphs | 2020 | SIGMOD | 0.00011140898 |
| 1,378 | Effective Community Search over Large Spatial Graphs | 2017 | VLDB | 0.00010971508 |
| 1,647 | Effective and Efficient Community Search over Large Heterogeneous Information Networks | 2020 | VLDB | 0.00010125633 |
| 2,024 | Efficient Algorithms for Densest Subgraph Discovery | 2019 | VLDB | 9.2907829e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,822 | Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery | 2023 | SIGMOD |
| 2 | 10,930 | Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory | 2025 | VLDB |
| 3 | 11,256 | Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs | 2024 | VLDB |
| 4 | 11,608 | Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques | 2022 | VLDB |
| 5 | 10,807 | In-depth Analysis of Densest Subgraph Discovery in a Unified Framework | 2025 | VLDB |
| 6 | 4,903 | A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery | 2022 | SIGMOD |
| 7 | 10,226 | Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance | 2026 | SIGMOD |
| 8 | 10,767 | Integral Densest Subgraph Search on Directed Graphs | 2025 | SIGMOD |
| 9 | 2,024 | Efficient Algorithms for Densest Subgraph Discovery | 2019 | VLDB |
| 10 | 10,363 | Efficient and Scalable Directed Densest Subgraph Discovery | 2026 | SIGMOD |