1
00:00:00,740 --> 00:00:03,800
So, today we will start
with with a new topic and

2
00:00:03,800 --> 00:00:06,810
we will start looking at
the Analysis of Large Graphs.

3
00:00:06,810 --> 00:00:10,756
And in particular, we will talk
about Link Analysis and PageRank.

4
00:00:10,756 --> 00:00:11,690
So here is the idea.

5
00:00:11,690 --> 00:00:15,380
So, so far,
this is how the class fits together and

6
00:00:15,380 --> 00:00:19,680
we are starting with a new topic with
a new set of data that is the Graph data.

7
00:00:19,680 --> 00:00:21,470
And in this module of the class.

8
00:00:21,470 --> 00:00:25,980
We will look at link analysis methods,
like PageRank and SimRank.

9
00:00:25,980 --> 00:00:28,160
We will look at Community Detection with,

10
00:00:28,160 --> 00:00:31,690
where the idea is that we want to find
clusters of nodes in the network.

11
00:00:31,690 --> 00:00:34,970
And then we will also look at
Spam Detection, where the idea is that we

12
00:00:34,970 --> 00:00:39,320
want to identify nodes that are spam,
spam nodes in the graph.

13
00:00:39,320 --> 00:00:42,970
So those are the three modules for
the Graph data section.

14
00:00:44,090 --> 00:00:47,280
If we think about graphs,
graph, graphs are everywhere.

15
00:00:47,280 --> 00:00:52,090
In a sense that for example,
social networks Facebook Twitter and

16
00:00:52,090 --> 00:00:52,850
things like that.

17
00:00:52,850 --> 00:00:55,420
Can very naturally be
represented as graphs.

18
00:00:55,420 --> 00:00:58,160
Graphs in a sense of as a set of nodes and

19
00:00:58,160 --> 00:01:02,570
a set of edges or connections or
intersections between them.

20
00:01:02,570 --> 00:01:06,560
Another set of data points that
also can be represented as

21
00:01:06,560 --> 00:01:09,060
graphs are social media networks.

22
00:01:09,060 --> 00:01:10,990
For example here, in this graph.

23
00:01:10,990 --> 00:01:14,940
What, what I'm showing you is is
an illustration of the structure of

24
00:01:14,940 --> 00:01:19,958
the United States blogosphere around
the Presidential Election in 2004.

25
00:01:19,958 --> 00:01:23,140
And what you see is basically
these two clumps in this network.

26
00:01:23,140 --> 00:01:27,020
These two communities and
they basically correspond to the two

27
00:01:27,020 --> 00:01:30,450
political parties in
the United States system.

28
00:01:30,450 --> 00:01:33,980
And you see how this class,
the nodes in one cluster then link

29
00:01:33,980 --> 00:01:37,430
into the other cluster and there is some
number of cross-linking between the two.

30
00:01:37,430 --> 00:01:40,227
So there is some amount of
polarization in a sense.

31
00:01:40,227 --> 00:01:43,360
Another word,
another set of data that can actually be

32
00:01:43,360 --> 00:01:46,900
represented as networks
are the networks of information.

33
00:01:46,900 --> 00:01:49,297
So for example, in this, in this case,

34
00:01:49,297 --> 00:01:51,841
what we are seeing here
is a map of science.

35
00:01:51,841 --> 00:01:57,690
So here every node is a, is a different
journal and or a different conference.

36
00:01:57,690 --> 00:02:02,130
And now the edges between these
journals are publication menus I mean,

37
00:02:02,130 --> 00:02:04,240
that one journal is
citing the other journal.

38
00:02:04,240 --> 00:02:07,390
So based on this citation
network between journals,

39
00:02:07,390 --> 00:02:10,782
we can basically visualize how
different disciplines of science and

40
00:02:10,782 --> 00:02:15,248
sub fields of science,
how they're relating to each other.

41
00:02:15,248 --> 00:02:19,766
Of course, internet is another case where
that can be studied as a, as a graph.

42
00:02:19,766 --> 00:02:23,360
So here, we have computers or
routers talking to each other.

43
00:02:23,360 --> 00:02:28,190
And again, this can be represented
as a dynamic network of nodes which

44
00:02:28,190 --> 00:02:30,800
represent computers or routers.

45
00:02:30,800 --> 00:02:35,930
And then let's say, physical links or
between, between these machines and

46
00:02:35,930 --> 00:02:37,940
those are the edges of the network.

47
00:02:37,940 --> 00:02:40,860
Of course, kind of the technological
networks are also the,

48
00:02:40,860 --> 00:02:43,240
the oldest example of graphs
people have been studying.

49
00:02:43,240 --> 00:02:49,080
So for example, the, the field of
graph theory goes, goes back to 1700s

50
00:02:49,080 --> 00:02:53,710
when Euler posed this problem about
the seven bridges of, of Konigsberg where

51
00:02:53,710 --> 00:03:00,010
the idea is that we want to cross at some
point and travel each bridge only once.

52
00:03:00,010 --> 00:03:02,320
And the question is can that be done?

53
00:03:02,320 --> 00:03:05,660
And this can be formulated as a,
as a graph problem.

54
00:03:05,660 --> 00:03:08,552
And examples of other
technological networks, for

55
00:03:08,552 --> 00:03:13,297
example are power grids, road networks
water distribution networks and so on.

56
00:03:13,297 --> 00:03:18,067
And it's, it's important for us to
understand the structure of these networks

57
00:03:18,067 --> 00:03:23,300
to detect failures to, to detect disease
outbreaks or contaminations and so on.

58
00:03:23,300 --> 00:03:28,290
Another example of a big part of
kind of networks is, is the web.

59
00:03:28,290 --> 00:03:29,400
Right.
So web itself,

60
00:03:29,400 --> 00:03:31,160
can be represented as a graph.

61
00:03:31,160 --> 00:03:32,200
And what we will do today,

62
00:03:32,200 --> 00:03:35,300
we will kind of focus on the structure
of the web graph and we will

63
00:03:35,300 --> 00:03:39,940
develop methods that allow us to learn
something about the, the pages on the web.

64
00:03:39,940 --> 00:03:43,464
So the first question is how do
we represent web as a graph?

65
00:03:43,464 --> 00:03:45,953
We will represent web as a directed graph.

66
00:03:45,953 --> 00:03:50,160
So we now will graph nodes will be,
will correspond to web pages.

67
00:03:50,160 --> 00:03:54,460
So every web page will be,
will be a node in this graph.

68
00:03:54,460 --> 00:03:57,610
And now we will have directed
links between these web pages that

69
00:03:57,610 --> 00:03:59,230
correspond to hyperlinks.

70
00:03:59,230 --> 00:04:01,230
Right?
So if I have my example here,

71
00:04:01,230 --> 00:04:03,660
I have a set of four web pages.

72
00:04:03,660 --> 00:04:06,120
And now these web pages
contain hyperlinks.

73
00:04:06,120 --> 00:04:08,120
So in this case, a particular,

74
00:04:08,120 --> 00:04:13,520
a particular webpage points to another,
another page via a hyperlink.

75
00:04:13,520 --> 00:04:17,690
So we can use now this hyperlink
relationships to create a network.

76
00:04:17,690 --> 00:04:19,400
All right.
So here is a small example,

77
00:04:19,400 --> 00:04:21,010
if I show you a bigger example.

78
00:04:21,010 --> 00:04:25,907
You could, think of the university
website as a big giant graph of

79
00:04:25,907 --> 00:04:31,534
web pages citing or referring to each
other via the use of hyperlinks.

80
00:04:31,534 --> 00:04:32,060
Right.
So we

81
00:04:32,060 --> 00:04:34,440
just represented the web as this network.

82
00:04:34,440 --> 00:04:36,089
The question is how is the web organized?

83
00:04:37,410 --> 00:04:41,690
The, the way people tried to
approach organizing the web was to

84
00:04:41,690 --> 00:04:44,861
human naturally created by humans.

85
00:04:44,861 --> 00:04:47,570
So for example, Yahoo back in 1996.

86
00:04:47,570 --> 00:04:51,720
Their original idea was to take
all the web pages on the web and

87
00:04:51,720 --> 00:04:55,100
manually categorize them
into a set of categories.

88
00:04:55,100 --> 00:04:58,830
So for example here,
I have a screen shot of the web page and

89
00:04:58,830 --> 00:05:01,680
you see that the top category was for
example arts.

90
00:05:01,680 --> 00:05:03,360
There was business.

91
00:05:03,360 --> 00:05:04,730
There was education.

92
00:05:04,730 --> 00:05:07,280
And each of these categories
had further subcategories.

93
00:05:07,280 --> 00:05:09,310
So the idea was to take every web page and

94
00:05:09,310 --> 00:05:12,160
categorize it into,
into this giant hierarchy.

95
00:05:12,160 --> 00:05:16,165
Of course, time showed that the web
was growing far, far to quickly so

96
00:05:16,165 --> 00:05:17,700
this, this did not scale.

97
00:05:17,700 --> 00:05:19,840
So the next way how to
organize the web and

98
00:05:19,840 --> 00:05:22,940
how to kind of find things on
the web is the web search.

99
00:05:22,940 --> 00:05:25,440
And this is what kind
of what we use today.

100
00:05:25,440 --> 00:05:29,010
And what is interesting in terms of
the web search is that there is lit,

101
00:05:29,010 --> 00:05:32,270
literature in particular the field
of information retrieval.

102
00:05:32,270 --> 00:05:37,720
That covers the problem of how do we find
a document in a large set of documents.

103
00:05:37,720 --> 00:05:39,330
Right?
So in our case of the web,

104
00:05:39,330 --> 00:05:42,110
we can think of every
web page as a document.

105
00:05:42,110 --> 00:05:46,160
The whole, the whole web is one
giant corpus of documents and

106
00:05:46,160 --> 00:05:50,800
our goal is to find a relevant document
to a given query in this huge set.

107
00:05:50,800 --> 00:05:55,520
However, traditionally the information
retrieval field was interested in finding

108
00:05:55,520 --> 00:06:00,450
these documents in relatively small,
small collections of trusted documents.

109
00:06:00,450 --> 00:06:06,750
So for example, like newspaper collections
or pap patent collections and so on.

110
00:06:06,750 --> 00:06:09,150
However, the web is very different.

111
00:06:09,150 --> 00:06:12,260
The, the difference is first,
that the web is huge.

112
00:06:12,260 --> 00:06:17,130
And the second thing is the web is full
of untrusted documents, random things,

113
00:06:17,130 --> 00:06:19,500
spam, unrelated things and so on.

114
00:06:19,500 --> 00:06:22,270
So the,
the big question on the web is which,

115
00:06:22,270 --> 00:06:24,380
which web pages on
the web should we trust?

116
00:06:24,380 --> 00:06:26,440
Which web pages are kind of legitimate?

117
00:06:26,440 --> 00:06:28,950
And which are,
which are fake and irrelevant?

118
00:06:28,950 --> 00:06:31,600
And this is what we will
be looking at today.

119
00:06:31,600 --> 00:06:36,330
Is how do we identify set of relevant or
trustworthy web page,

120
00:06:36,330 --> 00:06:39,300
web pages in this huge web graph.

121
00:06:39,300 --> 00:06:43,240
So, when you are doing the web search,
there are two that,

122
00:06:43,240 --> 00:06:44,580
that there are two challenges.

123
00:06:44,580 --> 00:06:45,210
Right?

124
00:06:45,210 --> 00:06:48,960
So as I mentioned, the first challenge
is who do we trust on the web?

125
00:06:48,960 --> 00:06:49,680
Right?

126
00:06:49,680 --> 00:06:53,700
How do we know which are, which web pages
are legitimate and which web pages are,

127
00:06:53,700 --> 00:06:57,160
for example, spam or
somehow fabricated on the web?

128
00:06:57,160 --> 00:07:00,740
The idea here is that we will use
the structure of the link web graph

129
00:07:00,740 --> 00:07:02,840
to understand these things.

130
00:07:02,840 --> 00:07:04,520
So the idea is kind of that trust,

131
00:07:04,520 --> 00:07:07,000
trustworthy web pages
will link to each other.

132
00:07:07,000 --> 00:07:10,140
And we will build on this idea
to exploit it to be able to

133
00:07:10,140 --> 00:07:12,910
identify the page rank algorithm.

134
00:07:12,910 --> 00:07:16,250
And then, the other problem
that happens on the web is that

135
00:07:16,250 --> 00:07:18,870
sometimes queries can be rather ambiguous.

136
00:07:18,870 --> 00:07:23,190
For example, you can ask, what is
the best answer to a query newspaper?

137
00:07:23,190 --> 00:07:27,050
And there is really kind of no,
no good answer to this query.

138
00:07:27,050 --> 00:07:28,110
And the, the, the,

139
00:07:28,110 --> 00:07:31,570
goal here if you want to identify
all the good newspapers on the web.

140
00:07:31,570 --> 00:07:36,060
Is to again, look at the,
at the web structure of the of,

141
00:07:36,060 --> 00:07:40,640
of the structure of the web graph in order
to identify the we, the set of pages.

142
00:07:40,640 --> 00:07:43,360
Or a set of newspapers that
are linking to each other.

143
00:07:43,360 --> 00:07:47,140
And again, get, get the result out
of the structure of the web graph.

144
00:07:47,140 --> 00:07:50,770
So these are the two challenges we
will address in today's lecture.

145
00:07:52,040 --> 00:07:56,080
The way we can address both of these
challenges is to basically realize that

146
00:07:56,080 --> 00:07:59,200
the web as a graph has
very reach structure.

147
00:07:59,200 --> 00:08:02,710
So one thing that we can do is we
can try to think of this problem

148
00:08:02,710 --> 00:08:06,810
abstractly as a way to rank
nodes of forbidden graph.

149
00:08:06,810 --> 00:08:09,410
So basically,
we would like to compute a score or

150
00:08:09,410 --> 00:08:13,120
an importance score of every
node in this web graph.

151
00:08:13,120 --> 00:08:16,500
And the idea is that some nodes
will collect lots of links, so

152
00:08:16,500 --> 00:08:18,400
they will have high importance and

153
00:08:18,400 --> 00:08:23,200
some other nodes will have a small number
of links or links from untrusted sources.

154
00:08:23,200 --> 00:08:25,190
So they will have low importance.

155
00:08:25,190 --> 00:08:28,724
So that's the,
that's the thing we want to compute.

156
00:08:28,724 --> 00:08:33,690
So, in order to compute the importances
of the nodes in a graph.

157
00:08:33,690 --> 00:08:35,395
There are several approaches to this.

158
00:08:35,395 --> 00:08:38,530
Broadly, these approaches
are called link analysis.

159
00:08:38,530 --> 00:08:41,310
Because you're analyzing
the links on the web graph to in,

160
00:08:41,310 --> 00:08:44,400
to compute an important
score of a node in a graph.

161
00:08:44,400 --> 00:08:48,060
So the b, the first approach we will
look at, it's called Page Rank.

162
00:08:48,060 --> 00:08:52,180
And this is really the algorithm that was,
that was invented in that

163
00:08:52,180 --> 00:08:56,050
behind the initial implementation
of the Google Search engine.

164
00:08:56,050 --> 00:08:58,990
Then we will take a look at
also at another algorithm that

165
00:08:58,990 --> 00:09:00,480
is called Hubs and Authorities.

166
00:09:00,480 --> 00:09:03,390
Here the idea is that we
have two types of web pages.

167
00:09:03,390 --> 00:09:06,300
In our web graph, we have the web
pages that are called Hubs.

168
00:09:06,300 --> 00:09:08,800
And we have web pages that
are kind of called Authorities.

169
00:09:08,800 --> 00:09:11,270
That are good authorities for
given topics.

170
00:09:11,270 --> 00:09:14,430
And then, we will look at some
extensions of these algorithms.

171
00:09:14,430 --> 00:09:19,680
First, in terms of topic-specific or what
is also called as Personalized Page Rank.

172
00:09:20,830 --> 00:09:26,270
And we will also use these ideas and
apply them to web spam, spam detection.

173
00:09:26,270 --> 00:09:29,530
Where basically spammers may want
to manipulate the structure of

174
00:09:29,530 --> 00:09:33,630
the web graph in such a way to,
to make some web pages to,

175
00:09:33,630 --> 00:09:35,750
to seem important even
though they are not.

176
00:09:35,750 --> 00:09:38,500
So basically,
boost importance of some of the web pages.