{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:56:19Z","timestamp":1772121379790,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T00:00:00Z","timestamp":1534896000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"<jats:p>\n            Betweenness is a well-known centrality measure that ranks the nodes according to their participation in the shortest paths of a network. In several scenarios, having a high betweenness can have a positive impact on the node itself. Hence, in this article, we consider the problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. In particular, we study the problem of maximizing the betweenness score of a given node\u2014Maximum Betweenness Improvement (MBI)\u2014and that of maximizing the ranking of a given node\u2014Maximum Ranking Improvement (MRI). We show that MBI cannot be approximated in polynomial-time within a factor (1\u22121\/2e) and that MRI does not admit any polynomial-time constant factor approximation algorithm, both unless\n            <jats:italic>P<\/jats:italic>\n            =\n            <jats:italic>NP<\/jats:italic>\n            . We then propose a simple greedy approximation algorithm for MBI with an almost tight approximation ratio and we test its performance on several real-world networks. We experimentally show that our algorithm highly increases both the betweenness score and the ranking of a given node and that it outperforms several competitive baselines. To speed up the computation of our greedy algorithm, we also propose a new dynamic algorithm for updating the betweenness of one node after an edge insertion, which might be of independent interest. Using the dynamic algorithm, we are now able to compute an approximation of MBI on networks with up to 10\n            <jats:sup>5<\/jats:sup>\n            edges in most cases in a matter of seconds or a few minutes.\n          <\/jats:p>","DOI":"10.1145\/3166071","type":"journal-article","created":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T12:41:46Z","timestamp":1534941706000},"page":"1-32","source":"Crossref","is-referenced-by-count":47,"title":["Improving the Betweenness Centrality of a Node by Adding Links"],"prefix":"10.1145","volume":"23","author":[{"given":"Elisabetta","family":"Bergamini","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Germany"}]},{"given":"Pierluigi","family":"Crescenzi","sequence":"additional","affiliation":[{"name":"University of Florence, Italy"}]},{"given":"Gianlorenzo","family":"D'angelo","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute (GSSI), Italy"}]},{"given":"Henning","family":"Meyerhenke","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Cologne, Germany"}]},{"given":"Lorenzo","family":"Severini","sequence":"additional","affiliation":[{"name":"ISI Foundation, Italy"}]},{"given":"Yllka","family":"Velaj","sequence":"additional","affiliation":[{"name":"University of Chieti-Pescara, Italy"}]}],"member":"320","published-online":{"date-parts":[[2018,8,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1080\/15326340600649052"},{"key":"e_1_2_1_2_1","volume-title":"Encyclopedia of Social Network Analysis and Mining","author":"Bader David A.","unstructured":"David A. Bader , Henning Meyerhenke , Peter Sanders , Christian Schulz , Andrea Kappes , and Dorothea Wagner . 2014. Benchmarking for graph clustering and partitioning . In Encyclopedia of Social Network Analysis and Mining . Springer , 73--82. David A. Bader, Henning Meyerhenke, Peter Sanders, Christian Schulz, Andrea Kappes, and Dorothea Wagner. 2014. Benchmarking for graph clustering and partitioning. In Encyclopedia of Social Network Analysis and Mining. Springer, 73--82."},{"key":"e_1_2_1_3_1","volume-title":"Retrieved","author":"Batagelj Vladimir","year":"2006","unstructured":"Vladimir Batagelj and Andrej Mrvar . 2006 . Pajek datasets . Retrieved July 23, 2018 from http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data. Vladimir Batagelj and Andrej Mrvar. 2006. Pajek datasets. Retrieved July 23, 2018 from http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00270"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556780903087124"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2016.1177802"},{"key":"e_1_2_1_8_1","volume-title":"16th International Symposium on Experimental Algorithms (SEA\u201917)","volume":"75","author":"Bergamini Elisabetta","year":"2017","unstructured":"Elisabetta Bergamini , Henning Meyerhenke , Mark Ortmann , and Arie Slobbe . 2017 . Faster betweenness centrality updates in evolving networks . In 16th International Symposium on Experimental Algorithms (SEA\u201917) , C. S. Iliopoulos, S. P. Pissis, S. J. Puglisi, and R. Raman (Eds.). Vol. 75 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 23:1--23:16. Elisabetta Bergamini, Henning Meyerhenke, Mark Ortmann, and Arie Slobbe. 2017. Faster betweenness centrality updates in evolving networks. In 16th International Symposium on Experimental Algorithms (SEA\u201917), C. S. Iliopoulos, S. P. Pissis, S. J. Puglisi, and R. Raman (Eds.). Vol. 75 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 23:1--23:16."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789813.2789825"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.014"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Bollob\u00e1s B\u00e9la","year":"2003","unstructured":"B\u00e9la Bollob\u00e1s , Christian Borgs , Jennifer Chayes , and Oliver Riordan . 2003 . Directed scale-free graphs . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903) . SIAM, 132--139. B\u00e9la Bollob\u00e1s, Christian Borgs, Jennifer Chayes, and Oliver Riordan. 2003. Directed scale-free graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). SIAM, 132--139."},{"key":"e_1_2_1_12_1","unstructured":"Michele Borassi and Emanuele Natale. 2016. KADABRA is an adaptive algorithm for betweenness via random approximation. CoRR abs\/1604.08553.  Michele Borassi and Emanuele Natale. 2016. KADABRA is an adaptive algorithm for betweenness via random approximation. CoRR abs\/1604.08553."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748050"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20086-6_4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2953882"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.03.011"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2015.09.003"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_39"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2015.09.001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9886-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_24_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability a Guide to the Theory of NP-Completeness. W.H. Freeman and Company New York.   M. R. Garey and D. S. Johnson. 1979. Computers and Intractability a Guide to the Theory of NP-Completeness. W.H. Freeman and Company New York."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791204.2791213"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom-PASSAT.2012.37"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850580"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.37"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492533"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Scalable online betweenness centrality in evolving graphs","volume":"99","author":"Kourtellis N.","year":"2015","unstructured":"N. Kourtellis , G. De Francisci Morales , and F. Bonchi . 2015 . Scalable online betweenness centrality in evolving graphs . IEEE Trans. Knowl. Data Eng. PP , 99 (2015), 1 -- 1 . N. Kourtellis, G. De Francisci Morales, and F. Bonchi. 2015. Scalable online betweenness centrality in evolving graphs. IEEE Trans. Knowl. Data Eng. PP, 99 (2015), 1--1.","journal-title":"IEEE Trans. Knowl. Data Eng. PP"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796570"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2015.07.053"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567948.2577358"},{"key":"e_1_2_1_35_1","volume-title":"SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl . 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved June 2014 from http:\/\/snap.stanford.edu\/data. Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved June 2014 from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-014-0800-9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939869"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_21"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Michel Minoux. 1978. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques J. Stoer (Ed.). Springer Berlin Heidelberg 234--243. https:\/\/link.springer.com\/chapter\/10.1007\/BFb0006528  Michel Minoux. 1978. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques J. Stoer (Ed.). Springer Berlin Heidelberg 234--243. https:\/\/link.springer.com\/chapter\/10.1007\/BFb0006528","DOI":"10.1007\/BFb0006528"},{"key":"e_1_2_1_41_1","volume-title":"Symp., MFCS","volume":"8635","author":"Nasre Meghana","year":"2014","unstructured":"Meghana Nasre , Matteo Pontecorvi , and Vijaya Ramachandran . 2014 . Betweenness centrality - Incremental and faster. In Mathematical Foundations of Computer Science 2014\u201439th Int . Symp., MFCS 2014. Lecture Notes in Computer Science Vol. 8635 . Springer, 577--588. Meghana Nasre, Matteo Pontecorvi, and Vijaya Ramachandran. 2014. Betweenness centrality - Incremental and faster. In Mathematical Foundations of Computer Science 2014\u201439th Int. Symp., MFCS 2014. Lecture Notes in Computer Science Vol. 8635. Springer, 577--588."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.08.003"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2757281"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063952"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.4"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/MILCOM.2013.319"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48971-0_29"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0423-0"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939770"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.64"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396795"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2010.03.003"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"D. P. Williamson and D. B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press.   D. P. Williamson and D. B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511921735"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062745.1062762"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3166071","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3166071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:55Z","timestamp":1750213615000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3166071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,22]]},"references-count":56,"alternative-id":["10.1145\/3166071"],"URL":"https:\/\/doi.org\/10.1145\/3166071","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,22]]}}}