Threshold-Driven Streaming Graph: Expansion and Rumor Spreading
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916873521594368 |
|---|---|
| author | Angileri, Flora Clementi, Andrea Natale, Emanuele Salvi, Michele Ziccardi, Isabella |
| author_facet | Angileri, Flora Clementi, Andrea Natale, Emanuele Salvi, Michele Ziccardi, Isabella |
| contents | A randomized distributed algorithm called RAES was introduced in [Becchetti et al., SODA 2020] to extract a bounded-degree expander from a dense $n$-vertex expander graph $G = (V, E)$. The algorithm relies on a simple threshold-based procedure. A key assumption in [Becchetti et al., SODA 2020] is that the input graph $G$ is static - i.e., both its vertex set $V$ and edge set $E$ remain unchanged throughout the process - while the analysis of RAES in dynamic models is left as a major open question.
In this work, we investigate the behavior of RAES under a dynamic graph model induced by a streaming node-churn process (also known as the sliding window model), where, at each discrete round, a new node joins the graph and the oldest node departs. This process yields a bounded-degree dynamic graph $\mathcal{G} =\{ G_t = (V_t, E_t) : t \in \mathbb{N}\}$ that captures essential characteristics of peer-to-peer networks -- specifically, node churn and threshold on the number of connections each node can manage. We prove that every snapshot $G_t$ in the dynamic graph sequence has good expansion properties with high probability. Furthermore, we leverage this property to establish a logarithmic upper bound on the completion time of the well-known PUSH and PULL rumor spreading protocols over the dynamic graph $\mathcal{G}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_23533 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Threshold-Driven Streaming Graph: Expansion and Rumor Spreading Angileri, Flora Clementi, Andrea Natale, Emanuele Salvi, Michele Ziccardi, Isabella Distributed, Parallel, and Cluster Computing Probability A randomized distributed algorithm called RAES was introduced in [Becchetti et al., SODA 2020] to extract a bounded-degree expander from a dense $n$-vertex expander graph $G = (V, E)$. The algorithm relies on a simple threshold-based procedure. A key assumption in [Becchetti et al., SODA 2020] is that the input graph $G$ is static - i.e., both its vertex set $V$ and edge set $E$ remain unchanged throughout the process - while the analysis of RAES in dynamic models is left as a major open question. In this work, we investigate the behavior of RAES under a dynamic graph model induced by a streaming node-churn process (also known as the sliding window model), where, at each discrete round, a new node joins the graph and the oldest node departs. This process yields a bounded-degree dynamic graph $\mathcal{G} =\{ G_t = (V_t, E_t) : t \in \mathbb{N}\}$ that captures essential characteristics of peer-to-peer networks -- specifically, node churn and threshold on the number of connections each node can manage. We prove that every snapshot $G_t$ in the dynamic graph sequence has good expansion properties with high probability. Furthermore, we leverage this property to establish a logarithmic upper bound on the completion time of the well-known PUSH and PULL rumor spreading protocols over the dynamic graph $\mathcal{G}$. |
| title | Threshold-Driven Streaming Graph: Expansion and Rumor Spreading |
| topic | Distributed, Parallel, and Cluster Computing Probability |
| url | https://arxiv.org/abs/2507.23533 |