1
00:00:00,970 --> 00:00:04,730
So this brings us now to
the notion of spam farming, right?

2
00:00:04,730 --> 00:00:08,880
Where the idea is, what I kind of
alluded to where this t-shirt seller

3
00:00:08,880 --> 00:00:14,080
creates a fake set of web pages that
they all link to his own web page, and

4
00:00:14,080 --> 00:00:18,310
all these web pages in the anchor text
says that the target page is about movies.

5
00:00:18,310 --> 00:00:20,770
And this is what is known as spam farming.

6
00:00:20,770 --> 00:00:23,690
So, Google versus spammers, round two.

7
00:00:23,690 --> 00:00:27,915
So right, once the Google became
a dominant search engine, really spammers

8
00:00:27,915 --> 00:00:32,880
become, become trying to figure out ways
how to trick the Google search results.

9
00:00:32,880 --> 00:00:36,030
And what they did is they created
what is called spam farms,

10
00:00:36,030 --> 00:00:38,800
where basically the idea is that
you want to concentrate and

11
00:00:38,800 --> 00:00:43,360
collect the page link, and kind of
funnel it towards a single target page.

12
00:00:43,360 --> 00:00:48,180
And there are, there is many kinds of web
spam and many kinds of link, link spam.

13
00:00:48,180 --> 00:00:53,850
And in particular, you, many, many times I
am sure you have visited a webpage where,

14
00:00:53,850 --> 00:00:58,130
where you see, where you come and
see things like this, where,

15
00:00:58,130 --> 00:01:02,070
that basically just have a set of
hyperlinks to some other web page.

16
00:01:02,070 --> 00:01:05,850
And the idea is exactly as I mentioned,
that these pages basically funnel their

17
00:01:05,850 --> 00:01:10,740
page rank score importance to the,
to the high value target web pages.

18
00:01:10,740 --> 00:01:13,550
So the way we can think about this now,
is that we want to

19
00:01:13,550 --> 00:01:18,100
manipulate the structure of the, of the
web graph in order to create new links in

20
00:01:18,100 --> 00:01:22,580
such a way that given web pages
will get high importance.

21
00:01:22,580 --> 00:01:25,100
Conceptually, we can take the web and

22
00:01:25,100 --> 00:01:27,850
split the web into three
types of web pages.

23
00:01:27,850 --> 00:01:33,150
We can call we can call them these
classes based on the spammer's viewpoint.

24
00:01:33,150 --> 00:01:34,140
So for example,

25
00:01:34,140 --> 00:01:38,170
inaccessible web pages are basically
pages that the spammer cannot touch.

26
00:01:38,170 --> 00:01:42,460
So these are pages on the rest of
the web that spammer cannot touch.

27
00:01:42,460 --> 00:01:45,130
Then we have a notion of accessible pages.

28
00:01:45,130 --> 00:01:48,022
These are basically pages
that the spammer can touch.

29
00:01:48,022 --> 00:01:52,503
So for example,
spammer can add fake blog comments,

30
00:01:52,503 --> 00:01:57,724
spammer can add fake posts to,
to various types of pages.

31
00:01:57,724 --> 00:02:00,940
And all these posts would kind
of point to the target page.

32
00:02:00,940 --> 00:02:04,180
And of course,
the spammer has also its own set of pages.

33
00:02:04,180 --> 00:02:07,100
We call these the pages
the web spammer owns.

34
00:02:07,100 --> 00:02:10,590
And these are completely controlled
by the spammer and, you know,

35
00:02:10,590 --> 00:02:12,290
may spam multiple domain names.

36
00:02:12,290 --> 00:02:14,150
There may be millions of these pages,
and so on.

37
00:02:15,200 --> 00:02:17,560
So now the question is,
what can the spammer do?

38
00:02:18,816 --> 00:02:20,335
And the spammers' goal,

39
00:02:20,335 --> 00:02:24,640
right, is really to maximize the page
rank score of a given page t.

40
00:02:24,640 --> 00:02:28,640
Right, so there is this this t-shirt
selling webpage, let’s call it page t,

41
00:02:28,640 --> 00:02:32,310
that the web spammer wants to
improve its page rank score.

42
00:02:32,310 --> 00:02:35,000
So the technique the web
spammer will use is that it

43
00:02:35,000 --> 00:02:40,130
will get many links from accessible
pages pointing to the target page t.

44
00:02:40,130 --> 00:02:44,890
And this way, they will create what
is called a link farm, such that the,

45
00:02:44,890 --> 00:02:47,990
all the page rank importances for
these pages kind of

46
00:02:47,990 --> 00:02:52,050
funnel their importance back to the,
to our target page t.

47
00:02:53,700 --> 00:02:58,330
One possible strategy for
a link farm is created here.

48
00:02:58,330 --> 00:03:02,110
So basically this is a topology of how
a link farm may be organized, right?

49
00:03:02,110 --> 00:03:09,290
So the blue, the blue cloud shows
the inaccessible part of the web.

50
00:03:09,290 --> 00:03:12,200
Then, this inaccessible
part of the web has in and

51
00:03:12,200 --> 00:03:16,332
out links to and
from the accessible part of the web.

52
00:03:16,332 --> 00:03:19,750
What the web spammer can do, make,
make this accessible part of the web,

53
00:03:19,750 --> 00:03:23,410
as I said before, these are kind of blog,
blog posts and things like that.

54
00:03:23,410 --> 00:03:28,060
They can create comments that,
that link into the target webpage t.

55
00:03:28,060 --> 00:03:31,570
And then, what the web spammer can also
do, they can take these webpages that

56
00:03:31,570 --> 00:03:35,950
they own, and they can make all these web
pages both point to the target page t,

57
00:03:35,950 --> 00:03:39,330
and the target page t can
point back to these pages.

58
00:03:39,330 --> 00:03:43,300
And the idea is that there is,
the number of these pages is huge.

59
00:03:43,300 --> 00:03:45,050
We will call the number
of these pages to be m.

60
00:03:45,050 --> 00:03:47,940
And think of them as
millions of farm web pages,

61
00:03:47,940 --> 00:03:50,120
because they are very cheap to, to create.

62
00:03:50,120 --> 00:03:53,370
So now, this is actually
one of the most common and

63
00:03:53,370 --> 00:03:56,620
most effective link farm topologies.

64
00:03:56,620 --> 00:03:58,410
Now let's start to compute, and

65
00:03:58,410 --> 00:04:03,290
let's try to con, convince ourselves,
what is the PageRank score of Node D?

66
00:04:03,290 --> 00:04:07,490
So basically the page we want
to boost its PageRank score.

67
00:04:07,490 --> 00:04:09,730
So, to do this we will do the following.

68
00:04:09,730 --> 00:04:11,430
Let's, let's use the,

69
00:04:11,430 --> 00:04:16,680
the symbol x to denote the PageRank score
contributed by all the accessible pages,

70
00:04:17,710 --> 00:04:22,600
here denoted as blue node, and
how much PageRank they contribute to t.

71
00:04:22,600 --> 00:04:27,290
And let's use the Y to be the,
to be the PageRank score of node t.

72
00:04:27,290 --> 00:04:31,350
So now, first thing we want to compute is
what is the PageRank score of every of

73
00:04:31,350 --> 00:04:34,160
the farm pages that the web spammer owns?

74
00:04:34,160 --> 00:04:35,780
That is very easy to compute.

75
00:04:35,780 --> 00:04:38,990
We know what is the score of node t.

76
00:04:38,990 --> 00:04:42,490
And it is only the node t that
links to the, to the farm pages.

77
00:04:42,490 --> 00:04:45,060
So the node t takes its PageRank score y,

78
00:04:45,060 --> 00:04:50,500
divides it evenly among all the M
pages that are owned by the spammer.

79
00:04:50,500 --> 00:04:56,300
And gives them data fraction of,
of its PageRank score to each one of them.

80
00:04:56,300 --> 00:05:02,260
And then, of course, each of these
owned spam pages also receives

81
00:05:02,260 --> 00:05:05,290
a fraction of the score
due to the random jumps.

82
00:05:05,290 --> 00:05:08,160
The random jumps happen with
probability 1 minus beta, and

83
00:05:08,160 --> 00:05:12,620
there is N pages in total on the web,
so that is 1 minus beta over N.

84
00:05:12,620 --> 00:05:17,500
So now, given that we now know what is
the score of every web page that we own,

85
00:05:17,500 --> 00:05:19,200
this is denoted as the red nodes.

86
00:05:19,200 --> 00:05:21,697
Let's also compute what is the value of y.

87
00:05:21,697 --> 00:05:26,831
So the value of y, y is the page rank
score of node t, is simply x, which is

88
00:05:26,831 --> 00:05:32,580
the amount of page rank contributed by
the accessible pages, plus beta times M.

89
00:05:32,580 --> 00:05:36,110
And now the the pages the contribution of

90
00:05:36,110 --> 00:05:39,230
page rank scores from
the pages that we own.

91
00:05:39,230 --> 00:05:44,610
So this is beta times y
divided by M plus 1 minus

92
00:05:44,610 --> 00:05:50,170
beta plus N plus 1 minus
beta divided by N.

93
00:05:50,170 --> 00:05:54,550
Where M now is the number of
pages that the spammer owns and

94
00:05:54,550 --> 00:05:57,960
N is the number of pages
that are total on the web.

95
00:05:57,960 --> 00:05:59,060
Okay?

96
00:05:59,060 --> 00:06:05,890
So if you think about this and
multiply with beta M and solve the system.

97
00:06:05,890 --> 00:06:06,410
What we,

98
00:06:06,410 --> 00:06:12,670
what we get is that y equals x plus
beta squared y plus some constant terms.

99
00:06:12,670 --> 00:06:14,080
All right?
And what we will do,

100
00:06:14,080 --> 00:06:18,000
is we will take this last term
1 minus beta over N, this is

101
00:06:18,000 --> 00:06:22,960
very small because the web is huge, and
is large, so we will ignore this one.

102
00:06:22,960 --> 00:06:25,180
So let's keep looking at what we get.

103
00:06:25,180 --> 00:06:30,900
What we basically get, is we get something
that is like y equals x over 1 minus

104
00:06:30,900 --> 00:06:36,270
beta squared plus M divided by N,

105
00:06:36,270 --> 00:06:40,530
plus some constant, where this
constant is beta over beta plus 1.

106
00:06:40,530 --> 00:06:41,710
Okay?

107
00:06:41,710 --> 00:06:44,230
N is the number of pages
that the spammer owns, and

108
00:06:44,230 --> 00:06:47,530
N is the number of pages
that are on the web.

109
00:06:47,530 --> 00:06:52,050
So what this means is that the page
rank score of our target page t,

110
00:06:52,050 --> 00:06:56,220
equals basically the amount of page rank
score that comes from the accessible part

111
00:06:56,220 --> 00:07:00,920
of the web, plus the ratio of M
to N multiplied by some constant.

112
00:07:01,960 --> 00:07:02,810
So what does this mean?

113
00:07:02,810 --> 00:07:07,630
It's basically that the more web pages
the web spammer owns, the bigger the M,

114
00:07:07,630 --> 00:07:10,620
the higher the score of
the target page y will be.

115
00:07:10,620 --> 00:07:15,250
So, in some sense, spammer can create
arbitrary large number of pages.

116
00:07:15,250 --> 00:07:20,060
So M can be arbitrarily large,
which means that the page rank score of

117
00:07:20,060 --> 00:07:23,550
the target page t can also
get arbitrarily large.

118
00:07:23,550 --> 00:07:28,930
And of course in reality, N is huge,
right, the size of the web graph is huge.

119
00:07:28,930 --> 00:07:34,050
And M doesn't need to be that large
because all we need to do is we need to

120
00:07:34,050 --> 00:07:39,140
boost the, the score of the target page
t not to be the most important page

121
00:07:39,140 --> 00:07:42,840
on the web, but to be more important than,
than, some other pages on the web.

122
00:07:42,840 --> 00:07:48,930
So even not, not too big link farms
can already have a big effect, right?

123
00:07:48,930 --> 00:07:51,430
So, now this is basically the problem, and

124
00:07:51,430 --> 00:07:56,480
the question is, how do we now go and
detect such links, link farms on the web?