PageRank

This site has three textbooks: the basic programming course, “Mathematics, the Queen of the Sciences” and the algorithms catalogue you are reading. Together that is 202 pages and 1624 links between them. Which page is the most important, judging by links alone? Below each page is a circle whose size is its PageRank importance, and PageRank itself is computed before your eyes: step by step importance flows along the links until it stops changing. Move the d slider and watch where it drains.

At the usual d = 0.85 the top places go to chapters of “Mathematics, the Queen of the Sciences”: “Sequences and induction”, “Prime numbers”, “Root two and the real numbers”. Mathematics has 46.6% of all importance with 30% of the pages, the course 31.7%, and the catalogue 21.7%, although it has the most articles. Lower d to 0.5, and the catalogue’s articles come forward: “Binary search”, “Binary heap”, “Dijkstra’s algorithm”, and the shares almost even out. Move d towards one, and all importance drains into “Mathematics, the Queen of the Sciences”. At d = 0.99 it has 90%, at d = 1 everything.

The reason is visible in the links themselves. The catalogue links to both the course and “Mathematics, the Queen of the Sciences”, the course to “Mathematics, the Queen of the Sciences”, and it links to neither of them. Importance flows downstream along the links and never comes back. In graph terms “Mathematics, the Queen of the Sciences” is a strongly connected component with no way out, and at d = 1 it takes everything.

The idea

Imagine a reader endlessly wandering around the site. On each page, with probability d they click one of its links, chosen at random, and with probability 1 − d they get bored and open a random page out of all of them. If they wander long enough, the share of time spent on each page stops changing. This share is the page’s PageRank. The number d is called the damping factor, and its meaning is simple: between two jumps the reader follows on average d/(1 − d) links in a row; at d = 0.85 that is 5.7 links, at d = 0.5 one, at d = 0.99 ninety-nine. The larger d, the further the ranking sees.

The importance of a page is the sum of the importances of those linking to it, where each divides its importance equally among all its links, plus a small share that every page gets for nothing. To find such numbers, start with equal ones and repeat the handing out until the numbers stop changing.

As a formula: if page p is linked to by pages q with out(q) links each, and there are N pages in all, then

This is a system of N linear equations, and it could be solved even by Gaussian elimination. But for a graph of billions of pages Gauss is unthinkable, while repeating the handing out, the power method, costs one pass over the links per step. In the language of linear algebra PageRank is the eigenvector of the random reader’s transition matrix with eigenvalue 1, and the power method is multiplying a vector by this matrix again and again.

Switch the scene to “Random reader”. There the same PageRank is computed literally: the reader walks the links, a solid line is following a link, a dashed one a jump, and the size of a circle is the share of visits. The shares converge to the same numbers, but slowly: halving the error takes four times as many steps. The power method reduces the error at least 1/d times on every step.

Dead ends and traps

Why have jumps at all? Without them the definition breaks in two places. Here are six pages: F is a dead end with no links out; D and E link only to each other, a trap that can be entered and not left.

At d = 1 the importance of the dead end F is lost on every step, and after 60 steps 0.633 is left of the one, all of it in the trap D–E. If the dead end hands its importance out to everyone equally, the sum is preserved, but the trap still takes everything, and the numbers do not converge: D and E swap places on every step, 0.489 and 0.511. Jumps with probability 1 − d fix everything at once: from any page anywhere can be reached, neither a dead end nor a trap holds importance, and at d = 0.85 the numbers converge to one answer, where the trap has 0.709 and the dead end 0.061. Real data always has dead ends: in our graph five of the catalogue’s articles do not yet link to a single written article. Their importance is handed out to everyone equally, like a jump.

Why it converges, and to one answer

At d = 1 there is no contraction, and everything depends on the structure of the graph: the answer may not be unique, as with the trap, or may not converge at all, as D and E. Taher Haveliwala and Sepandar Kamvar sharpened the d^k bound in 2003: the second largest eigenvalue in absolute value of the Google matrix is at most d, and if the graph has at least two closed parts with no way out, it equals d.

Code

The importances are an array, the links lists of neighbours. One step: (1 − d)/N to everyone, then each page with links hands out d of its importance along the links, and the importance of dead ends accumulates and is handed out to everyone equally. It stops when the total change over a step is below 10⁻¹². Sums are taken by a plain loop, without sum(): that way the Python and Go output match to the last digit.

At d = 0.5 the shares of the three textbooks are 34.0, 33.4 and 32.6%, almost equal, and the catalogue’s articles lead: many neighbours link to “Binary search”, “Binary heap” and “Dijkstra’s algorithm”, and with frequent jumps that is what matters, who has more incoming links nearby. The larger d, the further the reader goes along chains of links, and the more it matters where those chains lead in the end. At d = 0.95 “Mathematics, the Queen of the Sciences” already has 67%, at 0.99, 90%.

What it costs

One step is O(V + E): each link is looked at once. The steps to accuracy ε are at most log(1/ε) / log(1/d). For ε = 10⁻¹² at d = 0.85 the bound promises 170 steps, and our graph needed 106; at d = 0.99, 2749 steps by the bound and 268 in practice. The bound is designed for the worst graph, ours converges faster, but the growth of the number of steps as d → 1 is visible here too: 34, 106, 189, 268. So d = 0.85 is a compromise: with a smaller d the ranking hardly takes distant links into account, with a larger one it takes longer to compute, and importance drains ever more into traps.

The memory is the graph itself and two arrays of importances. The graph of the web in 1998 no longer fitted in memory, and in the report of Page, Brin, Motwani and Winograd on PageRank, as university courses retell it, a database of 322 million links needed about 52 steps. Steps of the power method are easy to divide among machines, each handing out the importance of its part of the pages, so PageRank is a classic example for distributed graph processing systems.

Where it works

• Search. Google began with PageRank: in 1998 Brin and Page described a search engine that combined matching the words of a query with the importance of a page by its links. Today it is only one of many ranking signals. How search works as a whole, with an index and text ranking, is in the course chapter on the search engine.
• Recommendations. If jumps go not to any page but only to “one’s own”, the result is personalised PageRank: importance through the eyes of one reader. In 2013 Twitter described its “who to follow” service, where a user’s “circle of trust” was built by random walks from the user. This is the article’s problem.
• Texts. TextRank (2004) builds a graph of the words or sentences of a text, with edges for adjacency or similarity, and picks keywords and main sentences by PageRank.
• Science. The importance of journals by citations, where a citation from an influential journal weighs more, is computed by Eigenfactor in the same way.

History

The idea “important is whoever is linked to by the important” is older than the web. In 1953 the sociologist Leo Katz proposed a status index in social networks that takes all chains of acquaintance into account, with long ones weighing less: that is the damping factor, only for chains. In 1965 Charles Hubbell ranked people by the importance of those who support them, and in 1976 Gabriel Pinski and Francis Narin called a journal influential if influential journals cite it. In 1998 Sergey Brin and Larry Page described PageRank for the web, and Jon Kleinberg in the same years the HITS algorithm with two scores for each page: how authoritative it is and how well it gathers links to authoritative ones. More on Google itself and on the link farms used to try to fool PageRank is in the course chapter “The link farm”.

Problem

A reader has marked favourite pages: suggest what to read next. Personalised PageRank is needed, and one of the tests is this site’s graph.