Probability Seminar: Sayan Banerjee
Non-parametric change point detection in growing networks
Motivated by applications of modeling both real world and probabilistic systems such as recursive trees, the last few years have seen an explosion in models for dynamically evolving networks. In this talk, we consider models of growing networks which evolve via new vertices attaching to the pre-existing network according to one attachment function f till the system grows to size τ(n) < n, when new vertices switch their behavior to a different function g till the system reaches size n. We explore the effect of this change point on the evolution and final degree distribution of the network. In particular, we consider two cases, the standard model where τ(n) = γn as well as the quick big bang model when τ(n) = nγ for some 0 < γ < 1. In the former case, we obtain deterministic ‘fluid limits’ to track the degree evolution in the sup-norm metric. In the latter case, we show that the effect of the pre-change point dynamics ‘washes out’ when the network reaches size n, although the maximal degree feels the effect of the change. We also devise non-parametric, consistent estimators to detect the change point. Our methods exploit and develop new techniques connecting inhomogeneous continuous time branching processes (CTBP) to the evolving networks. This is joint work with Shankar Bhamidi and Iain Carmichael.