A Web Search Engine Model - Suppose after we enter some keywords into our web search engine it finds five pages that contain those keywords. We will call these pages A, B, C, D, and E. The engine would like to rank the pages according to some measure of importance. To do so, we make note of which pages contain links to which other pages. Suppose we find the following links.

We then create a random walk where the initial state is equally likely to be any one of the five pages. At each time instant, the state changes with equal probability to one of the pages for which a link exists. For example, if we are currently in state A, then at the next time instant we will transition to either state B or state C with equal probability. If we are currently in state B, we will transition to state C, D, or E with equal probability, and so on. Draw a transition diagram and find the probability transition matrix for this Markov chain.

Transcribed Image Text:

Has links to Page pages B, C C, D, E A.E A, B, C, E B, D