Random Walks: Core Concepts
1 Introduction through Games: Ladder Lottery
In this module, we will learn random walks, one of the most fundamental techniques in network analysis. We’ll explore what random walks are, how to simulate them on networks, their behavior patterns, and their connections to community detection and network centralities.
To make these concepts tangible, let’s start with a fun game that perfectly illustrates random walk principles:
:class: tip
Ladder Lottery is a fun East Asian game, also known as “鬼腳圖” (Guijiaotu) in Chinese, “阿弥陀籤” (Amida-kuzi) in Japanese, “사다리타기” (Sadaritagi) in Korean, and “Ladder Lottery” in English. The game is played as follows: 1. A player is given a board with a set of vertical lines. 2. The player chooses a line and starts to move along the line 3. When hitting a horizontal line, the player must move along the horizontal line and then continue to move along the next vertical line. 4. The player wins if the player can hit a marked line at the bottom of the board. 5. You cannot see the horizontal lines in advance!
Play the {{ ‘Ladder Lottery Game! 🎮✨’.replace(‘BASE_URL’, base_url) }} and try to answer the following questions:
- Is there a strategy to maximize the probability of winning?
- How does the probability of winning change as the number of horizontal lines increases?
The Ladder Lottery game is actually a perfect introduction to random walks! In this game, states are the vertical lines, transitions happen when you encounter horizontal connections, randomness comes from not knowing where the horizontal lines are placed, and long-term behavior determines your probability of winning. This simple game illustrates many key concepts we’ll explore in random walks on networks.
2 Understanding Random Walks
Suppose you walk in a city. You are drunk and your feet have no idea where to go. You just take a step wherever your feet take you. At every intersection, you make a random decision and take a step. This is the core idea of a random walk.
While your feet are taking you to a random street, after making many steps and looking back, you will realize that you have been to certain places more frequently than others. If you were to map the frequency of your visits to each street, you will end up with a distribution that tells you about salient structure of the street network.
More formally, a random walk in undirected networks follows this process: 1. Start at a node i 2. Randomly choose an edge to traverse to a neighbor node j 3. Repeat step 2 until you have taken T steps
In directed networks, a random walker can only move along the edge direction, and it can be that the random walker is stuck in a so-called "dead end" that does not have any outgoing edges.When studying random walks, we want to understand several key aspects: short-term behavior (where does the walker go in the first few steps?), long-term behavior (after many steps, where does the walker spend most of its time?), structural insights (what does the walker’s behavior tell us about the network?), and applications (how can we use random walks for centrality and community detection?).
3 Pen and Paper Exercises
Before diving into the mathematical details and coding, it’s important to work through some fundamental concepts by hand.
These exercises will help you: - Understand the basic mechanics of random walks - Calculate transition probabilities manually - Explore simple examples of stationary distributions - Connect random walk concepts to network properties
4 Preview: What’s Coming Next
In the following sections, we will: 1. Dive into the mathematics behind random walks and their connection to Markov chains 2. Implement random walks in code and visualize their behavior on real networks 3. Explore applications including centrality measures and community detection 4. Work through practical exercises to solidify your understanding
The journey from this simple concept to powerful network analysis tools is both fascinating and practical!