Growing Networks with Random Walks

Abstract: Network growth is a fundamental theme that has received much attention over the past decades. Various models  that embody principles such as preferential attachment and local attachment rules have  been proposed and studied. Among various approaches, random walks have been leveraged to capture such principles.  In this work we propose and study the No Restart Random Walk (NRRW) model where a walker builds its network while moving around. In particular, after the walker takes s steps (a parameter) on the current network a new node with degree one is added to the network and connected to the node currently occupied by the walker. The walker then resumes, taking another s steps, and the process repeats. Through extensive simulations and theoretical arguments, we analyze this process from two different perspectives: the walker and the network. We show that, depending on the parity of s, there is a fundamental dichotomy between transience and recurrence for the walker as well as exponential and  heavy-tailed  degree distribution for the generated network. NRRW exhibits an interesting mutual dependency between network building and random walking. Understanding this kind of coupled dynamics is an important step towards modeling more realistic network growth processes.

Finally, we shall also present, and briefly discuss, a couple of recent variations of the NRRW model.

Posted on Jun 6, 2019 in Núcleo Modelos Estocásticos de Sistemas Complejos y Desordenados, Seminars, Stochastic Modeling