Long range dependence in evolving networks
Speaker: Shankar Bhamidi, University of North Carolina, Chapel Hill
Abstract: The goal of this talk is to describe probabilistic approaches to two major problems for dynamic networks, both of which are intricately connected to long range dependence in the evolution of such models.
- Change point detection: 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. The goal is to estimate the change point given the observation of the networks over time with no knowledge of the functions driving the dynamics. We will describe non-parametric estimators for such problems.
- Detecting the initial seed which resulted in the current state of the network: Imagine observing a static time slice of the network after some large time $n$ started with an initial seed. Suppose all one gets to see is the current topology of the network (without any label or age information). Developing probably efficient algorithms for estimating the initial seed has inspired intense activity over the last few years in the probability community. We will describe recent developments in addressing such questions including robustness results such as the fixation of so-called hub vertices as time evolves.