Abstract:Preferential attachment models typically assume that each arriving vertex observes the current network before choosing its connection. Motivated by distributed systems and social networks, we study network delay, where this decision uses only a time-delayed snapshot. We focus on macroscopic delays, for which the delay is proportional to the current network size and hence removes a non-vanishing fraction of the available information. We identify the local weak limit as a continuous-time branching process whose reproduction point process has memory of its entire past. Since this non-Markovian description is difficult to analyze directly, we construct a dual branching process in which edges reproduce, recovering enough independence for quantitative analysis. This yields a detailed understanding of how the delay affects features such as the tail behavior of the asymptotic degree distribution, together with necessary and sufficient conditions for condensation-the phenomenon in which a positive fraction of the degree mass escapes to infinity. We conclude by studying the impact of the delay distribution on macroscopic functionals such as the root degree.
From: Sayan Banerjee [view email]
[v1]
Mon, 9 Sep 2024 20:16:58 UTC (7,947 KB)
[v2]
Tue, 4 Aug 2026 21:34:30 UTC (2,311 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。