Connectivity of random graphs after centrality-based vertex removal
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916487362510848 |
|---|---|
| author | Pandey, Manish van der Hofstad, Remco |
| author_facet | Pandey, Manish van der Hofstad, Remco |
| contents | Centrality measures aim to indicate who is important in a network. Various notions of `being important' give rise to different centrality measures. In this paper, we study how important the central vertices are for the connectivity structure 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 to identify the limiting number of connected components for locally converging graphs and centrality measures that depend on the vertex's neighborhood. For the size of the giant, we prove a general upper bound. For the matching lower bound, we specialize to the case of degree centrality on one of the most popular models in network science, the configuration model, for which we show that removal of the highest-degree vertices destroys the giant most. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_16596 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Connectivity of random graphs after centrality-based vertex removal Pandey, Manish van der Hofstad, Remco Probability 60G99, 05C80, 60E15 Centrality measures aim to indicate who is important in a network. Various notions of `being important' give rise to different centrality measures. In this paper, we study how important the central vertices are for the connectivity structure 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 to identify the limiting number of connected components for locally converging graphs and centrality measures that depend on the vertex's neighborhood. For the size of the giant, we prove a general upper bound. For the matching lower bound, we specialize to the case of degree centrality on one of the most popular models in network science, the configuration model, for which we show that removal of the highest-degree vertices destroys the giant most. |
| title | Connectivity of random graphs after centrality-based vertex removal |
| topic | Probability 60G99, 05C80, 60E15 |
| url | https://arxiv.org/abs/2303.16596 |