Exploration of the Google PageRank Algorithm

Re:Exploration of the Google PageRank Algorithm by wfunction on Thursday May 02, 2013 @04:43AM (#5643290)

This is way too complicated!

How about an easy explanation, one that a middle- or high-schooler who just learned to solve 3-equations and 3-variables and has seen probability can understand?

Let's say you have three websites: Reddit, Yahoo, and Google. Let's say Reddit links to Yahoo and Google, and Yahoo links to Google, and Google links to Reddit.

If you start on a random page and click randomly, what happens? You'll land on Reddit with probability x, Yahoo with probability y, and Google with probability z. Notice that if you continue clicking randomly, x, y, and z will stop changing after a while.

Okay, now stop clicking. How likely are you to have landed on page Google? (i.e., What's z?)

- You're on Reddit with probability x, and 1/2 of the links there will take you to Google.

- You're on Yahoo with probability y, and 1/1 of the links there will take you to Google.

- You're on Google with probability z, and 0/1 of the links there will take you to Google.

Therefore, z = x(1/2) + y(1/1) + z(0/1)

Similarly, x = x(0/2) + y(0/1) + z (1/1)

Similarly, y = x(1/2) + y(0/1) + z (0/1)

Since x + y + z = 1, we get: x = 2/5, y = 1/5, z = 2/5

What does that mean? It means Reddit and Google are twice as "important" as Yahoo, since you're twice as likely to land on them.

There, we just learned how PageRank works with zero linear algebra business.

[ Parent | on HN ]

Re:Exploration of the Google PageRank Algorithm by mullr on Thursday May 02, 2013 @05:29AM (#5643406)

Nonetheless, linear algebra is the way it's done for real applications. It's how the literature treats the subject as well, so it's important to understand. This tool helps for that goal, so I'm glad it's there.

[ Parent | on HN ]

Re:Exploration of the Google PageRank Algorithm by wfunction on Thursday May 02, 2013 @05:41AM (#5643433)

In a real application, you don't even know the transition probabilities to begin with, so actually performing the computation is the least of your worries -- the first problem is coming up with numbers, which wasn't mentioned. :)

So I feel that if the goal is to give a conceptual understanding, linear algebra is overkill. If the goal is to show how it's done in practice then this isn't terribly useful since it doesn't even show the tip of the iceberg!

[ Parent | on HN ]

Re:Exploration of the Google PageRank Algorithm by bflbfl on Thursday May 02, 2013 @08:19PM (#5648118)

Hey wfunction

I believe we know exactly what the matrix is, based on the hyperlink structure itself. It's updated and displayed on the vis here based on that, too.

btw, David Austin's article on PageRank is highly recommended : http://www.ams.org/samplings/feature-column/fcarc-pagerank

[ Parent | on HN ]

Re:Exploration of the Google PageRank Algorithm by mullr on Thursday May 02, 2013 @05:58AM (#5643486)

Fair enough. I'm thinking in particular of a paper I read that used pagerank for word sense disambiguation [1]. It's actually variant of pagerank, so the high level description in terms of probabilities (which I read several of) didn't take me very far. In order to come to grips with the technique I ended up actually implementing it and trying it on some toy datasets. This definitely would have helped me in that case.

[1] http://www.aclweb.org/anthology/E/E09/E09-1005.pdf It's interesting research, but it unfortunately turns out that even the best results in word sense disambiguation aren't good enough for a lot of applications. I wish I had 2 years to do nothing but play around in this field.

[ Parent | on HN ]