{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:48:55Z","timestamp":1774986535119,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    The densest subgraph (DS) search over a directed graph focuses on finding the subgraph with the highest density among all subgraphs. This problem has raised numerous applications, such as fraud detection and community detection. The state-of-the-art DS algorithms have prohibitively high costs or poor approximation ratios, making them unsuitable for practical applications. To address these dilemmas, in this paper, we propose a novel model called integral densest subgraph (IDS). We show that IDS can serve as a near-DS model that has a tight floor relationship with the density of the DS. To compute IDS, we first propose a novel flow network named (\u03b1,\u03b2)-dense network, based on which we design an exact network-flow algorithm GetIDS with O(p \u2022 log |V| \u2022 |E|\n                    <jats:sup>1.5<\/jats:sup>\n                    ) time complexity, where\n                    <jats:italic toggle=\"yes\">p<\/jats:italic>\n                    is typically a small constant in real-world graphs. Additionally, we propose several non-trivial pruning techniques to further improve the efficiency. Subsequently, we propose a novel (2 + \u03b5)-approximation algorithm MultiCore with near-linear time complexity, providing a good approximation guarantee with high efficiency. Finally, our extensive experiments on 10 real-world graphs demonstrate the effectiveness of the proposed IDS model, and the high efficiency and scalability of the proposed solutions.\n                  <\/jats:p>","DOI":"10.1145\/3725313","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["Integral Densest Subgraph Search on Directed Graphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-4339-4131","authenticated-orcid":false,"given":"Yalong","family":"Zhang","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4496-8518","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2194-8146","authenticated-orcid":false,"given":"Longlong","family":"Lin","sequence":"additional","affiliation":[{"name":"Southwest University, Chongqing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5533-3430","authenticated-orcid":false,"given":"Qi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6068-5062","authenticated-orcid":false,"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0181-8379","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Diameter of the world-wide web. nature","author":"Albert R\u00e9ka","year":"1999","unstructured":"R\u00e9ka Albert, Hawoong Jeong, and Albert-L\u00e1szl\u00f3 Barab\u00e1si. 1999. Diameter of the world-wide web. nature, Vol. 401, 6749 (1999), 130--131."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/JAGM.1999.1062"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Oana Denisa Balalau Francesco Bonchi T.-H. Hubert Chan Francesco Gullo and Mauro Sozio. 2015. Finding Subgraphs with Maximum Total Density and Limited Overlap. In WSDM. 379--388.","DOI":"10.1145\/2684822.2685298"},{"key":"e_1_2_1_5_1","volume-title":"Flowless: Extracting Densest Subgraphs Without Flow Computations. In WWW. 573--583.","author":"Boob Digvijay","year":"2020","unstructured":"Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos E. Tsourakakis, Di Wang, and Junxing Wang. 2020. Flowless: Extracting Densest Subgraphs Without Flow Computations. In WWW. 573--583."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36065-7_12"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036116"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Lijun Chang and Miao Qiao. 2020. Deconstruct Densest Subgraphs. In WWW. 2747--2753.","DOI":"10.1145\/3366423.3380033"},{"key":"e_1_2_1_9_1","volume-title":"Third International Workshop, APPROX 2000, Saarbr\u00fccken, Germany, September 5--8, 2000, Proceedings (Lecture Notes in Computer Science","volume":"95","author":"Charikar Moses","year":"2000","unstructured":"Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbr\u00fccken, Germany, September 5--8, 2000, Proceedings (Lecture Notes in Computer Science, Vol. 1913). Springer, 84--95."},{"key":"e_1_2_1_10_1","volume-title":"Torres","author":"Chekuri Chandra","year":"2022","unstructured":"Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. 2022. Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. In SODA. SIAM, 1531--1555."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.chb.2014.12.011"},{"key":"e_1_2_1_13_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press.","edition":"3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Maximilien Danisch T.-H. Hubert Chan and Mauro Sozio. 2017. Large Scale Density-friendly Graph Decomposition via Convex Programming. In WWW. 233--242.","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Eugene Fratkin Brian T. Naughton Douglas L. Brutlag and Serafim Batzoglou. 2006. MotifCut: regulatory motifs finding with maximum density subgraphs. In ISMB. 156--157.","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0464-z"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0539-0"},{"key":"e_1_2_1_19_1","unstructured":"Andrew V Goldberg. 1984. Finding a maximum density subgraph. Technical Report. University of California Berkeley Berkeley CA USA."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348556"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348556"},{"key":"e_1_2_1_23_1","volume-title":"36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5--12, 2009, Proceedings, Part I (Lecture Notes in Computer Science","volume":"608","author":"Khuller Samir","year":"2009","unstructured":"Samir Khuller and Barna Saha. 2009a. On Finding Dense Subgraphs. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5--12, 2009, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 5555). Springer, 597--608."},{"key":"e_1_2_1_24_1","volume-title":"36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5--12, 2009, Proceedings, Part I (Lecture Notes in Computer Science","volume":"608","author":"Khuller Samir","year":"2009","unstructured":"Samir Khuller and Barna Saha. 2009b. On Finding Dense Subgraphs. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5--12, 2009, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 5555). Springer, 597--608."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJAIP.2014.059585"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529340"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551826"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517837"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Lu Qin Rong-Hua Li Lijun Chang and Chengqi Zhang. 2015. Locally Densest Subgraph Discovery. In KDD. 965--974.","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25--30","author":"Ryan","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25--30, 2015, Austin, Texas, USA. AAAI Press, 4292--4293."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12683-3_30"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40991-2_3"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_39_1","volume-title":"Papadopoulos","author":"Valari Elena","year":"2012","unstructured":"Elena Valari, Maria Kontaki, and Apostolos N. Papadopoulos. 2012. Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections. In SSDBM (Lecture Notes in Computer Science, Vol. 7338). 213--230."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3314643"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3637528.3671727"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681958"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681974"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:54:07Z","timestamp":1774983247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725313"],"URL":"https:\/\/doi.org\/10.1145\/3725313","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}