An equally interesting question might be how we figure out what is the first word
that comes to mind. For example, what is the first word
starting with an a? Many of you might say apple.
Are some words more important than others. Is it just the common words which are more
important than others. In this context if you are talking about
this course in this lecture, what's the first word that comes to mind starting
with G. I bet many of you think Google.
Does this, have anything to do with how Google figures out?
Which topics to include, in the top ten documents in displays matching the query
Clinton plays in their carts. Importance of search results in google, as
many of you may have read, is because of an algorithm called pagerank which we will
describe in a minute. What we also want to ask is there anything
deeper? Which we will come to just, after that.
So let's look at page [inaudible]. The web consists of documents which are
linked to each other, through hyper-links. And this was the initial structure of the
web, in a way when it first became very popular in the late 90s.
And it remains so today, but we will come to, come to that shortly, as to how it
might be changing. So what Brandon Page at Google, the
founders of Google imagined while they must have stand for was suppose there was
a random surfer, who hops from page to page, hyperlink to hyperlink At random.
So at a page the surfer chooses at random any of the links that go out from that
page. So the surfer is going from page to page,
and the question that Sergie brings and every page asks was; what is the relative
probability of visiting a particular page? So of all the pages on the web, which
pages are more likely to visited by such a random surfer than others?
And that probability across all the pages on the web is the page rank of that page.
No. It might appear that the number of
hyperlinks going into a page. Is sufficient to compute its page rank.
Obviously if more links point to a page. More likely it is that this random circle
will reach there. Question is, is this enough?
It turns out that this is not enough. And the answer is null because.
Even if a page doesn't have many incoming links.
A surfer can revisit a page because of cycles in the graph, so that The surfer
will go and come back to the page through variety of different roots maybe
traversing the same link again and again but because there are so many cycles which
return back. To the same page.
A particular page can become important even if it doesn't have a lot of incoming
hyperlinks. The point is that page rank is a global
property of this web graph and cannot be computed simply by looking at the number
links of each page. This is the second major computation that
a search engine like Google has to do, computing the page rank of each page, the
first of course being indexing the web as it grows.
This page rank of each page is computed iteratively continuously and in parallel
on, as we shall see, thousands and thousands of servers.
For those of you who are slightly more mathematically minded.
The page rank is related to the eigenvector of a particular adjacency
matrix. But we're not going to go into that math
in this course.