{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T13:53:32Z","timestamp":1770990812754,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T00:00:00Z","timestamp":1635811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Indian Institute of Technology Madras, India"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>\n            Betweenness centrality (BC) is a popular centrality measure, based on shortest paths, used to quantify the importance of vertices in networks. It is used in a wide array of applications including social network analysis, community detection, clustering, biological network analysis, and several others. The state-of-the-art Brandes\u2019 algorithm for computing BC has time complexities of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" content-type=\"gif\" xlink:href=\"3486613-inline1.gif\"\/>\n            <\/jats:inline-formula>\n            and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" content-type=\"gif\" xlink:href=\"3486613-inline2.gif\"\/>\n            <\/jats:inline-formula>\n            for unweighted and weighted graphs, respectively. Brandes\u2019 algorithm has been successfully parallelized on multicore and manycore platforms. However, the computation of vertex BC continues to be time-consuming for large real-world graphs. Often, in practical applications, it suffices to identify the most important vertices in a network; that is, those having the highest BC values. Such applications demand only the top vertices in the network as per their BC values but do not demand their actual BC values. In such scenarios, not only is computing the BC of\n            <jats:italic>all<\/jats:italic>\n            the vertices unnecessary but also\n            <jats:italic>exact<\/jats:italic>\n            BC values need not be computed. In this work, we attempt to marry controlled approximations with parallelization to\n            <jats:italic>estimate<\/jats:italic>\n            the\n            <jats:italic>k<\/jats:italic>\n            -highest BC vertices faster, without having to compute the exact BC scores of the vertices. We present a host of techniques to determine the top-\n            <jats:italic>k<\/jats:italic>\n            vertices\n            <jats:italic>faster<\/jats:italic>\n            , with a\n            <jats:italic>small<\/jats:italic>\n            inaccuracy, by computing\n            <jats:italic>approximate<\/jats:italic>\n            BC scores of the vertices. Aiding our techniques is a novel vertex-renumbering scheme to make the graph layout more\n            <jats:italic>structured<\/jats:italic>\n            , which results in faster execution of parallel Brandes\u2019 algorithm on GPU. Our experimental results, on a suite of real-world and synthetic graphs, show that our best performing technique computes the top-\n            <jats:italic>k<\/jats:italic>\n            vertices with an average speedup of 2.5\u00d7 compared to the exact parallel Brandes\u2019 algorithm on GPU, with an error of less than 6%. Our techniques also exhibit high precision and recall, both in excess of 94%.\n          <\/jats:p>","DOI":"10.1145\/3486613","type":"journal-article","created":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T20:19:32Z","timestamp":1635884372000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["ParTBC: Faster Estimation of Top-\n            <i>k<\/i>\n            Betweenness Centrality Vertices on GPU"],"prefix":"10.1145","volume":"27","author":[{"given":"Somesh","family":"Singh","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tejas","family":"Shah","sequence":"additional","affiliation":[{"name":"Microsoft, Bellandur, Bengaluru, Karnataka, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rupesh","family":"Nasre","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,11,2]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/1777879.1777889"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2006.57"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3307681.3326609"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/971617.971643"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/2791204.2791213"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2507826"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2628071.2628091"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295729"},{"key":"e_1_3_1_12_2","first-page":"1","volume-title":"Proceedings of the IEEE International Symposium on Parallel Distributed Processing (IPDPS\u201910)","author":"Jin S.","year":"2010","unstructured":"S. Jin, Z. Huang, Y. Chen, D. Chavarria-Miranda, J. Feo, and P. C. Wong. 2010. A novel application of parallel betweenness centrality to power grid contingency analysis. In Proceedings of the IEEE International Symposium on Parallel Distributed Processing (IPDPS\u201910). 1\u20137. https:\/\/doi.org\/10.1109\/IPDPS.2010.5470400"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2011.10.022"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2567948.2577358"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1038\/35082140"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/0713020"},{"key":"e_1_3_1_19_2","article-title":"GTgraph: A suite of synthetic random graph generators","author":"Madduri Kamesh","year":"2006","unstructured":"Kamesh Madduri and David A. Bader. 2006. GTgraph: A suite of synthetic random graph generators. Retrieved from http:\/\/www.cse.psu.edu\/ madduri\/software\/GTgraph\/.","journal-title":"http:\/\/www.cse.psu.edu\/ madduri\/software\/GTgraph\/"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161100"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.52"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2893356"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133126"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3296957.3173180"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993501"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442521"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3208351"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2458523.2458531"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TMSCS.2018.2795543"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295736"},{"key":"e_1_3_1_31_2","first-page":"11","volume-title":"Proceedings of the 49th International Conference on Parallel Processing (ICPP\u201920)","author":"Singh Somesh","year":"2020","unstructured":"Somesh Singh and Rupesh Nasre. 2020. Graffix: Efficient Graph processing with a tinge of GPU-specific approximations. In Proceedings of the 49th International Conference on Parallel Processing (ICPP\u201920). Association for Computing Machinery, New York, NY, Article 23, 11 pages. https:\/\/doi.org\/10.1145\/3404397.3404406"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126971"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3486613","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3486613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:06Z","timestamp":1750191126000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3486613"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,2]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3486613"],"URL":"https:\/\/doi.org\/10.1145\/3486613","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,2]]},"assertion":[{"value":"2021-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}