Updating Katz centrality by counting walks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909598175199232 |
|---|---|
| author | Arrigo, Francesca Bertaccini, Daniele Filippo, Alessandro |
| author_facet | Arrigo, Francesca Bertaccini, Daniele Filippo, Alessandro |
| contents | We develop efficient and effective strategies for the update of Katz centralities after node and edge removal in simple graphs. We provide explicit formulas for the ``loss of walks" a network suffers when nodes/edges are removed, and use these to inform our algorithms. The theory builds on the newly introduced concept of $\cF$-avoiding first-passage walks. Further, bounds on the change of total network communicability are also derived. Extensive numerical experiments on synthetic and real-world networks complement our theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19560 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Updating Katz centrality by counting walks Arrigo, Francesca Bertaccini, Daniele Filippo, Alessandro Numerical Analysis Social and Information Networks 05C50, 05C90, 68R10, 65F99 We develop efficient and effective strategies for the update of Katz centralities after node and edge removal in simple graphs. We provide explicit formulas for the ``loss of walks" a network suffers when nodes/edges are removed, and use these to inform our algorithms. The theory builds on the newly introduced concept of $\cF$-avoiding first-passage walks. Further, bounds on the change of total network communicability are also derived. Extensive numerical experiments on synthetic and real-world networks complement our theoretical results. |
| title | Updating Katz centrality by counting walks |
| topic | Numerical Analysis Social and Information Networks 05C50, 05C90, 68R10, 65F99 |
| url | https://arxiv.org/abs/2411.19560 |