1
8.1kviews
Explain the role and effect of damping factor (teleportation) in PageRank computation.
1 Answer
2
925views
  • Page rank is a function that assigns a real number to each page in the web (or at least to that portion of the web that has been crawled and its links discovered)

  • The intent is that the higher the page rank of a page the more important it is.

  • Think that a web is a directed graph, where pages are the nodes and there is an arc form page p1 to page p2.

  • For e.g. Consider graph

enter image description here

  • The page rank for above graph for pages A, B and C can be calculated as R = M . r --------- (1)

Where M is transition matrix.

  • Above equation is valid when following conditions are met.

1. Graph is strongly connected.

2. There are no dead ends.

  • While calculating page rank there are two problems:

1. Dead ends

  • a page which do not have any link outside is called a dead end.

  • To get page rank dead ends are removed recursively and page rank is calculated.

2. spider Trap

  • it is a set of nodes with no dead ends but no Ares out.

  • They cause page rank calculations to place all the page rank within the spider traps.

  • To avoid this problem we modify calculation of page rank by allowing each random surfer a small probability of teleporting to a random page, rather than following an out link from their current page.

  • The equation (1) gets modified as :

S = B M r + ( 1 - $ \beta) e/n$

Where $\beta$ is damping or teleportal factor.

  • The value of $\beta$ is in the range 0.8 to 0.9

  • The term BMr represents the case where, with probability b, the random surfer decides to follow an out link from their present page.

  • The term $(1 - \beta) e/n$ is a vector. Here $(1-\beta)/n$ represents the introduction, with probability $(1-\beta)$ of a new random surfer at a random page.

  • The teleportation factor takes care of dead ends also by introducing the term $(1-\beta)/n$

  • Thus the sum of components in vector r will never reach to zero because of teleportation.

Please log in to add an answer.