{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T08:44:27Z","timestamp":1766220267663,"version":"3.48.0"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,9,8]]},"DOI":"10.1145\/3754598.3754663","type":"proceedings-article","created":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T08:34:32Z","timestamp":1766219672000},"page":"309-319","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Parallel Algorithms for Dynamic Percolation Centrality"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-9679-9971","authenticated-orcid":false,"given":"Prajjwal","family":"Nijhara","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Jodhpur, Jodhpur, India"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-6739-0377","authenticated-orcid":false,"given":"Lokesh","family":"Venkatachalam","sequence":"additional","affiliation":[{"name":"International Institute of Information Technology (IIIT), Hyderabad, Hyderabad, India"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2403-8878","authenticated-orcid":false,"given":"Agam Harpreet","family":"Singh","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Jodhpur, Jodhpur, India"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2075-3704","authenticated-orcid":false,"given":"Athreya","family":"Chandramouli","sequence":"additional","affiliation":[{"name":"International Institute of Information Technology (IIIT), Hyderabad, Hyderabad, India"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-3692-8989","authenticated-orcid":false,"given":"Sayantan","family":"Jana","sequence":"additional","affiliation":[{"name":"International Institute of Information Technology (IIIT), Hyderabad, Hyderabad, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5523-4494","authenticated-orcid":false,"given":"Kishore","family":"Kothapalli","sequence":"additional","affiliation":[{"name":"International Institute of Information Technology (IIIT), Hyderabad, Hyderabad, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0476-1224","authenticated-orcid":false,"given":"Dip Sankar","family":"Banerjee","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Jodhpur, Jodhpur, India"}]}],"member":"320","published-online":{"date-parts":[[2025,12,20]]},"reference":[{"key":"e_1_3_3_2_2_2","doi-asserted-by":"crossref","unstructured":"Stephen\u00a0P Borgatti. 2005. Centrality and network flow. Social networks 27 1 (2005) 55\u201371.","DOI":"10.1016\/j.socnet.2004.11.008"},{"key":"e_1_3_3_2_3_2","doi-asserted-by":"crossref","unstructured":"U. Brandes. 2001. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25 2 (2001) 163\u2013177.","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_3_3_2_4_2","first-page":"111","volume-title":"Proc. IEEE HiPC","author":"Chandramouli A.","year":"2021","unstructured":"A. Chandramouli, S. Jana, and K. Kothapalli. 2021. Efficient Parallel Algorithms for Computing Percolation Centrality. In Proc. IEEE HiPC. IEEE, 111\u2013120."},{"key":"e_1_3_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Timothy\u00a0A. Davis and Yifan Hu. 2011. The university of Florida sparse matrix collection. Trans. Math. Softw. 38 1 Article 1 (Dec 2011) 25\u00a0pages.","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_3_2_6_2","first-page":"271","volume-title":"Proc. of ACM SPAA","author":"Dhulipala L.","year":"2020","unstructured":"L. Dhulipala, G.E. Blelloch, and J. Shun. 2020. A parallel batch-dynamic data structure for the closest pair problem. In Proc. of ACM SPAA. 271\u2013283."},{"key":"e_1_3_3_2_7_2","doi-asserted-by":"crossref","unstructured":"D. Eppstein Z. Galil G.\u00a0F. Italiano and A. Nissenzweig. 1997. Sparsification - A technique for speeding up dynamic graph algorithms. J. ACM 44 5 (1997) 669\u2013696.","DOI":"10.1145\/265910.265914"},{"key":"e_1_3_3_2_8_2","unstructured":"L\u00a0C Freeman et\u00a0al. 2002. Centrality in social networks: Conceptual clarification. Social network: critical concepts in sociology. Londres: Routledge 1 3 (2002) 238\u2013263."},{"key":"e_1_3_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Z. Galil and G.\u00a0F. Italiano. 1992. Fully Dynamic Algorithms for 2-Edge Connectivity. SIAM J. Comput. 21(6) (1992) 1047\u20131069.","DOI":"10.1137\/0221062"},{"key":"e_1_3_3_2_10_2","first-page":"11","volume-title":"IEEE SocialCom","author":"Green O.","year":"2012","unstructured":"O. Green, R. McColl, and D.\u00a0A. Bader. 2012. A Fast Algorithm for Streaming Betweenness Centrality. In IEEE SocialCom. 11\u201320."},{"key":"e_1_3_3_2_11_2","doi-asserted-by":"crossref","unstructured":"M.R. Henzinger and V. King. 1999. Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation. J. ACM 46 4 (1999) 502\u2013516.","DOI":"10.1145\/320211.320215"},{"key":"e_1_3_3_2_12_2","doi-asserted-by":"crossref","unstructured":"F.\u00a0T. Jamour S. Skiadopoulos and P. Kalnis. 2018. Parallel Algorithm for Incremental Betweenness Centrality on Large Graphs. IEEE TPDS 29 3 (2018) 659\u2013672.","DOI":"10.1109\/TPDS.2017.2763951"},{"key":"e_1_3_3_2_13_2","doi-asserted-by":"crossref","unstructured":"A. Khanda S. Srinivasan S. Bhowmick B. Norris and S.K. Das. 2022. A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks. IEEE TPDS 33 4 (2022) 929\u2013940.","DOI":"10.1109\/TPDS.2021.3084096"},{"key":"e_1_3_3_2_14_2","doi-asserted-by":"crossref","unstructured":"M.J Lee S. Choi and C.W. Chung. 2016. Efficient algorithms for updating betweenness centrality in fully dynamic graphs. Information Sciences 326 (2016) 278\u2013296.","DOI":"10.1016\/j.ins.2015.07.053"},{"key":"e_1_3_3_2_15_2","unstructured":"J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. (06 2014)."},{"key":"e_1_3_3_2_16_2","first-page":"135","volume-title":"In Proc 2010 ACM SIGMOD International Conference on Management of data","author":"Malewicz G.","year":"2010","unstructured":"G. Malewicz, H.M. Austern, Aart\u00a0JC Bik, J.C Dehnert, I. Horn, N. Leiser, and G. Czajkowski. 2010. Pregel: a system for large-scale graph processing. In In Proc 2010 ACM SIGMOD International Conference on Management of data. 135\u2013146."},{"key":"e_1_3_3_2_17_2","first-page":"246","volume-title":"Proc. HiPC 2013","author":"McColl R.","year":"2013","unstructured":"R. McColl, O. Green, and D.\u00a0A. Bader. 2013. A new parallel algorithm for connected components in dynamic graphs. In Proc. HiPC 2013. IEEE Computer Society, 246\u2013255."},{"key":"e_1_3_3_2_18_2","doi-asserted-by":"crossref","unstructured":"D. Merrill M. Garland and A. Grimshaw. 2012. Scalable GPU graph traversal. in Proc. ACM PPoPP (2012) 117\u2013128.","DOI":"10.1145\/2145816.2145832"},{"key":"e_1_3_3_2_19_2","doi-asserted-by":"crossref","unstructured":"S. Min V.\u00a0S. Mailthody Z. Qureshi J. Xiong E. Ebrahimi and W-M. Hwu. 2020. EMOGI: Efficient Memory-access for Out-of-memory Graph-traversal In GPUs. Proc. VLDB Endow. 14 2 (2020) 114\u2013127.","DOI":"10.14778\/3425879.3425883"},{"key":"e_1_3_3_2_20_2","volume-title":"The PageRank citation ranking: Bringing order to the web.","author":"Page L.","year":"1999","unstructured":"L. Page, S. Brin, R. Motwani, and T. Winograd. 1999. The PageRank citation ranking: Bringing order to the web.Technical Report. Stanford infolab."},{"key":"e_1_3_3_2_21_2","doi-asserted-by":"crossref","unstructured":"R. Panja and S.\u00a0S. Vadhiyar. 2019. HyPar: A divide-and-conquer model for hybrid CPU-GPU graph processing. JPDC. 132 (2019) 8\u201320.","DOI":"10.1016\/j.jpdc.2019.05.014"},{"key":"e_1_3_3_2_22_2","doi-asserted-by":"crossref","unstructured":"M. Piraveenan M. Prokopenko and L. Hossain. 2013. Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks. PLoS ONE 8 1 (2013).","DOI":"10.1371\/journal.pone.0053095"},{"key":"e_1_3_3_2_23_2","first-page":"1","volume-title":"EuroSys","author":"Sabet A.","year":"2020","unstructured":"A. Sabet, Z. Zhao, and R. Gupta. 2020. Subway: minimizing data transfer during out-of-GPU-memory graph processing. In EuroSys. 1\u201316."},{"key":"e_1_3_3_2_24_2","doi-asserted-by":"crossref","unstructured":"S. Sahu K. Kothapalli and D.S Banerjee. 2025. Parallel Multicore Algorithms for Community Detection in Dynamic Graphs. Int. J. Netw. Comput. 15 1 (2025) 2\u201331.","DOI":"10.15803\/ijnc.15.1_2"},{"key":"e_1_3_3_2_25_2","first-page":"239","volume-title":"Proc. HPDC","author":"Sallinen Scott","year":"2023","unstructured":"Scott Sallinen, Juntong Luo, and Matei Ripeanu. 2023. Real-Time PageRank on Dynamic Graphs. In Proc. HPDC. Association for Computing Machinery, 239\u2013251."},{"key":"e_1_3_3_2_26_2","doi-asserted-by":"crossref","unstructured":"A.\u00a0E. Sariy\u00fcce K. Kaya E. Saule and U.\u00a0V. Cataly\u00fcrek. 2017. Graph Manipulations for Fast Centrality Computation. ACM TKDD 11 3 (2017) 26:1\u201326:25.","DOI":"10.1145\/3022668"},{"key":"e_1_3_3_2_27_2","doi-asserted-by":"crossref","unstructured":"Mo Sha Yuchen Li Bingsheng He and Kian-Lee Tan. 2017. Accelerating dynamic graph analytics on GPUs. Proc. VLDB Endow. 11 1 (Sept. 2017) 107\u2013120.","DOI":"10.14778\/3151113.3151122"},{"key":"e_1_3_3_2_28_2","doi-asserted-by":"crossref","unstructured":"S.\u00a0M. Shovan Arindam Khanda and Sajal\u00a0K. Das. 2025. Parallel Multi Objective Shortest Path Update Algorithm in Large Dynamic Networks. IEEE TPDS 36 5 (2025) 932\u2013944.","DOI":"10.1109\/TPDS.2025.3536357"},{"key":"e_1_3_3_2_29_2","first-page":"10:1\u201310:12","volume-title":"Proc. ICS\u201920: 2020","author":"Shukla K.","year":"2020","unstructured":"K. Shukla, S.C. Regunta, S.H. Tondomker, and K. Kothapalli. 2020. Efficient parallel algorithms for betweenness- and closeness-centrality in dynamic graphs. In Proc. ICS\u201920: 2020. ACM, 10:1\u201310:12."},{"key":"e_1_3_3_2_30_2","first-page":"561","volume-title":"Proc. Euro-Par","author":"Simsiri N.","year":"2016","unstructured":"N. Simsiri, K. Tangwongsan, S. Tirthapura, and Kun-Lung Wu. 2016. Work-Efficient Parallel Union-Find with Applications to Incremental Graph Connectivity. In Proc. Euro-Par. 561\u2013573."},{"key":"e_1_3_3_2_31_2","first-page":"885","volume-title":"IPDPS Workshops","author":"Srinivasan S.","year":"2016","unstructured":"S. Srinivasan, S. Bhowmick, and S.\u00a0K. Das. 2016. Application of Graph Sparsification in Developing Parallel Algorithms for Updating Connected Components. In IPDPS Workshops. 885\u2013891."},{"key":"e_1_3_3_2_32_2","doi-asserted-by":"crossref","unstructured":"S. Srinivasan S. Pollard S. Das B. Norris and S. Bhowmick. 2018. A Shared-Memory Algorithm for Updating Tree-Based Properties of Large Dynamic Networks. IEEE T. Big Data (2018).","DOI":"10.1109\/HiPC.2018.00035"},{"key":"e_1_3_3_2_33_2","unstructured":"Y. Zhang Y. Liang J. Zhao Mao F L. Gu X. Liao H. Jin H. Liu S. Guo Y. Zeng et\u00a0al. 2022. EGraph: efficient concurrent GPU-based dynamic graph processing. IEEE TKDE 35 6 (2022) 5823\u20135836."}],"event":{"name":"ICPP '25: 54th International Conference on Parallel Processing","location":"San Diego CA USA","acronym":"ICPP '25"},"container-title":["Proceedings of the 54th International Conference on Parallel Processing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3754598.3754663","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T08:39:43Z","timestamp":1766219983000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3754598.3754663"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":32,"alternative-id":["10.1145\/3754598.3754663","10.1145\/3754598"],"URL":"https:\/\/doi.org\/10.1145\/3754598.3754663","relation":{},"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"2025-12-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}