{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T13:40:05Z","timestamp":1729518005337,"version":"3.28.0"},"reference-count":42,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T00:00:00Z","timestamp":1708646400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. Appl. Probab."],"published-print":{"date-parts":[[2024,9]]},"abstract":"Abstract<\/jats:title>Centrality measures aim to indicate who is important in a network. Various notions of \u2018being important\u2019 give rise to different centrality measures. In this paper, we study how important the central vertices are for the connectivity structure<\/jats:italic> of the network, by investigating how the removal of the most central vertices affects the number of connected components and the size of the giant component. We use local convergence techniques<\/jats:italic> to identify the limiting number of connected components for locally converging graphs and centrality measures that depend on the vertex\u2019s neighbourhood. For the size of the giant, we prove a general upper bound. For the matching lower bound, we specialise to the case of degree centrality<\/jats:italic> on one of the most popular models in network science, the configuration model<\/jats:italic>, for which we show that removal of the highest-degree vertices destroys the giant most.<\/jats:p>","DOI":"10.1017\/jpr.2023.106","type":"journal-article","created":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T10:33:17Z","timestamp":1708684397000},"page":"967-998","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Connectivity of random graphs after centrality-based vertex removal"],"prefix":"10.1017","volume":"61","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-1331-9697","authenticated-orcid":false,"given":"Remco","family":"van der Hofstad","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-1522-3835","authenticated-orcid":false,"given":"Manish","family":"Pandey","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,2,23]]},"reference":[{"key":"S0021900223001067_ref22","unstructured":"[22] Hofstad, R. v. d. (2021). The giant in random graphs is almost local. Available at arXiv:2103.11733."},{"key":"S0021900223001067_ref4","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1137\/050643799","article-title":"Monte Carlo methods in PageRank computation: when one iteration is sufficient","volume":"45","author":"Avrachenkov","year":"2007","journal-title":"SIAM J. Numer. Anal."},{"key":"S0021900223001067_ref23","unstructured":"[23] Hofstad, R. v. d. (2023+). Random Graphs and Complex Networks, Vol. 2. In preparation. Available at http:\/\/www.win.tue.nl\/~rhofstad\/NotesRGCNII.pdf."},{"key":"S0021900223001067_ref30","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1002\/rsa.20231","article-title":"A new approach to the giant component problem","volume":"34","author":"Janson","year":"2009","journal-title":"Random Structures Algorithms"},{"key":"S0021900223001067_ref10","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","article-title":"A probabilistic proof of an asymptotic formula for the number of labelled regular graphs","volume":"1","author":"Bollob\u00e1s","year":"1980","journal-title":"European J. Combinatorics"},{"key":"S0021900223001067_ref35","doi-asserted-by":"crossref","first-page":"1571","DOI":"10.1038\/s41598-018-19356-4","article-title":"Decentralized dynamic understanding of hidden relations in complex networks","volume":"8","author":"Mocanu","year":"2018","journal-title":"Scientific Reports"},{"key":"S0021900223001067_ref3","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1080\/15427951.2006.10129120","article-title":"PageRank of scale-free growing networks","volume":"3","author":"Avrachenkov","year":"2006","journal-title":"Internet Math."},{"volume":"110","year":"2004","author":"Aldous","key":"S0021900223001067_ref1"},{"key":"S0021900223001067_ref12","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.socnet.2004.11.008","article-title":"Centrality and network flow","volume":"27","author":"Borgatti","year":"2005","journal-title":"Soc. Netw."},{"key":"S0021900223001067_ref11","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.jctb.2015.03.002","article-title":"An old approach to the giant component problem","volume":"113","author":"Bollob\u00e1s","year":"2015","journal-title":"J. Combinatorial Theory B"},{"volume":"8882","year":"2014","author":"Chen","key":"S0021900223001067_ref15"},{"volume-title":"Principles of Mathematical Analysis","year":"1964","author":"Rudin","key":"S0021900223001067_ref40"},{"key":"S0021900223001067_ref34","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1080\/15427951.2007.10129293","article-title":"In-Degree and PageRank: why do they follow similar power laws?","volume":"4","author":"Litvak","year":"2007","journal-title":"Internet Math."},{"key":"S0021900223001067_ref42","doi-asserted-by":"crossref","first-page":"5550","DOI":"10.1038\/s41598-022-09341-3","article-title":"Identifying influential spreaders in complex networks for disease spread and control","volume":"12","author":"Wei","year":"2022","journal-title":"Scientific Reports"},{"key":"S0021900223001067_ref7","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1145\/1052934.1052938","article-title":"Inside PageRank","volume":"5","author":"Bianchini","year":"2005","journal-title":"ACM Trans. Internet Technol."},{"key":"S0021900223001067_ref9","doi-asserted-by":"crossref","unstructured":"[9] Boldi, P. , Santini, M. and Vigna, S. (2005). PageRank as a function of the damping factor. In Proceedings of the 14th International Conference on World Wide Web (WWW \u201905), pp. 557\u2013566. ACM, New York.","DOI":"10.1145\/1060745.1060827"},{"key":"S0021900223001067_ref16","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/rsa.20700","article-title":"Generalized PageRank on directed configuration networks","volume":"51","author":"Chen","year":"2017","journal-title":"Random Structures Algorithms"},{"key":"S0021900223001067_ref21","doi-asserted-by":"crossref","unstructured":"[21] Hofstad, R. v. d. (2017). Random Graphs and Complex Networks, Vol. 1 (Cambridge Series in Statistical and Probabilistic Mathematics 43). Cambridge University Press.","DOI":"10.1017\/9781316779422"},{"key":"S0021900223001067_ref26","doi-asserted-by":"crossref","unstructured":"[26] Hofstad, R. v. d. , Hooghiemstra, G. and Znamenski, D. (2007). A phase transition for the diameter of the configuration model. Internet Math. 4, 113\u2013128.","DOI":"10.1080\/15427951.2007.10129138"},{"key":"S0021900223001067_ref14","doi-asserted-by":"crossref","first-page":"1377","DOI":"10.1007\/s10955-006-9168-x","article-title":"Generating simple random graphs with prescribed degree distribution","volume":"124","author":"Britton","year":"2006","journal-title":"J. Statist. Phys."},{"key":"S0021900223001067_ref29","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1239\/jap\/1417528471","article-title":"The probability that a random multigraph is simple, II","volume":"51A","author":"Janson","year":"2014","journal-title":"J. Appl. Prob."},{"key":"S0021900223001067_ref39","unstructured":"[39] Page, L. , Brin, S. , Motwani, R. and Winograd, T. (1999). The PageRank citation ranking: bringing order to the web. Technical Report 1999-66, Stanford InfoLab. Previous number = SIDL-WP-1999-0120."},{"key":"S0021900223001067_ref31","doi-asserted-by":"crossref","unstructured":"[31] Jelenkovi\u0107, P. R. and Olvera-Cravioto, M. (2010). Information ranking and power laws on trees. Adv. Appl. Prob. 42, 1057\u20131093.","DOI":"10.1017\/S0001867800004523"},{"key":"S0021900223001067_ref28","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1017\/S0963548308009644","article-title":"The probability that a random multigraph is simple","volume":"18","author":"Janson","year":"2009","journal-title":"Combinatorics Prob. Comput."},{"key":"S0021900223001067_ref38","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198805090.001.0001","volume-title":"Networks","author":"Newman","year":"2018"},{"key":"S0021900223001067_ref19","doi-asserted-by":"crossref","unstructured":"[19] Garavaglia, A. , Hofstad, R. v. d. and Litvak, N. (2020). Local weak convergence for PageRank. Ann. Appl. Prob. 30, 40\u201379.","DOI":"10.1214\/19-AAP1494"},{"key":"S0021900223001067_ref2","unstructured":"[2] Anthonisse, J. M. (1971). The rush in a directed graph. Stichting Mathematisch Centrum, Mathematische Besliskunde BN 9\/71, 1\u201310."},{"key":"S0021900223001067_ref17","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1007\/s10955-018-2071-4","article-title":"The tail does not determine the size of the giant","volume":"173","author":"Deijfen","year":"2018","journal-title":"J. Statist. Phys."},{"key":"S0021900223001067_ref24","doi-asserted-by":"crossref","unstructured":"[24] Hofstad, R. v. d. , Hooghiemstra, G. and Van Mieghem, P. (2005). Distances in random graphs with finite variance degrees. Random Structures Algorithms 27, 76\u2013123.","DOI":"10.1002\/rsa.20063"},{"key":"S0021900223001067_ref6","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1214\/EJP.v6-96","article-title":"Recurrence of distributional limits of finite planar graphs","volume":"6","author":"Benjamini","year":"2001","journal-title":"Electron. J. Prob."},{"key":"S0021900223001067_ref18","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1038\/s42005-022-00949-5","article-title":"Linking the network centrality measures closeness and degree","volume":"5","author":"Evans","year":"2022","journal-title":"Commun. Phys."},{"key":"S0021900223001067_ref20","unstructured":"[20] Hinne, M. (2011). Local approximation of centrality measures. Master\u2019s thesis, Radboud University Nijmegen, The Netherlands."},{"key":"S0021900223001067_ref32","doi-asserted-by":"crossref","first-page":"2312","DOI":"10.1016\/j.spa.2019.07.002","article-title":"PageRank on inhomogeneous random digraphs","volume":"130","author":"Lee","year":"2020","journal-title":"Stochastic Process. Appl."},{"key":"S0021900223001067_ref13","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","article-title":"The anatomy of a large-scale hypertextual web search engine","volume":"30","author":"Brin","year":"1998","journal-title":"Comput. Netw. ISDN Syst."},{"volume":"9479","year":"2015","author":"Leskel\u00e4","key":"S0021900223001067_ref33"},{"key":"S0021900223001067_ref36","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/rsa.3240060204","article-title":"A critical point for random graphs with a given degree sequence","volume":"6","author":"Molloy","year":"1995","journal-title":"Random Structures Algorithms"},{"key":"S0021900223001067_ref41","doi-asserted-by":"crossref","first-page":"e0134794","DOI":"10.1371\/journal.pone.0134794","article-title":"The Pagerank-Index: going beyond citation counts in quantifying scientific impact of researchers","volume":"10","author":"Senanayake","year":"2015","journal-title":"PLoS One"},{"key":"S0021900223001067_ref27","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1214\/EJP.v14-603","article-title":"On percolation in random graphs with given vertex degrees","volume":"14","author":"Janson","year":"2009","journal-title":"Electron. J. Prob."},{"key":"S0021900223001067_ref5","doi-asserted-by":"crossref","first-page":"3060","DOI":"10.1214\/21-AAP1757","article-title":"PageRank asymptotics on directed preferential attachment networks","volume":"32","author":"Banerjee","year":"2022","journal-title":"Ann. Appl. Prob."},{"key":"S0021900223001067_ref8","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1080\/15427951.2013.865686","article-title":"Axioms for centrality","volume":"10","author":"Boldi","year":"2014","journal-title":"Internet Math."},{"key":"S0021900223001067_ref37","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1017\/S0963548398003526","article-title":"The size of the giant component of a random graph with a given degree sequence","volume":"7","author":"Molloy","year":"1998","journal-title":"Combinatorics Prob. Comput."},{"key":"S0021900223001067_ref25","doi-asserted-by":"crossref","unstructured":"[25] Hofstad, R. v. d. , Hooghiemstra, G. and Znamenski, D. (2007). Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Prob. 12, 703\u2013766.","DOI":"10.1214\/EJP.v12-420"}],"container-title":["Journal of Applied Probability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0021900223001067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T13:05:26Z","timestamp":1729515926000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0021900223001067\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,23]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["S0021900223001067"],"URL":"https:\/\/doi.org\/10.1017\/jpr.2023.106","relation":{},"ISSN":["0021-9002","1475-6072"],"issn-type":[{"type":"print","value":"0021-9002"},{"type":"electronic","value":"1475-6072"}],"subject":[],"published":{"date-parts":[[2024,2,23]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press on behalf of Applied Probability Trust","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}