{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:07:44Z","timestamp":1775815664394,"version":"3.50.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319200859","type":"print"},{"value":"9783319200866","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-20086-6_4","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T08:27:10Z","timestamp":1434702430000},"page":"43-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Greedily Improving Our Own Centrality in A Network"],"prefix":"10.1007","author":[{"given":"Pierluigi","family":"Crescenzi","sequence":"first","affiliation":[]},{"given":"Gianlorenzo","family":"D\u2019Angelo","sequence":"additional","affiliation":[]},{"given":"Lorenzo","family":"Severini","sequence":"additional","affiliation":[]},{"given":"Yllka","family":"Velaj","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"4_CR1","unstructured":"Arnetminer (accessed: 2015\u201301-15). http:\/\/arnetminer.org"},{"key":"4_CR2","unstructured":"Easyjet (accessed: 2015\u201301-15). http:\/\/www.easyjet.com"},{"key":"4_CR3","unstructured":"GLPK - GNU Linear Programming Kit. http:\/\/www.gnu.org\/software\/glpk"},{"issue":"2","key":"4_CR4","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1080\/15326340600649052","volume":"22","author":"K Avrachenkov","year":"2006","unstructured":"Avrachenkov, K., Litvak, N.: The effect of new links on google pagerank. Stoc. Models 22(2), 319\u2013331 (2006)","journal-title":"Stoc. Models"},{"issue":"3\u20134","key":"4_CR5","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1080\/15427951.2013.865686","volume":"10","author":"P Boldi","year":"2014","unstructured":"Boldi, P., Vigna, S.: Axioms for centrality. Internet Math. 10(3\u20134), 222\u2013262 (2014)","journal-title":"Internet Math."},{"key":"4_CR6","unstructured":"Bollob\u00e1s, B., Borgs, C., Chayes, J., Riordan, O.: Directed scale-free graphs. In: Proc. of the 14th Annu. ACM-SIAM Symp. on Disc. Alg. (SODA), pp. 132\u2013139. SIAM (2003)"},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"U Brandes","year":"2001","unstructured":"Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163\u2013177 (2001)","journal-title":"J. Math. Sociol."},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Panconesi, A., Raghavan, P.: Models for the compressible web. In: Proc. of the 50th Annu. Symp. on Found. of Comput. Sci. (FOCS), pp. 331\u2013340. IEEE (2009)","DOI":"10.1109\/FOCS.2009.63"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Cohen, E., Delling, D., Pajor, T., Werneck, R.F.: Computing classic closeness centrality, at scale. Technical Report MSR-TR-2014-71 (2014)","DOI":"10.1145\/2660460.2660465"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/978-3-642-13731-0_39","volume-title":"Algorithm Theory - SWAT 2010","author":"ED Demaine","year":"2010","unstructured":"Demaine, E.D., Zadimoghaddam, M.: Minimizing the diameter of a network using shortcut edges. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 420\u2013431. Springer, Heidelberg (2010)"},{"key":"4_CR11","first-page":"290","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On random graphs I. Publ. Math. 6, 290\u2013297 (1959)","journal-title":"Publ. Math."},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4) (1998)","DOI":"10.1145\/285055.285059"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Ishakian, V., Erd\u00f6s, D., Terzi, E., Bestavros, A.: A framework for the evaluation and management of network centrality. In: Proc. of the 12th SIAM Int. Conf. on Data Mining (SDM), pp. 427\u2013438. SIAM (2012)","DOI":"10.1137\/1.9781611972825.37"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the web graph. In: Proc. of the 41st Annu. Symp. on Found. of Comput. Sci. (FOCS), pp. 57\u201365. IEEE (2000)","DOI":"10.1109\/SFCS.2000.892065"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: KONECT - The Koblenz network collection. In: Proc. of the 1st Int. Web Observatory Work. (WOW), pp. 1343\u20131350 (2013)","DOI":"10.1145\/2487788.2488173"},{"key":"4_CR16","unstructured":"Malighetti, P., Martini, G., Paleari, S., Redondi, R.: The impacts of airport centrality in the EU network and inter-airport competition on airport efficiency. Technical Report MPRA-7673 (2009)"},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/978-3-642-03685-9_21","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"A Meyerson","year":"2009","unstructured":"Meyerson, A., Tagiku, B.: Minimizing average shortest path distances via shortcut edge addition. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. LNCS, vol. 5687, pp. 272\u2013285. Springer, Heidelberg (2009)"},{"issue":"1","key":"4_CR18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G Nemhauser","year":"1978","unstructured":"Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.tcs.2013.08.003","volume":"518","author":"M Olsen","year":"2014","unstructured":"Olsen, M., Viglas, A.: On the approximability of the link building problem. Theor. Comput. Sci. 518, 96\u2013116 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Riondato, M., Kornaropoulos, E.M.: Fast approximation of betweenness centrality through sampling. In: Proc. of the 7th ACM Int. Conf. on Web Search and Data Mining, (WSDM), pp. 413\u2013422. ACM (2014)","DOI":"10.1145\/2556195.2556224"},{"key":"4_CR21","unstructured":"Staudt, C.L., Sazonovs, A., Meyerhenke, H.: Networkit: An interactive tool suite for high-performance network analysis. arXiv preprint arXiv:1403.3005 (2014)"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Williamson, D., Shmoys, D.: The Design of Approximation Algorithms. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511921735"},{"issue":"10","key":"4_CR23","doi-asserted-by":"publisher","first-page":"2107","DOI":"10.1002\/asi.21128","volume":"60","author":"E Yan","year":"2009","unstructured":"Yan, E., Ding, Y.: Applying centrality measures to impact analysis: A coauthorship network analysis. J. Ass. Inf. Sci. Tech. 60(10), 2107\u20132118 (2009)","journal-title":"J. Ass. Inf. Sci. Tech."}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-20086-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:05:36Z","timestamp":1748459136000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-20086-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319200859","9783319200866"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-20086-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}