Page Rank

Question 1

What is pagerank:

Answer 1

Algorithm that ranks pages according to the number of links directing to the page.

Pages with more links pointing to it have higher authority.

Question 2

Hyperlink model inbounds

Answer 2

Suppose P(a) P(b) P(me)
My page rank = P(me) + BP(b) + YP(a)

B and Y weighted factor

P(me) inherits the page link portion of the pages directed to me )

Question 2

Hyperlink model

Answer 2

Suppose P(a) P(b) P(me)
My page rank =

Question 3

Outbounds

Answer 3

If a page has n outbound links the weight is split evenly by those N links

B = ½ if P(a) has 2 outbounds

Question 4

Sinkpage problem

Answer 4

When a page has links referencing it but does not reference any other links

Question 5

Sink page solution

Answer 5

The sinking page is weighted against the whole internet 1/N ( rank distributed over the internet)

Question 6

Cycle problem

Answer 6

Pages may be linked to a closed cycle causing and infinite increase of authority score.

Question 7

Cycle problem solution

Answer 7

Random surfer problem :
We have a damping factor d ( probability the surfer wills start a random session)

Pn + 1 = dH + (1 - d)

We iterate until the current probability of Pn is sufficiently close to the previous Pn

Pn = G^nP°

Question 8

Complexity

Answer 8

O(MN²)

Question 9

Example make the transition matrix of

C–>Bpage –> refences –> A page

Answer 9

A will have a transition matrix of [1(b) 0(c)]

Question 10

If transition matrix is all Zeros than that page is a sink page

Answer 10

So the zeros for that pages matrix are transformed to
1/N ( ex 1/3 )

Question 11

Calculate Google matrix with dampening factor 4/5

Answer 11

G = 4/5 * A + ( 1-4/5) *B