DBScholar

Back to papers

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)

Paper ID
hba84aaeebf8752f3
Venue
SIGMOD
Year
2020
Pagerank
7.0191274e-05
Overall Rank
3,789 | 74.53%
DOI
10.1145/3318464.3389697

Incoming Non-self Citations Over Time

Authors

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 26 of 26 citing papers.

Rank Citing Paper Year Venue Pagerank
1,663 Effective and Efficient Community Search over Large Heterogeneous Information Networks 2020 VLDB 9.9441685e-05
2,042 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 9.1416822e-05
3,064 Finding Locally Densest Subgraphs: A Convex Programming Approach 2022 VLDB 7.6898682e-05
3,412 Scaling Up k-Clique Densest Subgraph Detection 2023 SIGMOD 7.3251247e-05
3,875 Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions 2021 SIGMOD 6.9536357e-05
4,358 Anchored Densest Subgraph 2022 SIGMOD 6.6402693e-05
4,923 A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery 2022 SIGMOD 6.3522796e-05
4,954 Effective Community Search over Large Star-Schema Heterogeneous Information Networks 2022 VLDB 6.3411444e-05
5,174 Querying in the Age of Graph Databases and Knowledge Graphs 2021 SIGMOD 6.243251e-05
6,651 Efficient Parallel D-core Decomposition at Scale 2024 VLDB 5.7203229e-05
6,767 Scalable Time-Range k-Core Query on Temporal Graphs 2023 VLDB 5.6869663e-05
7,457 DeepTEA: Effective and Efficient Online Time-dependent Trajectory Outlier Detection 2022 VLDB 5.5223267e-05
7,807 A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery 2024 SIGMOD 5.4495451e-05
8,880 Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation 2024 VLDB 5.2567693e-05
8,974 Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery 2023 SIGMOD 5.2454233e-05
9,731 Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs 2025 VLDB 5.1349531e-05
10,256 Integral Densest Subgraph Search on Directed Graphs 2025 SIGMOD 5.050482e-05
10,442 Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance 2026 SIGMOD 4.9793485e-05
10,562 Efficient and Scalable Directed Densest Subgraph Discovery 2026 SIGMOD 4.9793485e-05
10,808 Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer 2026 VLDB 4.9793485e-05
11,180 Community Detection in Heterogeneous Information Networks Without Materialization 2025 SIGMOD 4.9793485e-05
11,206 Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum 2025 SIGMOD 4.9793485e-05
11,220 In-depth Analysis of Densest Subgraph Discovery in a Unified Framework 2025 VLDB 4.9793485e-05
11,321 Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory 2025 VLDB 4.9793485e-05
11,811 Density Personalized Group Query 2023 VLDB 4.9793485e-05
11,916 Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques 2022 VLDB 4.9793485e-05
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.

Previous Page 1 / 1 Next

Semantically Similar Papers