Random Surfing (Random Walks with Coin Flips) Model

A Random Surfing (Random Walks with Coin Flips) Model is a Random Surfing Model that takes (coin-flip) random steps.

• Example(s):
  • …
• Counter-Example(s):
  • a Random Surfing (1-Step Walk with Self-Loop) Model,
  • a Random Walk Model,
  • a Branching Random Walk Model,
  • a Hill Climbing Model.
• See: Markov Chain, Graph Theory, Web Page, Hyperlink, URL.

---

---

References

2021

• (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Random_surfing_model#Model_1 Retrieved:2021-8-15.

At time [math]\displaystyle{ t }[/math], vertex [math]\displaystyle{ v_t }[/math] makes [math]\displaystyle{ k }[/math] connections by [math]\displaystyle{ k }[/math] iterations of the following steps:

1. Pick an existing node [math]\displaystyle{ v }[/math] uniformly at random from [math]\displaystyle{ \{ v_0, v_1, \ldots , v_{t-1} \} }[/math]
2. With probability [math]\displaystyle{ p }[/math] stay at [math]\displaystyle{ v }[/math]; with probability [math]\displaystyle{ 1 - p }[/math] take a 1-step walk to a random neighbor of [math]\displaystyle{ v }[/math]
3. Add an edge from [math]\displaystyle{ v_t }[/math] to the current node

For directed graphs, edges added are directed from [math]\displaystyle{ v_t }[/math] into the existing graph. Edges are undirected in respective undirected graphs.

2006

• (Blum et al., 2006) ⇒ Avrim Blum, T. H. Hubert Chan, and Mugizi Robert Rwebangira (2006). "A Random-Surfer Web-Graph Model". In: Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2006).
  • QUOTE: In this model, we are given parameters $k$ and $p$. At time $t$, vertex $v_t$ makes $k$ connections to the existing graph by repeating the following process $k$ times:

1. Pick an existing node $v$ uniformly at random from $\{v_0, \ldots , v_{t−1}\}$.

2. With probability $p$ stay at $v$; with probability $1 − p$ take a 1-step walk to a random neighbor of $v$.

3. Add an edge from $v_t$ to the current node.

In the directed version, the edges added are directed from $v_t$ into the existing graph. In the undirected version, edges are undirected.

To motivate our first model, note that if the connections to the existing graph are made uniformly at random, then we have an online version of the standard Erdos-Renyi graph model, and with high probability the maximum degree will be $O (log\; n)$. On the other hand, suppose we make each connection by first picking a random start node in the existing graph, and then taking a random walk of exactly one step. Then, in the directed case, this will just produce a star (all edges will point to the root $v_0$), and in the undirected case, it is not hard to show that there is a good chance this produces something star-like of maximum degree $\Omega (n).

However, if we flip a coin and with probability $p \in (0, 1)$ connect to the random start and with probability $1 - p$ take a 1-step walk, then we get something much more natural.

---