So we start talking about our first extension, or fix to the page rank.
And this is called Topic Specific PageRank.
Sometimes it is also known as Personalized PageRank.
So here is basic, basically the idea.
Let's think of, our initial goal.
Our initial goal was to identify important pages on the web graph.
Now of course we don't necessarily want to find pages that are generic in
popularity or that have generically high PageRank score.
But we would want to say what are the web pages that are popular within our
given topic or within a domain.
So in order to identify this our goal is the following, right?
What we would like to do is we would like to evaluate web pages,
not just according to their overall popularity but also how
close they are to our particular topic or particular set of topic web pages.
For example, how, what is their importance in terms of the sports topic or
what is their importance in terms of the history topic?
Right?
And what is, why, why is this interesting is because if we
think of the web search the way, the way PageRank was initially thought of was that
somebody will come ask our web search query.
We will go identify all the,
all the web pages that are relevant towards that web search query.
And then now we need to decide how to rank or
how to present all these web pages to the user.
We, we would basically take pages, simply sort them by their page rank score, and
show the pages that have the highest page rank score first to the user.
Now, of course, if you would have the personalized page rank or topic specific
page rank way of measuring importance of a page, we could say, we could basically
show to the user a given, a given ranking depending on what, what the user wants.
And in particular there, there can be many queries that are ambiguous.
For example quee, query Trojan could have very different
relevant pages depending on what is, what is the topic you are interested in.
In a sense that trojan can mean, Trojans could mean us, a sports team.
It can mean something different if you are interested in history.
Or if can mean something very different if you're interested in Internet security.
So the idea would be that we could want to compute different important scores
of different web pages based on their relation to a given topic.
So the question is how do we achieve this?
And the way we will achieve this is actually to do a small but
very clever trick to the PageRank formulation.
So let's think of what we have so far.
So far right we talked about basically the random walker with the very
small probability can teleport from one page to any other page in the way.
And we made this assumption that this teleportation.
Where the random walker will land.
They land uniformly at random at any other web page.
So what we can do now is change this random, random teleportation part a bit.
Right?
So in the original PageRank formulation we said that the random walker can land at
any page with equal probability.
What we do in the personalized PageRank world is we say we will, the random walker
can teleport only to a topic-specific set of relevant pages, alright?
So whenever a random walker decides to jump, they don't jump to any page on
the web, but it only, they only jump to a small subset of pages.
And this subset of pages is called the teleport set.
So the idea here is in some sense that we are biasing the random walk, right?
So the idea is that,
when the walker teleports, they can only teleport into a small set of pages.
We call it S as the teleport set, right?
And in our case,
we can think that set S contains only pages that are relevant to a given topic.
So what this will allows us to do is basically to measure the relevance of
of all the other webpages on the web with regard to this given set s.
Okay?
So in some sense for every set s or for every topic s for every teleport set.
We'll now be able to compute a different page rank vector,
R, that is specific to that teleport set.
so, the way we do this is actually everything is still the same as we do,
all we need to do is we need to change the formulation.
So everything still works.
The only thing we do is now we change the definition of our matrix A to be
to be the following.
If the entry i is not in the ma, in the teleport set s.
Then basically nothing happens.
Everything is, everything is okay.
Right? But if our entry i is in the teleport set
now the, now we add the teleport edges in a set.
Right? So we have the data times MIJ plus 1
minus beta.
All right, this is the random jump probability.
Divided by S.
Right? So with probability 1 minus data we jump
into one of the S pages so to,
the probability of jumping to one of them is 1 over the size of the teleport set.
Okay?
And everything still works, A is still stochastic.
Power iteration still works.
Our paging algorithm still works, everything is good.
Just our matrix A is now a bit different.
Of course, here for
example, we are assuming that when a ran, a random walker jumps into teleport set,
they jump uniformly at random into any of the pages in the teleport set.
We could make things even more interesting and
say that there is a probability distribution, or
every page has a different rate of the random walker landing at that given page.
The idea here is basically that we have lots and
lots of freedom in how do we set the teleport set S.
For example, when teleport set S is just a single node,
this is called a random walk with restarts.
And I will talk about this a bit more later.
But for now, all we need to,
we need to unders, do to understand the personalized PageRank, or
topic specific PageRank, is that we have these topic specific set of pages s.
These topic specific pages set of pages we somehow decide we
now compute the new version of matrix a where the random walks, can only jump or
teleport to the entries of s.
And basically the same machinery that we have developed, developed so
far applies in the, in the case of Topic-Specific PageRank.
To give you an example how this works, here is a simple graph, and
what we will do is here I am showing you first the transition probabilities,
and now let's suppose that our teleport set is a single node s.
And our beta is 0.8.
Okay?
So now given, given these values.
I, I updated the transition probabilities.
Right? So be,
because with probability 0.2 a random walker can jump out of every node.
And then can, they can only jump back to the node 1.
Right, so with probability .2, the node will land, the random walker will
land at node one, and, with the remaining probabilities we see the transitions.
And now if we were, if we were and run the power method and see where it converges
to, here are the page rank scores of the, of the nodes under this case.
What we see, for example, is that node one.
Because the highest PageRank score nodes three and
four also have a very high PageRank score.
Actually what I, what I will also show you now is that in this particular case
what I'm varying here for example is I'm keeping the parameter beta the same but
I'm varying the teleports set S right?
When teleport set S is all the nodes in the graph these
are the traditional pagering scores.
For example, you notice that as I am, as I'm decreasing the size and
of the teleport set and at the end the teleport set only contains of node one.
Notice how the PageRank score of node one and
the PageRank scores of all other nodes tend to tends to decrease.
Similarly for example, if I keep the page, the, the teleport set S constant but
I'm changing the random jump probability or the teleportation probability you see.
As the parameter beta gets smaller, the score of the first, the node one,
the first node, the node where the random walker is jumping to also starts,
starts to increase.
Because more and more often, the random walker jumps to node one.
So more and more often the random walker is at that given node.
So, one thing that I haven't told you yet,
is, how do we find a topic specific, Vector S?
All right. How do we find a set of
authoritative pages on a given topic?
Actually, what we can do is,
we can go back to the initial efforts of how to organize wed graph.
So, for example, DMOZ, or open directory, is, is human created set of web pages,
that are, that categorized into a 16 category top level hierarchy.
Right? So one idea is for
example is that we go and use the web pages that are,
classified into this hierarchy as the teleport set S for every given topic.
So for example the idea would be, would be now the following.
That for every webpage on the, on the web, we have a number of different
PageRank scores, one, with respect to a given, to a given topic.
So, for every page we would know what is its quality with respect to arts?
What is its quality with respect to business?
And so on.
So now, the question is as I mentioned before, how do we,
how do we use this in terms of web search, right?
So one way how we could use personalized page rank for
a web search would be the following.
Basically a user types in a query and picks a particular topic from the menu,
whether, or, whether they are interested in arts or
whether they are interested in sports, and then
what we can also do is we can classify a query into a given topic, and now.
Based on this, we can basically show,
pick a particular topic in a particular ranking with respect to to a given topic.
And this is how the whole methodology could be used in
earlier [INAUDIBLE] settings.