Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2202.02888 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914645410840576 |
|---|---|
| author | Arrigo, Francesca Higham, Desmond J. Noferini, Vanni Wood, Ryan |
| author_facet | Arrigo, Francesca Higham, Desmond J. Noferini, Vanni Wood, Ryan |
| contents | We extend the notion of nonbacktracking walks from unweighted graphs to graphs whose edges have a nonnegative weight. Here the weight associated with a walk is taken to be the product over the weights along the individual edges. We give two ways to compute the associated generating function, and corresponding node centrality measures. One method works directly on the original graph and one uses a line graph construction followed by a projection. The first method is more efficient, but the second has the advantage of extending naturally to time-evolving graphs. Computational results are also provided. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_02888 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Weighted enumeration of nonbacktracking walks on weighted graphs Arrigo, Francesca Higham, Desmond J. Noferini, Vanni Wood, Ryan Combinatorics We extend the notion of nonbacktracking walks from unweighted graphs to graphs whose edges have a nonnegative weight. Here the weight associated with a walk is taken to be the product over the weights along the individual edges. We give two ways to compute the associated generating function, and corresponding node centrality measures. One method works directly on the original graph and one uses a line graph construction followed by a projection. The first method is more efficient, but the second has the advantage of extending naturally to time-evolving graphs. Computational results are also provided. |
| title | Weighted enumeration of nonbacktracking walks on weighted graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2202.02888 |