{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:52:32Z","timestamp":1773481952343,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>\n            The arboricity\n            <jats:italic>a<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) of a graph\n            <jats:italic>G<\/jats:italic>\n            is defined as the minimum number of edge-disjoint forests that the edge set of\n            <jats:italic>G<\/jats:italic>\n            can be partitioned into. It is a fundamental metric and has been widely used in many graph analysis applications. However, computing\n            <jats:italic>a<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) is typically a challenging task. To address this, an easier-to-compute alternative called pseudoarboricity was proposed. Pseudoarboricity has been shown to be closely connected to many important measures in graphs, including the arboricity and the densest subgraph density\n            <jats:italic>\u03c1<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ). Computing the exact pseudoarboricity can be achieved by employing a parametric max-flow algorithm, but it becomes computationally expensive for large graphs. Existing 2-approximation algorithms, while more efficient, often lack satisfactory approximation accuracy. To overcome these limitations, we propose two new approximation algorithms with theoretical guarantees to approximate the pseudoarboricity. We show that our approximation algorithms can significantly reduce the number of times the max-flow algorithm is invoked, greatly improving its efficiency for exact pseudoarboricity computation. In addition, we also study the pseudoarboricity maintenance problem in dynamic graphs. We propose two novel and efficient algorithms for maintaining the pseudoarboricity when the graph is updated by edge insertions or deletions. Furthermore, we develop two incremental pseudoarboricity maintenance algorithms specifically designed for insertion-only scenarios. We conduct extensive experiments on 195 real-world graphs, and the results demonstrate the high efficiency and scalability of the proposed algorithms in computing pseudoarboricity for both static and dynamic graphs.\n          <\/jats:p>","DOI":"10.14778\/3681954.3681958","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"2722-2734","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Yalong","family":"Zhang","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongchao","family":"Qin","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Oswin Aichholzer Franz Aurenhammer and G\u00fcnter Rote. 1995. Optimal graph orientation with storage applications. Universit\u00e4t Graz\/Technische Universit\u00e4t Graz. SFB F003-Optimierung und Kontrolle."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1988852.1988854"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/945546.945549"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00007-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004644"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Aditya Auradkar Chavdar Botev Shirshanka Das Dave De Maagd Alex Feinberg Phanindra Ganti Lei Gao Bhaskar Ghosh Kishore Gopalakrishna Brendan Harris Joel Koshy Kevin Krawez Jay Kreps Shi Lu Sunil Nagaraj Neha Narkhede Sasha Pachev Igor Perisic Lin Qiao Tom Quiggle Jun Rao Bob Schulman Abraham Sebastian Oliver Seeliger Adam Silberstein Boris Shkolnik Chinmay Soman Roshan Sumbaly Kapil Surlaker Sajid Topiwala Cuong Tran Balaji Varadarajan Jemiah Westerman Zach White David Zhang and Jason Zhang. 2012. Data Infrastructure at LinkedIn. In ICDE. IEEE Computer Society 1370--1381.","DOI":"10.1109\/ICDE.2012.147"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.04.010"},{"key":"e_1_2_1_8_1","volume-title":"Compact representations of graphs and adjacency testing. Master's thesis","author":"Bez\u00e1kov\u00e1 Ivona","unstructured":"Ivona Bez\u00e1kov\u00e1. 2000. Compact representations of graphs and adjacency testing. Master's thesis. Comenius University."},{"key":"e_1_2_1_9_1","volume-title":"Fast Algorithms for Pseudoarboricity","author":"Blumenstock Markus","unstructured":"Markus Blumenstock. 2016. Fast Algorithms for Pseudoarboricity. In ALENEX. SIAM, 113--126."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00435"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2618795"},{"key":"e_1_2_1_12_1","volume-title":"Scalable Top-K Structural Diversity Search","author":"Chang Lijun","unstructured":"Lijun Chang, Chen Zhang, Xuemin Lin, and Lu Qin. 2017. Scalable Top-K Structural Diversity Search. In ICDE. IEEE Computer Society, 95--98."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90020-3"},{"key":"e_1_2_1_16_1","unstructured":"Qiangqiang Dai Rong-Hua Li Hongchao Qin Meihao Liao and Guoren Wang. 2022. Scaling Up Maximal k-plex Enumeration. In CIKM. 345--354."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Maximilien Danisch Oana Balalau and Mauro Sozio. 2018. Listing k-cliques in Sparse Real-World Graphs. In WWW. 589--598.","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_18_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. ACM 233--242.","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.004"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90121-X"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0904"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758774"},{"key":"e_1_2_1_25_1","volume-title":"Alex Beutel, Neil Shah, Kijung Shin, and Christos Faloutsos.","author":"Hooi Bryan","year":"2016","unstructured":"Bryan Hooi, Hyun Ah Song, Alex Beutel, Neil Shah, Kijung Shin, and Christos Faloutsos. 2016. FRAUDAR: Bounding Graph Fraud in the Face of Camouflage. In KDD. ACM, 895--904."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3027950"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536272"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0379-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11940128_56"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0467-4"},{"key":"e_1_2_1_35_1","first-page":"3335","article-title":"I\/O-Efficient Algorithms for Degeneracy Computation on Massive Networks","volume":"34","author":"Li Rong-Hua","year":"2022","unstructured":"Rong-Hua Li, Qiushuo Song, Xiaokui Xiao, Lu Qin, Guoren Wang, Jeffrey Xu Yu, and Rui Mao. 2022. I\/O-Efficient Algorithms for Degeneracy Computation on Massive Networks. IEEE Trans. Knowl. Data Eng. 34, 7 (2022), 3335--3348.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.006"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Mark Ortmann and Ulrik Brandes. 2014. Triangle Listing Algorithms: Back from the Diversion. In ALENEX. 1--8.","DOI":"10.1137\/1.9781611973198.1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120206"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465298"},{"key":"e_1_2_1_41_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. AAAI Press, 4292--4293."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.07.007"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157795"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00541-4"},{"key":"e_1_2_1_46_1","volume-title":"Efficient Top-k Ego-Betweenness Search","author":"Zhang Qi","unstructured":"Qi Zhang, Rong-Hua Li, Minjia Pan, Yongheng Dai, Guoren Wang, and Ye Yuan. 2022. Efficient Top-k Ego-Betweenness Search. In ICDE. IEEE, 380--392."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Qi Zhang Rong-Hua Li Qixuan Yang Guoren Wang and Lu Qin. 2020. Efficient Top-k Edge Structural Diversity Search. In ICDE. 205--216.","DOI":"10.1109\/ICDE48307.2020.00025"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3681958","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:33:49Z","timestamp":1725474829000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3681958"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":47,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3681958"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3681958","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}