{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:57:51Z","timestamp":1777615071779,"version":"3.51.4"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T00:00:00Z","timestamp":1687219200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"crossref","award":["FA8750-17-C-0086"],"award-info":[{"award-number":["FA8750-17-C-0086"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["CNS-2009057 and OAC-1911229"],"award-info":[{"award-number":["CNS-2009057 and OAC-1911229"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>\n            <jats:italic>Wing<\/jats:italic>\n            and\n            <jats:italic>Tip<\/jats:italic>\n            decomposition are motif-based analytics for bipartite graphs that construct a hierarchy of butterfly\u00a0(2,2-biclique) dense edge and vertex induced subgraphs, respectively. They have applications in several domains, including e-commerce, recommendation systems, document analysis, and others.\n          <\/jats:p>\n          <jats:p>\n            Existing decomposition algorithms use a bottom-up approach that constructs the hierarchy in an increasing order of the subgraph density. They iteratively select the edges or vertices with minimum butterfly count\n            <jats:italic>peel<\/jats:italic>\n            , i.e., remove them along with their butterflies. The amount of butterflies in real-world bipartite graphs makes bottom-up peeling computationally demanding. Furthermore, the strict order of peeling entities results in a large number of sequentially dependent iterations. Consequently, parallel algorithms based on bottom up peeling incur heavy synchronization and poor scalability.\n          <\/jats:p>\n          <jats:p>In this article, we propose a novel Parallel Bipartite Network peelinG (PBNG) framework that adopts a two-phased peeling approach to relax the order of peeling, and in turn, dramatically reduce synchronization. The first phase divides the decomposition hierarchy into few partitions and requires little synchronization. The second phase concurrently processes all partitions to generate individual levels of the hierarchy and requires no global synchronization. The two-phased peeling further enables batching optimizations that dramatically improve the computational efficiency of PBNG.<\/jats:p>\n          <jats:p>\n            We empirically evaluate PBNG using several real-world bipartite graphs and demonstrate radical improvements over the existing approaches. On a shared-memory 36 core server, PBNG achieves up to 19.7\u00d7 self-relative parallel speedup. Compared to the state-of-the-art parallel framework P\n            <jats:sc>ar<\/jats:sc>\n            B\n            <jats:sc>utterfly<\/jats:sc>\n            , PBNG reduces synchronization by up to 15,260\u00d7 and execution time by up to 295\u00d7. Furthermore, it achieves up to 38.5\u00d7 speedup over state-of-the-art algorithms specifically tuned for wing decomposition. Our source code is made available at\n            <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"url\" xlink:href=\"https:\/\/github.com\/kartiklakhotia\/RECEIPT\">https:\/\/github.com\/kartiklakhotia\/RECEIPT<\/jats:ext-link>\n            .\n          <\/jats:p>","DOI":"10.1145\/3583084","type":"journal-article","created":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T12:09:14Z","timestamp":1676030954000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Parallel Peeling of Bipartite Networks for Hierarchical Dense Subgraph Discovery"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9414-8481","authenticated-orcid":false,"given":"Kartik","family":"Lakhotia","sequence":"first","affiliation":[{"name":"University of Southern California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8736-3012","authenticated-orcid":false,"given":"Rajgopal","family":"Kannan","sequence":"additional","affiliation":[{"name":"U.S. Army Research Lab, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1609-8589","authenticated-orcid":false,"given":"Viktor","family":"Prasanna","sequence":"additional","affiliation":[{"name":"University of Southern California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0965-5"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnx001"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/892318"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0340-z"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"issue":"3","key":"e_1_3_2_10_2","article-title":"Trusses: Cohesive Subgraphs for Social Network Analysis","volume":"16","author":"Cohen Jonathan","year":"2008","unstructured":"Jonathan Cohen. 2008. Trusses: Cohesive Subgraphs for Social Network Analysis. National Security Agency Technical Report 16, 3.1.","journal-title":"National Security Agency Technical Report"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091042"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502550"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856327"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_3_2_17_2","volume-title":"Proceedings of the 7th International AAAI Conference on Weblogs and Social Media","author":"Fei Geli","year":"2013","unstructured":"Geli Fei, Arjun Mukherjee, Bing Liu, Meichun Hsu, Malu Castellanos, and Riddhiman Ghosh. 2013. Exploiting burstiness in reviews for review spammer detection. In Proceedings of the 7th International AAAI Conference on Weblogs and Social Media."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2018.8547759"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091038"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2018.8547581"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883037"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.04.027"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00017"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1060.0619"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3380942"},{"key":"e_1_3_2_31_2","article-title":"Parallel peeling of bipartite networks for hierarchical dense subgraph discovery","author":"Lakhotia Kartik","year":"2021","unstructured":"Kartik Lakhotia, Rajgopal Kannan, and Viktor Prasanna. 2021. Parallel peeling of bipartite networks for hierarchical dense subgraph discovery. arXiv:2110.12511. Retrieved from https:\/\/arxiv.org\/abs\/2110.12511.","journal-title":"arXiv:2110.12511"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430929"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.026120"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871557"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_3_2_38_2","first-page":"1","article-title":"The core decomposition of networks: Theory, algorithms and applications","author":"Malliaros Fragkiskos D.","year":"2019","unstructured":"Fragkiskos D. Malliaros, Christos Giatsidis, Apostolos N. Papadopoulos, and Michalis Vazirgiannis. 2019. The core decomposition of networks: Theory, algorithms and applications. VLDB J. (2019), 1\u201332.","journal-title":"VLDB J."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187863"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.3390\/a10030102"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.98.2.404"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939757"},{"key":"e_1_3_2_45_2","first-page":"286","volume-title":"International Conference on Parallel Processing and Applied Mathematics","author":"Riedy E. Jason","year":"2011","unstructured":"E. Jason Riedy, Henning Meyerhenke, David Ediger, and David A. Bader. 2011. Parallel community detection for massive graphs. In International Conference on Parallel Processing and Applied Mathematics. Springer, 286\u2013296."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623674"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091039"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091039"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357983"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021927"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159678"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275540"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_3_2_56_2","article-title":"Parallel algorithms for butterfly computations","author":"Shi Jessica","year":"2019","unstructured":"Jessica Shi and Julian Shun. 2019. Parallel algorithms for butterfly computations. arXiv:1907.08607. Retrieved from https:\/\/arxiv.org\/abs\/1907.08607.","journal-title":"arXiv:1907.08607"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113280"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091049"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2390633"},{"key":"e_1_3_2_61_2","first-page":"8\u2013pp","volume-title":"Proceedings of the 5th IEEE International Conference on Data Mining (ICDM\u201905)","author":"Sun Jimeng","year":"2005","unstructured":"Jimeng Sun, Huiming Qu, Deepayan Chakrabarti, and Christos Faloutsos. 2005. Neighborhood formation and anomaly detection in bipartite graphs. In Proceedings of the 5th IEEE International Conference on Data Mining (ICDM\u201905). IEEE, 8\u2013pp."},{"key":"e_1_3_2_62_2","article-title":"A novel approach to finding near-cliques: The triangle-densest subgraph problem","author":"Tsourakakis Charalampos E.","year":"2014","unstructured":"Charalampos E. Tsourakakis. 2014. A novel approach to finding near-cliques: The triangle-densest subgraph problem. arXiv:1405.1477. Retrieved from https:\/\/arxiv.org\/abs\/1405.1477.","journal-title":"arXiv:1405.1477"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052653"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091037"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2014.13"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00030"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00063"},{"key":"e_1_3_2_70_2","first-page":"1","article-title":"Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs","author":"Wang Kai","year":"2021","unstructured":"Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2021. Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. VLDB J. (2021), 1\u201324.","journal-title":"VLDB J."},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833070"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32049-6_14"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583084","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583084","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:48Z","timestamp":1750182528000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,20]]},"references-count":73,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3583084"],"URL":"https:\/\/doi.org\/10.1145\/3583084","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,20]]},"assertion":[{"value":"2021-07-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}