More Curiosities with Google PageRank and "Distant" Links

This is a continuation of my experiments with the PageRank algorithm for small network systems.  The figures below are from the Google PageRank explorer web app, which is here:

https://googledrive.com/host/0B2GQktu-wcTiaWw5OFVqT1k3bDA/

The figures show the surprising impact of adding a single link to the system.  Page H - and even pages C, D, and E - have their PageRank cut by about 30%, with this being taken up by pages I and J.  And the only change is that there is a link added from page I to page J.  And, even though we add a hyperlink out of page I, its PageRank goes up.

Adding Just One Hyperlink to the System - from I to J - Has an Impact on the "Distant" H, and increases the PageRank for I 

Why would the PageRank for page I go up when we add a hyperlink out of it?  This is because prior to adding the link, page I has no outlinks - it is a "dangling node" - and so it is forced to send an equal amount to every page in the system (the webapp above shows the details on all of the matrices involved).  When it has the link to page J in the bottom network, it sends much less to the rest of the cells in the system, as it sends stuff mostly to page J, which in turn is passing it right back to I.  In conjunction with this is the fact that there is a only constant amount of PageRank to go around, and so if one page is getting more, then this is reducing PageRank for other pages.  Results can certainly be counterintuitive at first glance.  And, in thinking about it, the very smallness of these networks may lead to results not seen when there are billions of pages.  Only Google knows for sure.

Please feel free to let me know if you find otherwise with the examples above.

Exploring Convergence of the PageRank Algorithm

As part of learning more about the PageRank algorithm, I created a web app that lets you add/remove nodes and links, and see how this might impact the calculated PageRank values for small web systems. I have now also added the ability to watch how the power method converges (or not) to the PageRank vector for a web system.  You can step forward or backward in the iteration process, as "stuff" moves amongst the pages each step.  This can be particularly interesting in cases where the method does not converge, as you can (usually) see the stuff cycling through the system.

You can play with it here: https://googledrive.com/host/0B2GQktu-wcTiaWw5OFVqT1k3bDA/

You click the "Explore Convergence" button to explore the convergence, and click the "Hide Convergence" button to return back to "normal mode".

Click the "Explore Convergence" button over there on the right to watch how the power method converges (or doesn't converge, if that be the case).

Once the "Explore Convergence" button is clicked, a few extra things related to the power method are shown on the screen near the top.  Clicking the "Hide Convergence" button will hide this extra stuff, and show the final result of the iteration method once again.

By using the left/right arrows anywhere on the page (or by using the slider), you can step forward or backward through the power iteration method.

One thing that might stand out to you is how stuff will get sent to apparently "disconnected" pages as the method progresses.  This is because - unless the damping factor is one - the PageRank algorithm forces every page to be connected to every other page in the web, although the "pipes" between the pages are very small.

Exploring Google PageRank - the Impact of "Distant" Links

This the second little note about playing with the Google PageRank algorithm using this little work-in-progress web app.  The results below should be reproducible with it (or let me know if it's not!).

Note that it has been stated that PageRank is now one of over a hundred factors used to rank pages, so it is unclear how much this matters for Google's rankings today.

Here's the before - the sizes of the circles correspond to the calculated PageRank (damping factor 1, but that doesn't seem to affect the results in this case):

A Little Web - Sizes Correspond to Calculated PageRank

The ranking is A=H=E>D>B>C=F, with values 0.25,0.25,0.25,0.13,0.12,0,0, respectively.

Now, see what happens to when we connect A to F:

A Little Web - One Page Adds a Single Link and It Has an Impact on PageRank

All we did was connect A to F, and yet the impact is surprising.  The ranking is now A>B>C=E=F=F>D, with values 0.25,0.19,0.13,0.13,0.13,0.13,0.6, respectively.

What struck me when playing with this was the impact on page D.  It is not directly connected to A at all, and yet its PageRank gets cut in half (from 0.13 to 0.06) and moves from 4th to last, all because of something that happened somewhere else.  The impact of a "distant" small but abrupt change that, even in the case of a tiny network, is difficult to predict.  And what about a network of 42 billion pages?

This Miyoko Shida Rigolo performance seems relevant yet again.

Google PageRank - Evaluating Simple Networks

I have been playing with the calculated PageRank for simple systems using the little web app I put together the other day.  This is partly to continue improving my understanding of the PageRank algorithm, but also to root out any issues with the implementation itself.

I was looking at one system and was concerned that the calculated solution was wrong.  This is because the end result was (and is) counter-intuitive.

Here is the basic little network:

A "Simple" Network - Is It Obvious to You Why "C" should have a higher PageRank than "D"?

The circles correspond to web pages, and the links correspond to hyperlinks.  Here's the Google Matrix when the damping factor is one (this simplifies the numbers, but note that the ranking itself seems to be the same if you use a smaller damping factor):

Google Matrix for System Above when Damping Factor is One

If we denote the entries of the PageRank vector x by [x_A, x_B, x_C, x_D, x_E], then based on the Google Matrix G above, the fact that the PageRank vector must satisfy x = Gx means that we should have

• x_A = (x_C + x_D)/2
• x_B = (x_D + x_E)/2
• x_C = x_B
• x_D = x_E/2
• x_E = x_A + x_C/2

Here's the calculated PageRank (scaled so that the values are integers):

• A: 15
• B: 18
• C: 18
• D: 12
• E: 24

This is all just arithmetic, written out here as part of confirming the answer once again.

The bigger issue to me is how to explain the result in any kind of simple or intuitive manner.  Could you have predicted that Page D would have a PageRank less than page C, especially if I told you that E was going to have a higher PageRank than B?  Page D seems to get ALL of Page E's PageRank, which has the most PageRank of any of the pages.  Page C gets all of B's PageRank, but Page B has less than Page E.  The results are not intuitive.

And this is only a web of five pages.  What does this say about trying to reliably predict the impact of adding/removing links when there are 42 billion nodes.  Where, if each page is represented by a standard marble, the array of marbles would not just stretch to 70% of the distance to the moon - which is the case when each column takes up about a quarter inch on your screen - but past it?   Where the removal of a single link somewhere might tilt equilibrium and shift page rankings worth billions of dollars.  This amazing performance by Miyoki Shida Rigolo comes to mind:

The Impact of Little Things in a Connected World

This being a bit overly dramatic, I realize.  And I understand that PageRank (or rather, its evolved form internal to Google) is only one of many factors used in determining the rankings.  Nevertheless, I still have experimentation and reading-up to do on this area in search of the "explanation for a five-year-old".

Please feel free to let me know what you find as well.  Perhaps something obvious is being overlooked here.

Exploring Google's PageRank

I recently started looking at Google's PageRank, and as part of trying to understand it a little better I made a simple web app to see how PageRank depends on the damping factor, links, etc.  The actual implementation includes the breaking out of the "dangling nodes matrix" as discussed in  Dave Austin's nice article on PageRank.

The web app is on googledrive here.

With this you can

• create custom web system systems, and see how the PageRank of pages is affected by adding/removing links or other pages
• see exactly what the underlying matrices are used in the calculation of PageRank, and how they are related to the web system
• step through the iterations of the power method in the estimation of PageRank

The work-in-progress app is built using:

• D3's force directed layout and general associated svg-helper stuff 
• A slightly modified version of Ross Kirsling's D3 directed graph editor
• James Coglan's Sylvester vector/math Javascript library, which nicely deals with lots of drudgery

A simple tool to play with Google's PageRank - Add/Delete Pages or Links,  or Explore Convergence of the Power Method

One of the main goals of this project is to show the actual intermediate matrices used in the calculations  so as to try to maintain the connection(s) with the starting web structure as long as possible.  These matrices are updated dynamically as you modify the graph or the damping factor (in addition to the PageRank calculations themselves, of course). 

Per usual, power iteration is used to estimate the PageRank vector. For the most part, it seems to converge in a handful of iterations, and sufficiently fast enough to allow updating for any change of the slider that controls the damping factor.  I have seen a few cases where, with the damping factor set at 1.0, it did not converge within 20,000 iterations.  As pointed out in Austin's note (with some examples), the power method can fail to to converge in this case if the resulting Google matrix is not "regular" (some power of the matrix has all positive entries).

I knew things were big in real life, but one thing that caught my attention was the magnitude of the size of the actual Google matrix for the web.  For example, if its full contents were to be written on the screen, where each column gets about a quarter of an inch, then since there are about 42 billion web pages considered (assuming that the worldwidewebsize.com value for Google is approximately correct), your screen would need to be about 166,000 miles wide and tall... it would extend nearly 70% of the way to the moon.  Even if each column was reduced to the size of a pixel on an iPad retina display (264 ppi), the screen would still need to be about 2500 miles wide and tall.  Of course, the excessive sparsity of the underlying matrices is exploited when performing calculations.