1. Problem description

A page is considered important if other important pages link to it. The importance of a page is therefore determined by the importance of the other pages linking to it. If a personal web page is only referenced in the main page of a small laboratory, this will give it relatively little importance. If, on the other hand, a link to it is found from the French President's page, then it will acquire much greater importance. The definition of a page's importance is therefore implicit, and the line vector r ^T containing the PageRanks of all pages is the solution to a fixed-point problem, as we shall see.

Let deg(i) ≥ 0 be the output degree of page i, i.e. the total number of pages to which this page points. Let P = (p _ij ) be the transition matrix between page i and page j, where...