{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,20]],"date-time":"2026-10-20T16:31:43Z","timestamp":1792513903714,"version":"4.5.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"8","license":[{"start":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T00:00:00Z","timestamp":1563840000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["#HR0011-13-2-0001"],"award-info":[{"award-number":["#HR0011-13-2-0001"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACI-1339745, OCI-0910735"],"award-info":[{"award-number":["ACI-1339745, OCI-0910735"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2018,7,23]]},"abstract":"<jats:p>Graphs that model social networks, numerical simulations, and the structure of the Internet are enormous and cannot be manually inspected. A popular metric used to analyze these networks is Betweenness Centrality (BC), which has applications in community detection, power grid contingency analysis, and the study of the human brain. However, these analyses come with a high computational cost that prevents the examination of large graphs of interest.<\/jats:p>\n                  <jats:p>Recently, the use of Graphics Processing Units (GPUs) has been promising for efficient processing of unstructured data sets. Prior GPU implementations of BC suffer from large local data structures and inefficient graph traversals that limit scalability and performance. Here we present a hybrid GPU implementation that provides good performance on graphs of arbitrary structure rather than just scale-free graphs as was done previously. Our methods achieve up to 13\u00d7 speedup on high-diameter graphs and an average of 2.71\u00d7 speedup overall compared to the best existing GPU algorithm. We also observe near linear speedup when running BC on 192 GPUs.<\/jats:p>","DOI":"10.1145\/3230485","type":"journal-article","created":{"date-parts":[[2018,7,24]],"date-time":"2018-07-24T11:50:24Z","timestamp":1532433024000},"page":"85-92","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Accelerating GPU betweenness centrality"],"prefix":"10.1145","volume":"61","author":[{"given":"Adam","family":"McLaughlin","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David A.","family":"Bader","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Bader D.A. Meyerhenke H. Sanders P. Wagner D. (eds) Graph Partitioning and Graph Clustering--10th DIMACS Implementation Challenge volume 588 of Contemporary Mathematics (2013).","DOI":"10.1090\/conm\/588"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2007.11.001"},{"key":"e_1_2_1_5_1","first-page":"3","article-title":"Complex brain networks: Graph theoretical analysis of structural and functional systems","volume":"10","author":"Bullmore E.","year":"2009","unstructured":"Bullmore, E., Sporns, O. Complex brain networks: Graph theoretical analysis of structural and functional systems. Nat. Rev. Neurosci. 10, 3 (2009), 186--198.","journal-title":"Nat. Rev. Neurosci."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.45"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_8_1","volume-title":"A set of measures of centrality based on betweenness. Sociometry","author":"Freeman L.C.","year":"1977","unstructured":"Freeman, L.C. A set of measures of centrality based on betweenness. Sociometry (1977), 35--41."},{"key":"e_1_2_1_9_1","volume-title":"N","author":"Hoberock J.","year":"2010","unstructured":"Hoberock, J., Bell, N. Thrust: A Parallel Template Library. Online at: http:\/\/thrust.googlecode.com, 42:43 (2010)."},{"key":"e_1_2_1_10_1","first-page":"15","article-title":"node parallelism for graph centrality metrics","volume":"2","author":"Jia Y.","year":"2011","unstructured":"Jia, Y., Lu, V., Hoberock, J., Garland, M., Hart, J.C. Edge v. node parallelism for graph centrality metrics. GPU Computing Gems 2 (2011), 15--30.","journal-title":"GPU Computing Gems"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470400"},{"key":"e_1_2_1_12_1","unstructured":"Leskovec J. Krevl A. SNAP datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/35082140"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161100"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2014.157"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.52"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145831"},{"key":"e_1_2_1_18_1","volume-title":"https:\/\/nvlabs.github.io\/cub\/ (accessed","author":"Merrill D. CUDA","year":"2014","unstructured":"Merrill, D. CUDA Unbound. 2013. https:\/\/nvlabs.github.io\/cub\/ (accessed April 11, 2014)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145832"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1068\/b34098"},{"key":"e_1_2_1_21_1","volume-title":"Parallel Distrib. Comput. (JPDC)","author":"Sariy\u00fcce A.E.","year":"2014","unstructured":"Sariy\u00fcce, A.E., Saule, E., Kaya, K., \u00e7ataly\u00fcrek, \u00dc. Regularizing graph centrality computations. J, Parallel Distrib. Comput. (JPDC) (2014)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-12-149"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.61"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2011.83"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230485","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3230485","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3230485","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:26:13Z","timestamp":1764782773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,23]]},"references-count":25,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,7,23]]}},"alternative-id":["10.1145\/3230485"],"URL":"https:\/\/doi.org\/10.1145\/3230485","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,23]]},"assertion":[{"value":"2018-07-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}