Simulating the Tree Builder Random Walk in R with tbrw

Created: April 13, 2025 16:59 updated: April 13, 2025 16:59

A snapshot of the TBRW. The square vertex represents the root, whereas the blue vertex, the position of the walker.

The Tree Builder Random Walk (TBRW) is a stochastic process where a walker walks on a dynamically growing tree. At each time step, the walker may add new leaves to its current position, growing the tree as it walks. This model exhibits various behaviors—such as recurrence, transience, or ballisticity—depending on specific parameters of the process.

Purpose of the tbrw Package

The tbrw R package provides tools to simulate the TBRW process, with it you can:

Generate the adjacency list of the tree after a specified number of steps.
Track the distance and degree of vertices encountered during the walk.
Visualize the evolving tree structure using graphing tools like igraph.

This package is particularly useful for researchers interested in exploring the dynamics of self-modifying random walks and their resulting structures.

Key Features

Simulation of TBRW: Easily simulate the Tree Builder Random Walk for a given number of steps.
Tree Structure Output: Obtain the adjacency list representing the tree's structure at any point.
Vertex Metrics: Monitor metrics such as the degree and distance of vertices from the root.
Visualization Support: Integrate with visualization packages like igraph to plot and analyze the tree.

How to Use tbrw

Installation

To install the development version of tbrw from GitHub:

# Install devtools if you haven't already
install.packages("devtools")

# Install tbrw
devtools::install_github("rbribeiro/tbrw")

Basic Usage

After installation, load the package:


library(tbrw)

To simulate a Tree Builder Random Walk with a Bernoulli distribution of parameter .5


# Simulate TBRW for 100 steps
result <- bgrw(steps = 100, prob = 0.5)

# View the adjacency list of the resulting tree
adjacency_list <- result$adjacency

# View the degrees of vertices
vertex_degrees <- result$degrees

# View the distances of vertices from the root
vertex_distances <- result$distances

Visualization

To visualize the generated tree, you can use the igraph package:


# Install igraph if you haven't already
install.packages("igraph")
library(igraph)

# Create a graph object from the adjacency list
g <- graph_from_adj_list(adjacency_list)

# Plot the graph
plot(g)

This will provide a visual representation of the tree structure resulting from the TBRW simulation.

For more details and to access the source code, visit the tbrw GitHub repository.