{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T16:23:43Z","timestamp":1780590223004,"version":"3.54.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T00:00:00Z","timestamp":1489104000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"T\u00dcB\u0130TAK","award":["115C018"],"award-info":[{"award-number":["115C018"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>\n            The betweenness and closeness metrics are widely used metrics in many network analysis applications. Yet, they are expensive to compute. For that reason, making the betweenness and closeness centrality computations faster is an important and well-studied problem. In this work, we propose the framework\n            <jats:italic>BADIOS<\/jats:italic>\n            that manipulates the graph by compressing it and splitting into pieces so that the centrality computation can be handled independently for each piece. Experimental results show that the proposed techniques can be a great arsenal to reduce the centrality computation time for various types and sizes of networks. In particular, it reduces the betweenness centrality computation time of a 4.6 million edges graph from more than 5 days to less than 16 hours. For the same graph, the closeness computation time is decreased from more than 3 days to 6 hours (12.7x speedup).\n          <\/jats:p>","DOI":"10.1145\/3022668","type":"journal-article","created":{"date-parts":[[2017,3,13]],"date-time":"2017-03-13T12:25:15Z","timestamp":1489407915000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Graph Manipulations for Fast Centrality Computation"],"prefix":"10.1145","volume":"11","author":[{"given":"Ahmet Erdem","family":"Sariy\u00fcce","sequence":"first","affiliation":[{"name":"Sandia National Laboratories, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kamer","family":"Kaya","sequence":"additional","affiliation":[{"name":"Sabanc\u0131 University, Istanbul, Turkey"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erik","family":"Saule","sequence":"additional","affiliation":[{"name":"University of North Carolina at Charlotte, Charlotte, NC, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00dcmit V.","family":"\u00c7ataly\u00fcrek","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,3,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.79"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2007.11.001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127407018403"},{"key":"e_1_2_1_5_1","unstructured":"\u00d6. \u015eim\u015fek and A. G. Barto. 2008. Skill characterization based on betweenness. In Neural Information Processing Systems.  \u00d6. \u015eim\u015fek and A. G. Barto. 2008. Skill characterization based on betweenness. In Neural Information Processing Systems."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972887.9"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of GPU Computing Gems: Jade Edition.","author":"Jia Y."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470400"},{"key":"e_1_2_1_10_1","volume-title":"Betweenness Centrality: Algorithms and Lower Bounds. Arxiv preprint arXiv:0809.1906","author":"Kintali S.","year":"2008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4137\/GRSB.S702"},{"key":"e_1_2_1_12_1","first-page":"43","article-title":"Mapping networks of terrorist cells","volume":"24","author":"Krebs V.","year":"2002","journal-title":"Connections"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2011.55"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2010.46"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.80"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161100"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnu015"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom-PASSAT.2012.66"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939770"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2458523.2458531"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.76"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2014.156"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.07.006"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-12-149"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3022668","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3022668","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:39Z","timestamp":1750218639000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3022668"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,10]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3022668"],"URL":"https:\/\/doi.org\/10.1145\/3022668","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,10]]},"assertion":[{"value":"2015-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}