Tuesday, 9 April 2013

Google PageRank Search

Google: "A page is good insofar as good pages link to it"
=> PageRank invented by Larry Page while a graduate Math student in Stanford University, under the supervision of Prof Tony Chan (now the President and Professor of Mathematics & Computer Science and Engineering of Hong Kong University of Science and Technology).

Below is a simplified 3 web pages of PageRanks x, y, z respectively.

x page receives link from z :
(x=z)

y page receives 1/2 link from x:
(y= 1/2 x)

z page receives 1/2 link from x and 1 link from y:
(z = 1/2 x + y)

All PageRank scores = 1 (Conservation Law of PageRank):
(x + y + z = 1)

Solve PageRank Simultaneous Equation:
x = z
y = 1/2 x
z = 1/2 x + y
x + y + z = 1

=> x = 2y = z
=> x = 2/5, y = 1/5, z = 2/5

Visually from below, you can see x and z pages have more links than y.

So the search result should return x,z pages in front of y page.

Using Linear Algebra to compute the eigenvalues and the eigenvectors of large matrix of billion variables, Google applies mathematics and the power of clustering 50,000 cheap CPU to search the Internet, making billion dollars.

Computers are powerful only when they are 'told' with great algorithm, which is based on Math. The other example is RSA Encryption with big prime number factorization.



20130409-164228.jpg

No comments:

Post a Comment