{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T23:49:03Z","timestamp":1769212143176,"version":"3.49.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,7,20]],"date-time":"2016-07-20T00:00:00Z","timestamp":1468972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"14th International Symposium on Experimental Algorithms"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,2,28]]},"abstract":"<jats:p>\n            The closeness centrality is a well-known measure of importance of a vertex within a given complex network. Having high closeness centrality can have positive impact on the vertex itself: hence, in this paper we consider the optimization problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. We will consider both the undirected and the directed graph cases. In both cases, we first prove that the optimization problem does not admit a polynomial-time approximation scheme (unless\n            <jats:italic>P<\/jats:italic>\n            =\n            <jats:italic>NP<\/jats:italic>\n            ), and then propose a greedy approximation algorithm (with an almost tight approximation ratio), whose performance is then tested on synthetic graphs and real-world networks.\n          <\/jats:p>","DOI":"10.1145\/2953882","type":"journal-article","created":{"date-parts":[[2016,7,21]],"date-time":"2016-07-21T15:13:24Z","timestamp":1469114004000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Greedily Improving Our Own Closeness Centrality in a Network"],"prefix":"10.1145","volume":"11","author":[{"given":"Pierluigi","family":"Crescenzi","sequence":"first","affiliation":[{"name":"University of Florence, Florence, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0377-7037","authenticated-orcid":false,"given":"Gianlorenzo","family":"D'angelo","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, L'Aquila, Italy"}]},{"given":"Lorenzo","family":"Severini","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, L'Aquila, Italy"}]},{"given":"Yllka","family":"Velaj","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, L'Aquila, Italy"}]}],"member":"320","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Arnetminer. Accessed January 15 2015 from http:\/\/arnetminer.org.  Arnetminer. Accessed January 15 2015 from http:\/\/arnetminer.org."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/15326340600649052"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935914"},{"key":"e_1_2_1_4_1","volume-title":"Emergence of scaling in random networks. Science 286, 5439","author":"Barabasi Albert-Laszlo","year":"1999"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00270"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.014"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2013.865686"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Bollob\u00e1s B\u00e9la","year":"2003"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748050"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20086-6_4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.03.011"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2015.09.003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_39"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_2_1_17_1","first-page":"290","article-title":"On random graphs I","volume":"6","author":"Erd\u0151s P.","year":"1959","journal-title":"Publ. Math."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9886-4"},{"key":"e_1_2_1_20_1","unstructured":"GNU. GLPK -- GNU Linear Programming Kit. http:\/\/www.gnu.org\/software\/glpk.  GNU. GLPK -- GNU Linear Programming Kit. http:\/\/www.gnu.org\/software\/glpk."},{"key":"e_1_2_1_21_1","unstructured":"IMDB. Accessed January 15 2015 from http:\/\/www.imdb.com.  IMDB. Accessed January 15 2015 from http:\/\/www.imdb.com."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.37"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492533"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796570"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_27_1","unstructured":"LAW. Laboratory for Web Algorithmics. Accessed January 15 2015 from http:\/\/law.di.unimi.it\/index.php.  LAW. Laboratory for Web Algorithmics. Accessed January 15 2015 from http:\/\/law.di.unimi.it\/index.php."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_29_1","volume-title":"Accessed","author":"Leskovec Jure","year":"2014"},{"key":"e_1_2_1_30_1","unstructured":"Michael Ley. DBLP. Accessed January 15 2015 from http:\/\/dblp.uni-trier.de\/.  Michael Ley. DBLP. Accessed January 15 2015 from http:\/\/dblp.uni-trier.de\/."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-014-0800-9"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_21"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060204"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.08.003"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2757281"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063952"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835818"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/MILCOM.2013.319"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of IJCAI Workshop on Learning Statistical Models from Relational Data.","author":"Popescul Alexandrin"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.64"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2013.6691611"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396795"},{"key":"e_1_2_1_47_1","unstructured":"Uri AlonLab. Accessed January 15 2015 from http:\/\/www.weizmann.ac.il\/mcb\/UriAlon\/.  Uri AlonLab. Accessed January 15 2015 from http:\/\/www.weizmann.ac.il\/mcb\/UriAlon\/."},{"key":"e_1_2_1_48_1","volume-title":"Strogatz","author":"Watts Duncan J.","year":"1998"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v60:10"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2010.27"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2953882","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2953882","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:22Z","timestamp":1750222582000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2953882"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,20]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,2,28]]}},"alternative-id":["10.1145\/2953882"],"URL":"https:\/\/doi.org\/10.1145\/2953882","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,20]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}