Rumors on evolving graphs through stationary times
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910988786204672 |
|---|---|
| author | Bonasorte, Vicenzo |
| author_facet | Bonasorte, Vicenzo |
| contents | We study rumor spreading in dynamic random graphs. Starting with a single informed vertex, the information flows until it reaches all the vertices of the graph (completion), according to the following process. At each step $k$, the information is propagated to neighbors of the informed vertices, in the $k$-th generated random graph. The way this information propagates from vertex to vertex at each step will depend on the ``protocol". We provide a method based on strong stationary times to study the completion time when the graphs are Markovian time dependent, using known results of the literature for independent graphs. The concept of strong stationary times is then extended to non-Markovian Dynamics using coupling from the past algorithms. This allows to extend results on completion times for non-Markov dynamics |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_04386 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rumors on evolving graphs through stationary times Bonasorte, Vicenzo Data Structures and Algorithms Discrete Mathematics Probability We study rumor spreading in dynamic random graphs. Starting with a single informed vertex, the information flows until it reaches all the vertices of the graph (completion), according to the following process. At each step $k$, the information is propagated to neighbors of the informed vertices, in the $k$-th generated random graph. The way this information propagates from vertex to vertex at each step will depend on the ``protocol". We provide a method based on strong stationary times to study the completion time when the graphs are Markovian time dependent, using known results of the literature for independent graphs. The concept of strong stationary times is then extended to non-Markovian Dynamics using coupling from the past algorithms. This allows to extend results on completion times for non-Markov dynamics |
| title | Rumors on evolving graphs through stationary times |
| topic | Data Structures and Algorithms Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2506.04386 |