{"ID":2888375,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.23533","arxiv_id":"2507.23533","title":"Threshold-Driven Streaming Graph: Expansion and Rumor Spreading","abstract":"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}$.","short_abstract":"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 $...","url_abs":"https://arxiv.org/abs/2507.23533","url_pdf":"https://arxiv.org/pdf/2507.23533v1","authors":"[\"Flora Angileri\",\"Andrea Clementi\",\"Emanuele Natale\",\"Michele Salvi\",\"Isabella Ziccardi\"]","published":"2025-07-31T13:19:11Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"math.PR\"]","methods":"[]","has_code":false}