random_walk

Random walk primitives for graph analysis and community detection.

Provides basic random walk operations that can be used for community detection, node ranking, and graph exploration.

Functions

Function	Purpose
`random_walk/3`	Simple random walk from a start node
`random_walk_with_restart/4`	Random walk with restart probability (RWR)
`transition_probabilities/3`	Calculate transition probabilities from a node

When to Use

Graph exploration: Traverse graph in a stochastic manner
Similarity measure: Random walk distances between nodes
Community detection: Used by Walktrap and other algorithms
Personalized PageRank: RWR is related to PPR

Example

import yog
import yog/community/random_walk as rw

let graph =
  yog.undirected()
  |> yog.add_node(1, "A")
  |> yog.add_node(2, "B")
  |> yog.add_node(3, "C")
  |> yog.add_edges([#(1, 2, 1), #(2, 3, 1)])

// Simple random walk
let path = rw.random_walk(graph, start: 1, steps: 10)
// => [1, 2, 3, 2, 1, ...]  (stochastic)

// Random walk with restart (Personalized PageRank style)
let path = rw.random_walk_with_restart(graph, start: 1, restart_prob: 0.15, steps: 100)

// Transition probabilities from a node
let probs = rw.transition_probabilities(graph, node: 1, to_float: fn(x) { x })
// => [#(2, 1.0)]  // 100% chance to go to node 2

Values

random_walk

</>

pub fn random_walk(
  graph: model.Graph(n, e),
  start: Int,
  steps: Int,
) -> List(Int)

Basic random walk from a starting node. Each step chooses a neighbor uniformly at random (unweighted). Returns the sequence of node IDs visited, including the start node. Stops early if a sink (node with no outgoing edges) is reached.

random_walk_with_restart

</>

pub fn random_walk_with_restart(
  graph: model.Graph(n, e),
  start: Int,
  restart_prob: Float,
  steps: Int,
) -> List(Int)

Random walk with a restart probability (Personalized PageRank style). At each step, there is a restart_prob chance of jumping back to the start node. If a sink is reached, it always jumps back to the start node.

transition_probabilities

</>

pub fn transition_probabilities(
  graph: model.Graph(n, e),
  node: Int,
  to_float: fn(e) -> Float,
) -> List(#(Int, Float))

Calculates transition probabilities from a node based on edge weights. Assumes weights are numeric and can be converted to Float.