Random Surfing Algorithm

From GM-RKB
(Redirected from random walker)
Jump to navigation Jump to search

A Random Surfing Algorithm is a Personalized Ranking Algorithm that is based on a random surfing model.



References

2021

  • (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Random_surfing_model Retrieved:2021-8-14.
    • The random surfing model is a graph model which describes the probability of a random user visiting a web page. The model attempts to predict the chance that a random internet surfer will arrive at a page by either clicking a link or by accessing the site directly, for example by directly entering the website's URL in the address bar. For this reason, an assumption is made that all users surfing the internet will eventually stop following links in favor of switching to another site completely. The model is similar to a Markov chain, where the chain's states are web pages the user lands on and transitions are equally probable links between these pages.

2008

1. add $v_{t+1}$ to the graph
2. pick $u$ uniformly at random from $v_1, \ldots, v_t$
3. with probability $p$ add the edge $\left(v_{t+1}, u\right)$ to the graph and stop
4. otherwise with probability $q$ replace $u$ by the unique vertex $u$ points to and repeat step 3
We see that $G_t$ will be a directed tree rooted at the first vertex, $v_1$, which we will refer to as the root.

For a directed graph the PageRank is defined as the stationary probability distribution of a random walk on the graph. The random walk follows the outgoing edges of the graph, but will restart itself every time with probability $1−c$, and start at a new vertex, chosen uniformly at random. The probability $c$ is called the decaying factor and influences the convergence of the computation of PageRank; (...)

2006