So now, we will start talking about
how to combat the web spam, and
the method we will talk
about is called TrustRank.
So, as we mentioned before,
there are two types of web spam.
There is the term spam and
there is the link spam.
Term spam, you can think of it as it's
very similar to the email spam filtering.
All right.
Basically, it would like to identify what
are the terms, what are the words that
correspond to spam and for every webpage,
we would like to automatically say
whether it contains a set of those
words and filter out the webpage.
Combating link spam however, is, is more,
more, more expensive, or more tricky.
The idea here is basically that
we would want to detect or
blacklist a set of graph structures
on the web that look like spam farms.
In particular what is the problem
here is that kind of this links,
this leads to another war where
if we would have such a filter,
that would try to identify structures
that look like spams farms,
is that then spammers would
try to hide themselves.
And, we would have to update them back,
blacklist, and
everything would go back and forth.
So, we need a more universal solution.
So, the more universal
solution is called TrustRank.
And, in its basic idea, TrustRank is
simply a topic-specific PageRank with
a teleport set to a trusted set of pages.
Right?
So, when I say for
example trusted set of web pages,
this would be web pages to which,
to which we trust, and that are not
likely to be hacked or farmed.
So, for example, .edu domains.
Or, from non-US schools would be such a,
such a way to identify a good
set of trust web pages.
So, let's think about this a bit,
a bit more and see what is the idea.
So basically, the, the idea becau,
behind the TrustRank is this is
the notion of approximate isolation,
where the idea is that it's rare for
a good page to point to a bad page.
Right, it's very rare that a good
legitimate page would point to spam.
So, the idea is that we want to select
a set of seed pages from the web that we
trust that they are good.
And then, we would want to compute some
kind of similarity, or importance of
proximity of all the webpages on
the web to this, to this trusted set.
And now, if a,
some other webpage is legitimate,
then it will be close to
the trusted set of webpages.
Of course, what we are depending on
here is that we have some oracle,
right.Some human to identify good
trustworthy set of webpages.
And and of course,
that the idea is that web spam page
are not is this web, in this set.
Of course, this is a very expensive
task because a user would have to go, or
a human would have to go through,
and do this do these labors.
So, in some sense,
we want to make this set of seed
trusted webpages as small as possible.
So, the idea is the following.
What basically, we'll be doing is,
we are doing the trust propagation.
So basically, we have a subset of good
seed pages that we identify as good as,
we will call them trusted pages.
And then, we perform,
as I mentioned before,
topic-sensitive PageRank with
a teleport set to the trusted pages.
What this really means
is that now basically,
we are propagating trust
across the links of the graph.
Right?
And, the trust can
take value between zero and one,
the same way as the as the PageRank score.
So, one possible way to identify
spam would be the following.
We take the set of trusted web pages, we
compute the personalized or topic-specific
PageRank score with the teleport set
being the set of trusted web pages.
And now, what we do is we compute
the PageRank score of all,
every other page on the graph.
And, if the,
if the PageRank score of some page on the,
on the web graph is smaller
than some given threshold.
Then, we go and cut that page
away from the, from our data set.
And, we say that that corresponds to SPAM.
The problem with this method though,
is that basically we go and cut away all
the web pages that have low PageRank
scores with respect to the trusted set.
And now, of course,
some web page on the web can have a low
PageRank score because this web page
is new, and has just been born.
Or, this webpage can have a low tr,
PageRank score because it's spam.
So, the question is, can we,
why is this a good idea and maybe,
can we later improve on this idea?
So, let's first talk about why is this
idea of personalized PageRank score fr er,
from a given trusted set of webpages
a good idea to detect link spam.
So, first is,
notion is that we have this notion of
trust attenuation where
the degree of trust conferred by
a trusted page decreases with
the distance from that page in the graph.
Right?
So, kind of
farther away a given page is from the,
from the trusted set of pages, the lower,
the lower the trust it receives will be.
And, another important notion that also
works in our favor is the notion of
trust splitting.
Right?
Where the larger the number of
out-links from a page, the less scrutiny
a page author gives to each out-link.
In a sense, what this means is that,
if a page has lots of trust, but
then has lots of out-links,
then this trust kind of gets
split into these small chunks and
distributed over, over the target pages.
Right?
And,
this is exactly what is happening
in the topic specific PageRank,
with trust trusted set of
webpages being the teleport set.
So now, let's quickly discuss how do
we go in practice to pick a seed set.
Picking a seed set, we have kind
of two conflicting considerations.
In some sense, we would want to make
the seed set to be as small as possible.
Why as small as possible?
Because human labeling webpages are,
are trusted or not, is very expensive.
So, we want to use as little
of human time as possible.
On the other hand,
we would like in some sense,
to be the seed set to
be as big as possible.
Because we want to cover all
the good pages on the web.
So, in, in a sense ideally we would
like to put every non-spam page into our
seed set.
But, that would mean the seed set is,
is huge.
So, the question is, how do we balance
out these two kind of competing or
con, conflicting, goals?
The idea is the following, right?
For example, imagine that we want
to select the seed set of k pages.
One idea would be, for
example, that we pick the k pages on
the web according to the PageRank.
And, the hope is that this, the top,
small fraction of webpages pages on
the web are really the,
the truly import pages on the web.
And, we label those as the seed set.
Another, another idea that I briefly
mentioned before is that we use a set of
trusted domains whose menmership
is controlled by some
that are set organizations.
So, for example, .edu, .mil, or
.gov domains, these are the,
these are the domains that not
just everyone can, can register.
So, all the pages in these domains we
would trust them to be good pages and
that are not spammy and don't spam,
don't, don't point to other spammy pages.
So, one way to create a trusted
set of webpages would simply be to
take all the web pages of these domains.
What is also interesting now is
that we can actually take our
initial idea of identifying web spam and
extend it a bit.
And, we will extend it by creating
this notion of spam mass, right?
So, the idea is the following.
We will use the TrustRank as a model, and
start with a good, a set of good
trusted pages, and propagate the trust.
But now, we will flip our reasoning and
we will kind of view,
use two complimentary views.
Our goal will kind of be to ask,
what fraction of page's PageRank
comes from the spam pages?
Right?
So, what we would like to
do is not to ask how, what is your
proximity to the trusted part of the web,
but we would like to say what fraction or
estimate.
What fraction of page rank score of
a given page comes from the spam?
Right?
So, in practice we don't know
the answer to this question,
but we need to estimate it.
So, the way we can think about this
is the following we can think that we
have our webpage that we are interested
in here as our F circle.
We have a trusted set of webpages,
and we have the full web.
And, our goal is to estimate
what fraction of page rank
score of our red node here
comes from the spam pages.
So, what we can do is proceed as follows.
We can first go and compute r sub p,
where p is our red node,
where r sub p is simply
the PageRank of our node p.
And then,
we can also compute the r plus of p,
which is the page rank of the same node.
Where the teleport was done to
the trusted set of web pages.
Right?
And now, we can say that the spam mass
of a given web page is simply r p
minus r, r plus p.
What does this mean basically, is we say
we will compute the PageRank score of
a page using the simple PageRank
where the teleportation is uniform.
We will also compute the PageRank
score of a page where,
where we always travel from
the trusted set of webpages.
And now, with our webpage is, is really
spam, then this difference will be high.
Right?
Basically, there is a lot of other web
pages on the web that we don't trust that
reboost the importance of that page.
So, this way, we can come, we can define
the notion of a spam mass of a, of a page,
which is simply the ratio of the overall
PageRank score of the page and the,
the amount of spam mass that
that page will receives.
And, this way, we would, we could go and
all the pages that have this spam mass,
fraction high.
We would proclaim these pages as spam and
remove them from the, from our web corpus.
And, this idea is, is better than
the first solution to our problem.
Because here, the,
the question whether a, a page is spam or
not, does not depend on the absolute
value of its PageRank score.
But, kind of, it depends on the relative
value, when we compare how much Page Rank
score of a page comes from
the trusted part of the web.
And, how much of it's PageRank comes
from the un-trusted part of the web.
And, the ratio between these two
quantities is tell us how spammy
is a web page.