Collections > Electronic Theses and Dissertations > Inhomogeneous Branching Processes: A Tale of Two Networks
pdf

A basic theme in probability is the use of simple approximations to study complex systems. In this thesis we leverage the humble branching process to tackle two problems on random graphs. First, we study a variant of linear preferential attachment graphs which includes a change point in the parameter set driving the attachment dynamics. Using a continuous-time branching process embedding, we show how to estimate the change point and prove its consistency via a functional central limit theorem for the number of leaves. Additionally, we analyze the long-range dependence in the evolution of the graph, showing in particular that the exponent of the degree distribution does not feel the effect of any change. Second, motivated by recent studies showing that the spread of viral content on the internet takes surprising shapes, we introduce a simple discrete-time model for social media cascades whereby the transmission probability of the cascade decays with the distance from source. We argue that such a cascade can be reasonably approximated by a generation-dependent Galton-Watson process with infinite mean, and, as a first step to understanding its growth behavior, derive a simple criteria for its extinction.