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 link
|
Pa ge
|
Has links to
pages
|
|
A
|
B, C
|
|
B
|
C, D, E
|
|
C
|
A,E
|
|
D
|
A, B, C, E
|
|
E
|
B, D
|
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 probabilty 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 weare 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.
Note: This process forms the basis for the PageRank algorithm used by Google.