Long Range Dependence in Evolving Networks

          @misc{ scivideos_22614,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/22614},
            author = {},
            keywords = {},
            language = {en},
            title = {Long Range Dependence in Evolving Networks},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {sep},
            note = {22614 see, \url{https://scivideos.org/simons-institute/22614}}
          }
          

Abstract

Abstract The goal of this talk is to describe probabilistic approaches to three major problems for dynamic networks, both of which are intricately connected to long range dependence in the evolution of such models: 1.Nonparametric 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. 2. 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. 3. Co-evolving networks: models of networks where dynamics on the network (directed random walks towards the root) modifies the structure of the network which then impacts behavior of subsequent dynamics. We will describe non-trivial phase transitions of condensation around the root and its connection to quasi-stationary distributions of 1-d random walks.