1
00:00:09,028 --> 00:00:13,220
Hello, last time, we talked about PageRank
and how to compute it on a network.

2
00:00:13,220 --> 00:00:16,580
And today, we're going to talk
about how to interpret it and

3
00:00:16,580 --> 00:00:20,010
identify a potential problem
that it has and also a solution.

4
00:00:21,130 --> 00:00:25,581
So first of all, the PageRank value of
a node after k steps can be interpreted as

5
00:00:25,581 --> 00:00:30,390
the probability that a random walker lands
on that node after taking k random steps.

6
00:00:30,390 --> 00:00:36,000
And so having said that,
let me tell you what a random walk is.

7
00:00:36,000 --> 00:00:38,120
Let's think about
a random walk of k steps.

8
00:00:38,120 --> 00:00:41,830
The way it works is that you would start
on a random node, and then you're going to

9
00:00:41,830 --> 00:00:46,300
choose outgoing edges at random, and
follow those edges to the next node.

10
00:00:46,300 --> 00:00:48,630
And then you're going
to repeat this k times.

11
00:00:48,630 --> 00:00:52,790
So, for example, let's take a random
walk of five steps in this graph.

12
00:00:52,790 --> 00:00:55,916
So first, you would choose some random
node, let's say you chose node D.

13
00:00:55,916 --> 00:01:01,740
And now, you're going to choose one
random edge going from D to another node.

14
00:01:01,740 --> 00:01:03,660
So there are three options here.

15
00:01:03,660 --> 00:01:06,900
Let's say you chose
the one going to node A.

16
00:01:06,900 --> 00:01:10,834
So then, for your first step,
you're going to walk from D to A.

17
00:01:10,834 --> 00:01:13,858
And then you are going to
repeat this four more times.

18
00:01:13,858 --> 00:01:17,252
So you're going to choose a random
edge going out from A, in this case,

19
00:01:17,252 --> 00:01:18,410
there are no options.

20
00:01:18,410 --> 00:01:21,660
The only one you can choose is the one
going to B, so you follow it and

21
00:01:21,660 --> 00:01:23,030
you go to node B.

22
00:01:23,030 --> 00:01:24,550
And then you choose again a random edge,
and

23
00:01:24,550 --> 00:01:27,530
there are two options,
either go to C or go to D.

24
00:01:27,530 --> 00:01:30,350
Let's say you go to C, that's your Step 3.

25
00:01:30,350 --> 00:01:32,470
Then out of C, there's only one edge,

26
00:01:32,470 --> 00:01:36,540
you have to go back to B so
you go back to B, that's Step 4.

27
00:01:36,540 --> 00:01:40,856
And then we're back at B, you choose
again randomly between going to C and D.

28
00:01:40,856 --> 00:01:43,042
You may go to C again or
maybe you go to D.

29
00:01:43,042 --> 00:01:46,190
In this case, you went to D,
and that's your fifth step.

30
00:01:46,190 --> 00:01:47,060
So that's a random walk.

31
00:01:47,060 --> 00:01:49,760
You simply randomly choose edges and
walk along in the network.

32
00:01:51,088 --> 00:01:55,550
And so in thinking about this
interpretation of PageRank that says that

33
00:01:55,550 --> 00:01:58,700
the value of PageRank of
each node is the probability

34
00:01:58,700 --> 00:02:02,220
that you would land on
that node after k steps.

35
00:02:02,220 --> 00:02:04,752
Well, we computed the PageRank values for
this network.

36
00:02:04,752 --> 00:02:09,717
And I told you that if you repeat this for
a lot of steps, say k equals infinity.

37
00:02:09,717 --> 00:02:12,591
These are the values that
you can eventually approach,

38
00:02:12,591 --> 00:02:14,864
these are the values
that you converges to.

39
00:02:14,864 --> 00:02:17,916
So here, B had the highest
value of PageRank of .38.

40
00:02:17,916 --> 00:02:22,699
And you can interpret this value of .38
as the probability that are random walk

41
00:02:22,699 --> 00:02:26,230
after taking many, many,
many steps would land on node B.

42
00:02:27,700 --> 00:02:29,870
Here's why this interpretation is useful.

43
00:02:29,870 --> 00:02:31,880
Well, we have this network
that we've been looking at.

44
00:02:31,880 --> 00:02:34,230
Let me make a small
change to this network.

45
00:02:34,230 --> 00:02:38,940
I'm going to add these two nodes, F and
G, where B points to both of those nodes,

46
00:02:38,940 --> 00:02:40,520
and then they point to each other.

47
00:02:41,640 --> 00:02:44,089
I want you to look at this network and
try and

48
00:02:44,089 --> 00:02:48,736
figure out what the PageRank of each node
is after taking a lot of PageRank steps.

49
00:02:48,736 --> 00:02:49,670
So, 4k very large.

50
00:02:50,690 --> 00:02:53,930
I claimed that you should be able to
figure this out without doing any type

51
00:02:53,930 --> 00:02:54,770
of computation,

52
00:02:54,770 --> 00:02:58,640
just by thinking about the interpretation
of PageRank as a random walk.

53
00:02:58,640 --> 00:02:59,650
So take some time to do that.

54
00:03:03,958 --> 00:03:07,594
So you should have figured out that for
large enough k, F and

55
00:03:07,594 --> 00:03:10,890
G are going to have a PageRank
value of about one half.

56
00:03:10,890 --> 00:03:14,350
And all the other nodes are going
to have a PageRank value of 0.

57
00:03:14,350 --> 00:03:15,820
So, why is that?

58
00:03:15,820 --> 00:03:18,190
Well, imagine a random
walk on this network.

59
00:03:18,190 --> 00:03:22,880
Whenever the random walk lands on F or G,
which will happen eventually if you walk

60
00:03:22,880 --> 00:03:26,060
long enough on this network,
then they're going to stock on F and

61
00:03:26,060 --> 00:03:28,790
G because there are no edges to go to,
right?

62
00:03:28,790 --> 00:03:31,282
So if you're in G,
the only place you have to go is F.

63
00:03:31,282 --> 00:03:34,310
And if you are in F,
the only place you have to go to is G.

64
00:03:34,310 --> 00:03:38,670
So, there's no way to get back from G and
F to any of the other notes.

65
00:03:38,670 --> 00:03:42,643
And so all the other nodes, a probability
that you land on one of them after taking

66
00:03:42,643 --> 00:03:44,990
a very,
very long random walk is going to be 0.

67
00:03:44,990 --> 00:03:48,220
And the probability of
landing on either F or

68
00:03:48,220 --> 00:03:52,946
G after a very long random walk is
going to be about half for each.

69
00:03:52,946 --> 00:03:54,370
And so this seems like a problem, right?

70
00:03:54,370 --> 00:03:59,030
Because while it may be true that F and
G are very important for this reason,

71
00:03:59,030 --> 00:04:02,630
it's not reasonable to think that all
the other nodes have no importance,

72
00:04:02,630 --> 00:04:04,210
have zero importance.

73
00:04:04,210 --> 00:04:07,380
And so we need to figure out
a way of how to fix this problem.

74
00:04:07,380 --> 00:04:10,979
And the way we fix this problem is
by introducing a new parameter to

75
00:04:10,979 --> 00:04:14,590
the PageRank computation called
this damping parameter alpha.

76
00:04:14,590 --> 00:04:19,095
And so what we're going to do is
we're going to change the way we do

77
00:04:19,095 --> 00:04:21,220
our random walk.

78
00:04:21,220 --> 00:04:24,200
What we're going to do is we're going to
take a random walk with the damping

79
00:04:24,200 --> 00:04:24,880
parameter alpha.

80
00:04:24,880 --> 00:04:29,030
And the way it works is that we
again start at a random node.

81
00:04:29,030 --> 00:04:31,250
And then with probability alpha,

82
00:04:31,250 --> 00:04:34,290
we're going to follow
the outgoing edges at random,

83
00:04:34,290 --> 00:04:38,430
just like we did before, but this is only
going to happen with probability alpha.

84
00:04:39,540 --> 00:04:41,550
With probability 1- alpha,

85
00:04:41,550 --> 00:04:45,700
we're actually going to choose a node
completely at random and jump to it.

86
00:04:45,700 --> 00:04:50,100
So again, at every step, what we used to
do before was to always follow the edges.

87
00:04:50,100 --> 00:04:52,415
What we're going to do now
is that at every step,

88
00:04:52,415 --> 00:04:55,532
we're either going to follow
the edges with probability alpha.

89
00:04:55,532 --> 00:04:58,978
Or we are going to forget about the edges,
and choose a random node, and

90
00:04:58,978 --> 00:05:03,014
go to it with probability one minus alpha,
and we're going to repeat this k times.

91
00:05:03,014 --> 00:05:06,947
And so what happens now, if you think
about the random walk on this particular

92
00:05:06,947 --> 00:05:10,290
network, is that we're no longer
stuck on nodes F and G, right?

93
00:05:10,290 --> 00:05:12,760
because even if we were
to be on node F and

94
00:05:12,760 --> 00:05:16,900
G, because we have some probability
1- alpha of choosing a random node,

95
00:05:16,900 --> 00:05:21,570
then we're going to get unstuck whenever
we actually choose a random node.

96
00:05:21,570 --> 00:05:26,290
And so the Scaled PageRank of k steps with
damping parameter alpha of a node n is

97
00:05:26,290 --> 00:05:31,420
going to be the probability that this new
random walk with damping parameter alpha

98
00:05:31,420 --> 00:05:34,390
lands on a node and after k steps.

99
00:05:34,390 --> 00:05:36,710
I'm not going to show you how to
actually compute this Scaled PageRank.

100
00:05:36,710 --> 00:05:40,177
I'm assuming you're going
to use NetworkX to do this,

101
00:05:40,177 --> 00:05:44,260
but this is the way you interpret
it with respect to a random walk.

102
00:05:44,260 --> 00:05:47,610
And so just like with the other
PageRank with the basic PageRank, for

103
00:05:47,610 --> 00:05:53,630
most networks as k gets larger, the Scaled
PageRank converges to a unique value.

104
00:05:53,630 --> 00:05:54,160
But now,

105
00:05:54,160 --> 00:05:58,610
that unique value will be dependent on the
particular value of alpha that you choose.

106
00:05:59,860 --> 00:06:01,215
And so in practice,

107
00:06:01,215 --> 00:06:05,932
what we do is we choose our
parameter alpha between 0.8 and 0.9.

108
00:06:05,932 --> 00:06:09,210
So most of the time,
we're going to be following the edges.

109
00:06:09,210 --> 00:06:14,340
But sometimes, maybe 10 or 20% of the
time, we're going to be jumping randomly,

110
00:06:14,340 --> 00:06:16,190
that way we're not stuck
anywhere in the network.

111
00:06:17,520 --> 00:06:22,640
And so if we look at the Scaled PageRank
value for each one of these nodes, for

112
00:06:22,640 --> 00:06:28,050
k very large and alpha parameter of .08,
these are the values that we get.

113
00:06:28,050 --> 00:06:29,540
So, what you find is that F and

114
00:06:29,540 --> 00:06:33,450
G still have a very high PageRank
compared to the other notes.

115
00:06:33,450 --> 00:06:36,110
But the other nodes don't
have a PageRank value of 0.

116
00:06:36,110 --> 00:06:39,676
And if we you at the PageRank of
all the other nodes, A through E,

117
00:06:39,676 --> 00:06:43,518
you find that it follows the same
type of ordering that it did before.

118
00:06:43,518 --> 00:06:48,464
So B still has the highest value of Scaled
PageRank followed by C, followed by D and

119
00:06:48,464 --> 00:06:53,460
A, which roughly get the same value,
and then followed by node E.

120
00:06:53,460 --> 00:06:57,120
And so F and G still have high PageRank,
but not all of the PageRank.

121
00:06:57,120 --> 00:07:01,895
And this damping parameter works better
for large networks like the web or

122
00:07:01,895 --> 00:07:03,295
very large social networks.

123
00:07:03,295 --> 00:07:07,055
And this small networks sometimes,
it doesn't work very well.

124
00:07:07,055 --> 00:07:10,755
In this particular example that
I showed you, it works well.

125
00:07:10,755 --> 00:07:14,635
So it serves the purpose of showing you
how it works, but it's much better for

126
00:07:14,635 --> 00:07:16,820
very, very large network.

127
00:07:16,820 --> 00:07:20,661
And if you're using NetworkX, you can
use the function PageRank with input G,

128
00:07:20,661 --> 00:07:21,530
which is a graph.

129
00:07:21,530 --> 00:07:24,250
And then you have to tell
what the alpha parameter is

130
00:07:24,250 --> 00:07:28,560
to compute this Scaled PageRank of the
network G with a damping parameter alpha.

131
00:07:30,030 --> 00:07:30,640
So in summary,

132
00:07:30,640 --> 00:07:33,760
what we find is that the basic PageRank
of a node can be interpreted as

133
00:07:33,760 --> 00:07:37,650
the probability that a random walk
lands on that node after k steps.

134
00:07:37,650 --> 00:07:40,353
And this is a useful interpretation,
because well,

135
00:07:40,353 --> 00:07:43,244
it allows us to see this problem
that Basic PageRank has.

136
00:07:43,244 --> 00:07:46,136
That sometimes for some networks,
a few nodes can sort of suck up all

137
00:07:46,136 --> 00:07:48,880
the PageRank from all the other
nodes in the network.

138
00:07:48,880 --> 00:07:52,200
And so to fix this problem, there is this
other version of PageRank which is called

139
00:07:52,200 --> 00:07:55,050
Scaled PageRank that introduces
this parameter alpha.

140
00:07:55,050 --> 00:08:00,020
So this random walker chooses a random
node to jump to with probability 1- alpha.

141
00:08:00,020 --> 00:08:04,800
So, what that does is that it allows
the walker to not be stuck anywhere, but

142
00:08:04,800 --> 00:08:07,420
sometimes it's sort of jumping randomly.

143
00:08:07,420 --> 00:08:10,680
And typically, we use a perimeter
alpha between 0.8 and 0.9.

144
00:08:10,680 --> 00:08:15,618
But we do have to keep in mind that the
PageRank value that we get will depend on

145
00:08:15,618 --> 00:08:18,770
the particular choice of alpha.

146
00:08:18,770 --> 00:08:23,570
And to compute this or to use this in
NetworkX, you can use the function

147
00:08:23,570 --> 00:08:28,340
PageRank with input parameters G, the
network, and then the alpha that you want,

148
00:08:28,340 --> 00:08:32,500
to compute the Scaled PageRank with the
network G with damping parameter alpha.

149
00:08:32,500 --> 00:08:34,680
And that's all for today, and
I hope to see you next time.