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.