Transient and slim versus recurrent and fat: random walks and the trees they grow

DOI10.1017/JPR.2019.43MaRDI QIDQ5235052zbMATH OpenOpenAlexFDO

Authors Daniel R. Figueiredo, Giovanni Neglia, Giulio Iacobelli

Publication date 7 October 2019

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.02913

zbMATH Keywords

network growth modelrandom graphrandom walk

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Processes in random environments (60K37)

Abstract: 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: i) for s=1 the random walk is transient and the degree of every node is bounded from above by a geometric distribution. ii) for 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.

Recommendations

• Tree builder random walk: recurrence, transience and ballisticity
• On a random walk that grows its own tree
• Recurrent and transient trees
• The type problem for random walks on trees
• Random walk attachment graphs

Cites work

• Emergence of Scaling in Random Networks
• From transience to recurrence with Poisson tree frogs
• scientific article; zbMATH DE number 5032032 (Why is no real title available?)
• Localization for linearly edge reinforced random walks
• Networks
• Random walk attachment graphs
• Transience of edge-reinforced random walk
• Type transition of simple random walks on randomly directed regular lattices
• Walking within growing domains: recurrence versus transience

Cited in

(7)

• On a random walk that grows its own tree
• Tree builder random walk: recurrence, transience and ballisticity
• Walking within growing domains: recurrence versus transience
• A phase transition for the biased tree-builder random walk
• The recurrence/transience of random walks on a bounded grid in an increasing dimension
• Recurrence, transience and degree distribution for the tree builder random walk
• Structural results for the tree builder random walk

This page was built for publication: Transient and slim versus recurrent and fat: random walks and the trees they grow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5235052)