Transient and Slim versus Recurrent and Fat: Random Walks and the Trees they Grow
| Autor: | Daniel R. Figueiredo, Giovanni Neglia, Giulio Iacobelli |
|---|---|
| Přispěvatelé: | Instituto de Matemática da Universidade Federal do Rio de Janeiro (IM / UFRJ), Universidade Federal do Rio de Janeiro (UFRJ), Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia (COPPE-UFRJ), Network Engineering and Operations (NEO ), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) |
| Rok vydání: | 2017 |
| Předmět: |
Statistics and Probability
Discrete mathematics Random graph General Mathematics 010102 general mathematics Probability (math.PR) [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Preferential attachment Degree distribution Random walk 01 natural sciences Upper and lower bounds [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI] 010104 statistics & probability symbols.namesake Bounded function symbols FOS: Mathematics Graph (abstract data type) Pareto distribution 0101 mathematics Statistics Probability and Uncertainty Mathematics - Probability Mathematics |
| Zdroj: | Journal of Applied Probability Journal of Applied Probability, Cambridge University press, 2019, 56 (03), pp.769-786. ⟨10.1017/jpr.2019.43⟩ Journal of Applied Probability, 2019, 56 (03), pp.769-786. ⟨10.1017/jpr.2019.43⟩ |
| ISSN: | 0021-9002 1475-6072 |
| DOI: | 10.48550/arxiv.1711.02913 |
| Popis: | International audience; Network growth models that embody principles such as preferential attachment and local attachment rules have received much attention over the last decade. Among various approaches, random walks have been leveraged to capture such principles. In this paper we consider the No Restart Random Walk (NRRW) model where a walker builds its graph (tree) while moving around. In particular, the walker takes s steps (a parameter) on the current graph. A new node with degree one is added to the graph and connected to the node currently occupied by the walker. The walker then resumes, taking another s steps, and the process repeats. We analyze this process from the perspective of the walker and the network, showing a fundamental dichotomy between transience and recurrence for the walker as well as power law and exponential degree distribution for the network. More precisely, we prove the following results: s = 1: the random walk is transient and the degree of every node is bounded from above by a geometric distribution. s even: the random walk is recurrent and the degree of non-leaf nodes is bounded from below by a power law distribution with exponent decreasing in s. We also provide a lower bound for the fraction of leaves in the graph, and for s = 2 our bound implies that the fraction of leaves goes to one as the graph size goes to infinity. NRRW exhibits an interesting mutual dependency between graph building and random walking that is fundamentally influenced by the parity of s. Understanding this kind of coupled dynamics is an important step towards modeling more realistic network growth processes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|