1
00:00:09,120 --> 00:00:09,667
Hello.

2
00:00:09,667 --> 00:00:12,175
We've been thinking about how
to measure the importance or

3
00:00:12,175 --> 00:00:14,190
the centrality of a node in a network.

4
00:00:14,190 --> 00:00:17,470
And today we're going to talk
about another way of doing this.

5
00:00:17,470 --> 00:00:21,378
It's called PageRank and it was developed
by the Google founders when they were

6
00:00:21,378 --> 00:00:24,179
thinking about how to measure
the importance of webpages

7
00:00:24,179 --> 00:00:26,709
using the hyperlink network
structure of the web.

8
00:00:26,709 --> 00:00:27,853
And the basic idea,

9
00:00:27,853 --> 00:00:31,971
is that PageRank will assign a score
of importance to every single node.

10
00:00:31,971 --> 00:00:35,629
And the assumption that it makes, is that
important nodes are those that have many

11
00:00:35,629 --> 00:00:38,291
in-links from important pages or
important other nodes.

12
00:00:40,090 --> 00:00:44,422
Now, Page Rank can be used on any type of
network, for example, the web or social

13
00:00:44,422 --> 00:00:48,648
networks, but it really works better for
networks that have directed edges.

14
00:00:48,648 --> 00:00:54,168
So, for example, a social network where
the edges indicate who emailed whom.

15
00:00:54,168 --> 00:00:56,483
And so, if we think about the definition,
what I said,

16
00:00:56,483 --> 00:00:59,984
that important pages are those that have
many in-links from more important pages,

17
00:00:59,984 --> 00:01:02,570
then there's a little bit of
a circular definition, right?

18
00:01:02,570 --> 00:01:07,010
Because if you imagine trying to measure
the PageRank of a particular node,

19
00:01:07,010 --> 00:01:08,920
let's say the first node
that you're looking at,

20
00:01:08,920 --> 00:01:12,290
then you would want to look at the
PageRank of the nodes that point to it.

21
00:01:12,290 --> 00:01:14,050
And you don't have those yet.

22
00:01:14,050 --> 00:01:16,760
So the ways it's defined
sounds a little bit circular.

23
00:01:16,760 --> 00:01:17,620
And in this video,

24
00:01:17,620 --> 00:01:21,540
we're going to walk through the process
of how you can actually compute it.

25
00:01:22,700 --> 00:01:27,180
So the setup is that we're going to
have a network with n nodes, and

26
00:01:27,180 --> 00:01:30,930
then we're going to compute
PageRank on a step by step fashion.

27
00:01:30,930 --> 00:01:34,069
And so, what's going to happen,
is that the sum of the PageRank or

28
00:01:34,069 --> 00:01:37,560
all the nodes is always going to be
constant, it's always going to be 1.

29
00:01:37,560 --> 00:01:42,701
And so at first, we're going to start with
every node having a PageRank value of 1/n.

30
00:01:42,701 --> 00:01:45,892
And then what we're going to do is
we're going to have every node give all

31
00:01:45,892 --> 00:01:48,325
of its PageRank to all the nodes
that it points to, and

32
00:01:48,325 --> 00:01:50,349
then were going to do this over and
over again.

33
00:01:51,580 --> 00:01:53,080
So, what we're going to
do is we're going to

34
00:01:53,080 --> 00:01:56,850
perform these
Basic PageRank Update Rule k times.

35
00:01:56,850 --> 00:01:59,272
And the Basic PageRank Update Rule
does what I just said.

36
00:01:59,272 --> 00:02:03,416
So every node will give an equal share
of its current PageRank to all the other

37
00:02:03,416 --> 00:02:04,731
nodes that it links to.

38
00:02:04,731 --> 00:02:08,865
And then, the new value of PageRank for
every node is going to be simply the sum

39
00:02:08,865 --> 00:02:12,760
of all the PageRank that are received
from all the nodes that point to it.

40
00:02:13,980 --> 00:02:16,240
So let's look at an example.

41
00:02:16,240 --> 00:02:18,690
Let's take, for example,
this network here that you see.

42
00:02:18,690 --> 00:02:21,720
And now take some time to think
about which one should be the most

43
00:02:21,720 --> 00:02:22,978
important node.

44
00:02:22,978 --> 00:02:24,340
And then we're going to compute PageRank,
and

45
00:02:24,340 --> 00:02:27,560
then you can see if your guess
matches with what PageRank would say.

46
00:02:28,770 --> 00:02:32,740
So, we're going to calculate PageRank for
every node after just 2 steps.

47
00:02:32,740 --> 00:02:35,560
I'm going to show you the calculations for
just 2 steps and then I'm going to

48
00:02:35,560 --> 00:02:38,820
show you what happens if you were to
perform even more steps on this network.

49
00:02:40,110 --> 00:02:43,850
So first, like I said, we're going to
assign every node a PageRank of 1/n.

50
00:02:43,850 --> 00:02:48,290
So in this case, every node will
have a PageRank value of 1/5.

51
00:02:48,290 --> 00:02:52,420
And now we're going to start applying
the Update Rule that I described.

52
00:02:52,420 --> 00:02:55,962
So we're going to have to keep track
of the old values of PageRank, and

53
00:02:55,962 --> 00:02:58,400
what the new value of
PageRank of each node is.

54
00:02:59,450 --> 00:03:00,890
Let's start with node A.

55
00:03:00,890 --> 00:03:04,876
Nodes D and E point to node A, so
A is going to get PageRank from D and E.

56
00:03:06,120 --> 00:03:09,170
Now let's think about how much
PageRank A is going to receive from

57
00:03:09,170 --> 00:03:10,050
each one of those two nodes.

58
00:03:11,380 --> 00:03:14,450
So if we look at D, D has three edges,

59
00:03:14,450 --> 00:03:17,640
that points to three different nodes,
C, A, and E.

60
00:03:17,640 --> 00:03:22,180
So A is going to receive 1/3 of
the current page rank that D has.

61
00:03:22,180 --> 00:03:25,514
D currently has 1/ 5 PageRank, and so

62
00:03:25,514 --> 00:03:30,327
A is going to get 1/3 of that
1/5 PageRank that D has.

63
00:03:30,327 --> 00:03:35,052
Now A is also going to get PageRank from
node E, and because E only points to A,

64
00:03:35,052 --> 00:03:38,355
then it's going to give all
of its PageRank to node A.

65
00:03:38,355 --> 00:03:42,327
And so A is going to get
1/5 PageRank from node E.

66
00:03:42,327 --> 00:03:47,009
And so, in total, A is going to get
4/15 PageRank from those two nodes.

67
00:03:47,009 --> 00:03:50,720
And so
the new value PageRank of node A is 4/15.

68
00:03:50,720 --> 00:03:52,500
Now, let's think of node B.

69
00:03:53,640 --> 00:03:55,860
B gets PageRank from node A.

70
00:03:56,880 --> 00:04:00,110
And A currently has 1/5 PageRank.

71
00:04:00,110 --> 00:04:03,775
Now, it's important here to note that
we've updated the PageRank of node A to be

72
00:04:03,775 --> 00:04:08,120
4/15, but when we do this computation,
we're always using the old values,

73
00:04:08,120 --> 00:04:14,240
not the updated values, so B is going
to get a PageRank of 1/5 from node A.

74
00:04:14,240 --> 00:04:19,100
And then B is also getting PageRank from
C, and so because C is only pointing to

75
00:04:19,100 --> 00:04:23,490
node B then it's also going to give all
of its PageRank to B which is 1/5 and

76
00:04:23,490 --> 00:04:27,475
so in total,
B is getting 2/5 PageRank from both nodes.

77
00:04:28,570 --> 00:04:30,600
Now let's look at node C.

78
00:04:30,600 --> 00:04:34,487
C is getting PageRank from D which,
again, is pointing to three nodes, and

79
00:04:34,487 --> 00:04:36,820
is giving 1/3 of its PageRank from node C.

80
00:04:36,820 --> 00:04:40,850
So C is getting 1/3 times 1/5 from D.

81
00:04:40,850 --> 00:04:43,350
And it's also getting
PageRank from node B.

82
00:04:43,350 --> 00:04:48,167
And because Bs pointing to two nodes,
B is going to give 1/2 of

83
00:04:48,167 --> 00:04:52,740
its PageRank to node C for
a PageRank of 1/2 times 1/5.

84
00:04:52,740 --> 00:04:56,070
And so, in total,
C is getting 5/30 or 1/6 PageRank.

85
00:04:57,680 --> 00:05:02,509
Now, node D is getting PageRank from B,
which again is given half of

86
00:05:02,509 --> 00:05:07,198
its PageRank to D and half to C so
D is getting 1/2 times 1/5.

87
00:05:07,198 --> 00:05:09,540
And that's the only node D
is getting PageRank from.

88
00:05:09,540 --> 00:05:12,580
So it's getting a total of 1/10 PageRank.

89
00:05:12,580 --> 00:05:15,855
And then E is getting
PageRank from D only.

90
00:05:15,855 --> 00:05:21,800
Which is 1/3 times 1/5, and
so in total is getting 1/15.

91
00:05:21,800 --> 00:05:25,800
So we've now computed the new PageRank
values of all the nodes, as so

92
00:05:25,800 --> 00:05:27,430
that's our first step, K equals 1.

93
00:05:27,430 --> 00:05:34,250
And so now those new values are going to
become our old values, and we're going to

94
00:05:34,250 --> 00:05:40,320
do this process again, now using
the values we got after the first step.

95
00:05:40,320 --> 00:05:46,394
We're going to do the exact same thing
again to get the second step of PageRank,

96
00:05:46,394 --> 00:05:47,432
k equals 2.

97
00:05:47,432 --> 00:05:48,905
So let's start with node A.

98
00:05:48,905 --> 00:05:52,710
A is getting PageRank from D,
1/3 of its PageRank.

99
00:05:52,710 --> 00:05:58,750
And D has 1/10 Page Rank, so
it's given a 1/3 times 1/10.

100
00:05:58,750 --> 00:06:00,810
And A is also getting PageRank from E,

101
00:06:00,810 --> 00:06:05,820
E is giving all its PageRank to A,
so it's getting 1/15 PageRank.

102
00:06:05,820 --> 00:06:10,860
And so A, in total, is getting 1/10 and
that's its new PageRank value.

103
00:06:10,860 --> 00:06:14,705
Now if we look at node B,
B is getting PageRank from node C.

104
00:06:14,705 --> 00:06:18,540
C points to only B, so
you want to give all of its PageRank to B.

105
00:06:18,540 --> 00:06:21,652
And it has 1/6, so B is getting 1/6.

106
00:06:21,652 --> 00:06:25,820
B is also getting PageRank from A, and A
is going to give all of its PageRank to B

107
00:06:25,820 --> 00:06:30,980
as well, so it's going to give all
of its current 4/15 PageRank to B.

108
00:06:30,980 --> 00:06:33,820
And, in total,
B is going to be getting 13/30.

109
00:06:34,920 --> 00:06:36,930
Now let's go look at node C.

110
00:06:36,930 --> 00:06:38,280
C is getting PageRank from D,

111
00:06:38,280 --> 00:06:42,130
which again is giving 1/3 of its PageRank
to each of the three nodes it points to.

112
00:06:42,130 --> 00:06:46,390
So C is getting 1/3 times times 1/10.

113
00:06:46,390 --> 00:06:49,610
And C is also getting
PageRank from node B.

114
00:06:49,610 --> 00:06:53,066
Which is given half of its PageRank to C,
so

115
00:06:53,066 --> 00:06:59,140
1/2 times its current PageRank
which is 2/5 for a total of 7/30.

116
00:06:59,140 --> 00:07:05,220
Node D is getting PageRank from B,
1/2 times 2/5.

117
00:07:05,220 --> 00:07:09,524
Finally E is going to be
getting PageRank from D only,

118
00:07:09,524 --> 00:07:14,032
which is 1/3 times 1/10 for
a total of 1/30.

119
00:07:14,032 --> 00:07:20,348
And so that's our new values of PageRank
for all those nodes after two steps.

120
00:07:20,348 --> 00:07:26,700
Now if we look at those values, we find
that node B has the highest PageRank so

121
00:07:26,700 --> 00:07:34,220
far after two steps of 0.43, followed
by node C, then node D, node A, and E.

122
00:07:34,220 --> 00:07:36,200
And so, up to this point,

123
00:07:36,200 --> 00:07:39,910
this is suggesting that B is the most
important node in this network.

124
00:07:41,530 --> 00:07:43,850
But what happens if we continue for
another step?

125
00:07:43,850 --> 00:07:47,719
Well here's the values that you
would get if you go to k equals 3.

126
00:07:47,719 --> 00:07:50,633
So you notice that the values
change a little bit, but so

127
00:07:50,633 --> 00:07:52,431
far you still have the same order.

128
00:07:52,431 --> 00:07:56,056
And B is still the most important node,
followed by C, followed by D,

129
00:07:56,056 --> 00:07:57,843
followed by A, and followed by E.

130
00:07:57,843 --> 00:08:01,424
As you may wonder what happens if I
just sort of continue doing this for

131
00:08:01,424 --> 00:08:03,050
k equals 4, 5, 6 and so on?

132
00:08:03,050 --> 00:08:04,866
How do I know when to stop, and

133
00:08:04,866 --> 00:08:09,254
how do I know when the actual values
that I should consider are, right?

134
00:08:09,254 --> 00:08:11,500
So what if we continue this process?

135
00:08:11,500 --> 00:08:16,040
Well, for this particular network, if you
continue doing this over and over and

136
00:08:16,040 --> 00:08:20,960
do it for many, many, many steps, it turns
out that eventually these values will

137
00:08:20,960 --> 00:08:25,050
start to change very little, so
they're converging to a unique value.

138
00:08:25,050 --> 00:08:28,080
And that unique value, in this case,
is the values that I'm showing.

139
00:08:28,080 --> 00:08:33,878
So B has a PageRank of 0.38,
C has a page rank of 0.25,

140
00:08:33,878 --> 00:08:37,934
and D 0.19, and A .12 and E .06.

141
00:08:37,934 --> 00:08:39,480
And actually, it turns out that for

142
00:08:39,480 --> 00:08:43,150
most networks, these PageRank
values will actually converge and

143
00:08:43,150 --> 00:08:46,910
that's the value that we think
of as the PageRank of the nodes.

144
00:08:46,910 --> 00:08:51,350
So, the PageRank of the node is the value
that you get after you do this process

145
00:08:51,350 --> 00:08:52,270
many, many, many times.

146
00:08:53,710 --> 00:08:57,000
So in summary, the steps of
Basic PageRank are the following.

147
00:08:57,000 --> 00:09:01,083
First, you start with all the nodes
with a PageRank value of 1/n.

148
00:09:01,083 --> 00:09:04,720
And then you perform these
Basic PageRank Update Rule k times.

149
00:09:04,720 --> 00:09:08,680
And this Update Rule said says that every
node is going to give an equal share of

150
00:09:08,680 --> 00:09:12,160
its current PageRank to all
the other nodes that it links to.

151
00:09:12,160 --> 00:09:15,760
And so the new PageRank value of every
node is going to be simply the sum of

152
00:09:15,760 --> 00:09:18,850
all the PageRank that it gets from
all the nodes that point to it.

153
00:09:20,260 --> 00:09:23,950
And for most networks, these PageRank
values will actually converge as

154
00:09:23,950 --> 00:09:26,450
k gets larger, as k goes to infinity.

155
00:09:26,450 --> 00:09:29,750
We're going to find that these
values converge to a unique value.

156
00:09:29,750 --> 00:09:32,834
And so
that's how you compute a basic PageRank.

157
00:09:32,834 --> 00:09:36,099
And that's all for this video,
and I will see you next time.