Network evolution with Macroscopic Delays: asymptotics and condensation

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.

45 pages