Explain how to compute Page Rank for any web graph.

• Page Rank is a function that assigns a real number to each page in the Web. The intent is that the higher the Page Rank of a page, the more important it is.
• Think of the web as a directed graph where pages are the nodes and links between those pages as an edge of a graph, there is an arc from page p₁ to page p₂ if there are one or more links from p₁ to p_2.

Consider an example given below as a web with four pages (A, B, C, D). Page  A has links to each of other three pages, page B has links to A and D only, page C has a link only to A, and page D has links to B and C only.

Fig. A hypothetical example of the web

Suppose a random surfer starts at page A. There are links to B, C and D so this surfer will next be at each of those pages with probability 1/3, and has zero probability has zero probability of being at A. The random surfer at B has a probability of 1/2 of being at A or at D and zero at B and C.

    In general, we can define a transition matrix of the web to describe what happens to random surfer after one step. This matrix has 'n' row and columns if there are 'n' number of pages. The element m_ij in row i and column j has value 1/k if page j has k arcs out and one of them is to page i, otherwise m_ij = 0.
The transition matrix for the web is,

	0	1/2	1	0
	1/3	0	0	1/2
	1/3	0	0	1/2
	1/3	1/2	0	0

Suppose we start a random surfer at any of the 'n' pages of the web with equal probability. Then the initial vector V₀ will have 1/n for each component. If M is the transition matrix of the web, then after one step the distribution of the surfer will be Mv₀, after two step it will be M(Mv₀) = M² v₀, and so on. In general, multiplying the initial vector vo by M a total of i times will give us the distribution of the surfer after i steps.
    The probability x_i that a random surfer will be at node i at the next step is  ∑ j m_ijv_j . Here m_ijis a probability that a surfer at node j will move to node i at the next step and v_j is the probability that the surfer was at node j at the previous step.
    It is known that the distribution of the surfer approaches a limiting distribution v that satisfies, V = Mv, provided two conditions are met,

1. The graph is strongly connected, i.e, it is possible to get from any node to any other node.
2. There are no dead ends node that have no arcs out.