How does pageranking algorithm deal with webpage without outbound links?
algorithm, google-search, pagerank, search-engine
Solution
As page-rank is described in the original article, and in the wikipedia article, it is indeed not defined when `out-degree(v)=0` for some `v`, since you get `P(v,u)=d/n+(1-d)*0/0` - which is undefined
A node that has no outgoing edge is called a dangling node and there are basically 3 common ways to take care of them:
- Eliminate such nodes from the graph (and repeat the process iteratively until there are no dangling nodes.
- Consider those pages to link back to the pages that linked to them (i.e. - for each edge `(u,v)`, if `out-degree(v) = 0`, regard `(v,u)` as an edge).
- Link the dangling node to all pages (including itself usually), and effectively make the probability for random jump from this node 1.
About a page with no incoming node - that shouldn't be an issue because everything is perfectly defined. Such a node will have a page rank of exactly `d/n` - because you can only get to it by random surfing from any node - and that's the probability to be in it.
Hope that answered your question!
Problem
I am learning about the PageRanking algorithm so sorry for some newbie questions. I understand that the PR value is calculated for each page by the summation of incoming links to itself. Now I am bothered by a statement which stated that "the PageRank values sum to one " at wikipedia. As the example shown at wikipedia, if every page has a outbound link, then the summation of whole probabilities from each page should be one. However, if a page does not have any outbound link such as page A at the example, then the summation should not be value 1 right ? Thus, does Pagerank algorithm have to assume that every page has at least one outbound link ? Could someone elaborate more how Pageranking deal with pages without any incoming or outbound links ? How will the formulas change accordingly ? Thanks