1
23:59:59,976 --> 00:00:05,638
[MUSIC]. 

2
00:00:05,638 --> 00:00:08,410
So we talked about a couple different 
notions of centrality, and one more is 

3
00:00:08,410 --> 00:00:11,182
degree centrality, which is just the 
degree of a vertex divided by the total 

4
00:00:11,182 --> 00:00:15,840
number of edges, right? 
So this is the fraction of all the edges 

5
00:00:15,840 --> 00:00:17,610
that touch me. 
Okay? 

6
00:00:17,610 --> 00:00:21,380
And so imagine, this, so maybe this is a 
good candidate for our, you know, we're 

7
00:00:21,380 --> 00:00:25,785
seeking some notion of importance in the 
vertex of a graph. 

8
00:00:25,785 --> 00:00:29,062
All right. 
So imagine we have a social network and, 

9
00:00:29,062 --> 00:00:32,950
you know, then the degree of a vertex is 
the number of friends you might have. 

10
00:00:32,950 --> 00:00:35,656
Well, the people with more friends are in 
some sense, some sense more important 

11
00:00:35,656 --> 00:00:39,025
than people with fewer friends in the 
context of a social network. 

12
00:00:39,025 --> 00:00:41,698
Fine. 
But if, you know, say we both have five 

13
00:00:41,698 --> 00:00:44,077
friends. 
Well, then we have the same degree 

14
00:00:44,077 --> 00:00:47,263
centrality by this definition, but what 
if your five friends are, they 

15
00:00:47,263 --> 00:00:51,650
themselves, much more connected than my 
five friends? 

16
00:00:51,650 --> 00:00:54,614
In some sense, you should be more 
important than I am in the context of 

17
00:00:54,614 --> 00:00:58,046
this social network, and the notion of 
this degree centrality doesn't capture 

18
00:00:58,046 --> 00:01:00,226
that. 
All right? 

19
00:01:00,226 --> 00:01:04,182
So, let's see if we can improve on this. 
Well, another notion of centrality is 

20
00:01:04,182 --> 00:01:08,040
Eigenvector Centrality, which is actually 
just PageRank. 

21
00:01:08,040 --> 00:01:10,560
And so if you are, are familiar with 
PageRank, or this may just be another way 

22
00:01:10,560 --> 00:01:13,160
of looking at it, if you're not familiar 
with PageRank, then this is a great way 

23
00:01:13,160 --> 00:01:17,922
to develop an intuition for it. 
So the basic idea for computing PageRank 

24
00:01:17,922 --> 00:01:21,402
is, you know, while things are not 
converged, for each vertex in a, in the 

25
00:01:21,402 --> 00:01:26,316
graph. 
Compute the rank of that vertex by adding 

26
00:01:26,316 --> 00:01:29,974
up the ranks of all of its neighbor 
vertices, all the incoming edges that we 

27
00:01:29,974 --> 00:01:36,490
see in the directed graph. 
Right, so this allows you to say well, 

28
00:01:36,490 --> 00:01:40,450
look, if Barack Obama, if the president 
of the United States is connected to you 

29
00:01:40,450 --> 00:01:45,035
by one hop, he's your friend. 
Say, follows you on Twitter or something 

30
00:01:45,035 --> 00:01:47,660
like that. 
Well then, you're more important than 

31
00:01:47,660 --> 00:01:52,510
somebody who doesn't have such a, such an 
influential person to grab. 

32
00:01:52,510 --> 00:01:58,210
You add up the rank of the president to 
your rank, okay? 

33
00:01:58,210 --> 00:02:03,460
Meanwhile, you distribute your rank to 
all your friends, right. 

34
00:02:03,460 --> 00:02:06,998
So, and you do this, you repeat this 
passing of, of rank, of wait, of 

35
00:02:06,998 --> 00:02:10,658
importance to across the network, across 
the graph until you reach some 

36
00:02:10,658 --> 00:02:15,346
convergence condition. 
And then that convergence condition gives 

37
00:02:15,346 --> 00:02:17,970
you a relative score of whose more 
important than who, perhaps, which, which 

38
00:02:17,970 --> 00:02:21,500
vertex is more important than which other 
vertex. 

39
00:02:21,500 --> 00:02:23,520
But there's a couple of problems with 
this approach. 

40
00:02:23,520 --> 00:02:27,936
So one is, you know, up one page or one 
person in a social network with millions 

41
00:02:27,936 --> 00:02:32,421
of outgoing links, if they link to me, 
that's somehow less valuable than a page 

42
00:02:32,421 --> 00:02:37,820
that only links to a few people. 
Right? 

43
00:02:37,820 --> 00:02:42,580
So if you've got one of these crawlers 
that follow everyone in order to collect 

44
00:02:42,580 --> 00:02:46,710
as much, follow everyone on Twitter, in 
order to collect as much data as 

45
00:02:46,710 --> 00:02:50,682
possible. 
It's not very important that they follow 

46
00:02:50,682 --> 00:02:52,690
you, right? 
You don't consider that to be very 

47
00:02:52,690 --> 00:02:56,930
prestigious that you have some automatic 
robot crawler following you. 

48
00:02:56,930 --> 00:03:00,505
Meanwhile, if you let an aggregator page 
that sort links out to everyone on the 

49
00:03:00,505 --> 00:03:06,230
internet as similarly that's not very 
important that it links to you. 

50
00:03:06,230 --> 00:03:09,238
So somehow you want to make sure that 
they divide their rank amongst all their 

51
00:03:09,238 --> 00:03:13,694
outgoing edges as opposed to just give 
their total rank to each outgoing edge. 

52
00:03:13,694 --> 00:03:16,619
Fine. 
So that's easy to fix. 

53
00:03:16,619 --> 00:03:19,595
You know, another notion here is that, 
well, if I'm, if I'm 27 hops away from 

54
00:03:19,595 --> 00:03:24,060
Barack Obama, that's less important than 
if I'm one hop away. 

55
00:03:24,060 --> 00:03:26,810
And so, we, we really shouldn't count 
that as very influential. 

56
00:03:27,820 --> 00:03:30,529
And so, we need some sort of a damping 
factor that, as you get further away, it 

57
00:03:30,529 --> 00:03:32,954
sort of lowers the importance. 
Okay? 

58
00:03:32,954 --> 00:03:37,364
So you combine these two definitions 
together and you get the definition of 

59
00:03:37,364 --> 00:03:42,194
PageRank, as it was published and there's 
a couple of variations on this, but, this 

60
00:03:42,194 --> 00:03:45,883
is the one to know. 
Okay? 

61
00:03:45,883 --> 00:03:52,795
So while not converged, the rank of, of a 
vertex A, is the sum of all the ranks of 

62
00:03:52,795 --> 00:03:58,999
the vertices that link to A. 
But each one is divided by the total 

63
00:03:58,999 --> 00:04:02,274
number of outgoing edges. 
So, in this notation, we assume that 

64
00:04:02,274 --> 00:04:07,660
there are edges B linking to A, C linking 
to A, D linking to A. 

65
00:04:07,660 --> 00:04:11,356
And PR of A, the PageRank of a no, of a 
vertex X is the, is going to be the 

66
00:04:11,356 --> 00:04:17,510
PageRank of the vertex X, L of X is the 
number of outgoing links from X. 

67
00:04:17,510 --> 00:04:20,814
And so, for the page, we take the 
PageRank of B and divide by the number of 

68
00:04:20,814 --> 00:04:25,280
outgoing links from B. 
Take the PageRank of C, divide by the 

69
00:04:25,280 --> 00:04:27,811
number of outgoing links away from C and 
so on. 

70
00:04:27,811 --> 00:04:31,520
Add all that up, and that's all the 
contribution to A. 

71
00:04:31,520 --> 00:04:34,930
And then we multiply by a damping factor 
to make sure that we, what we pass on 

72
00:04:34,930 --> 00:04:38,395
goes, diminishes over time as we get 
further and further away, and then this 

73
00:04:38,395 --> 00:04:44,720
other term in this expression is just to 
ensure that all the ranks sum up to one. 

74
00:04:44,720 --> 00:04:47,260
So that we can sort of interpret them as 
probabilities. 

75
00:04:47,260 --> 00:04:50,900
And in fact, you can directly interpret 
this as probability which is another way 

76
00:04:50,900 --> 00:04:54,228
of look at PageRank and deriving PageRank 
is to talk random walks around the, 

77
00:04:54,228 --> 00:04:58,492
around the internet, around the, around 
the graph. 

78
00:04:58,492 --> 00:05:02,570
Right, so you start on a random vertex 
and just start walking. 

79
00:05:02,570 --> 00:05:06,098
Should make a choice at random among the 
edges, the outgoing edges, and just 

80
00:05:06,098 --> 00:05:09,420
traverse around. 
Well, if you do this a bunch of times, 

81
00:05:09,420 --> 00:05:12,600
you can derive how likely it is that 
you'll spend time on some particular 

82
00:05:12,600 --> 00:05:15,833
vertex versus some other particular 
vertex, and that will exactly be the 

83
00:05:15,833 --> 00:05:20,753
PageRank. 
And so this is sort of, you know, all 

84
00:05:20,753 --> 00:05:24,907
roads lead back to Wikipedia or CNN or 
some other very, you know, important 

85
00:05:24,907 --> 00:05:31,650
vertex in the web graph. 
So that's PageRank and what I want to 

86
00:05:31,650 --> 00:05:34,890
point out before we move on is just the 
relative simplicity of this, right? 

87
00:05:34,890 --> 00:05:38,362
It really comes out of an intuitive 
notion of trying to figure out how can we 

88
00:05:38,362 --> 00:05:41,970
measure the importance of a vertex in the 
graph? 

89
00:05:41,970 --> 00:05:45,155
And so, you know, you start from very 
simple notions of, well, maybe important 

90
00:05:45,155 --> 00:05:49,230
means just the one with the highest 
number of edges that link to it. 

91
00:05:49,230 --> 00:05:51,640
Well, there's some problems with that, so 
let's see if we can fix it. 

92
00:05:51,640 --> 00:05:56,265
Maybe it's the one with the the most 
number of paths that go through it. 

93
00:05:56,265 --> 00:05:58,930
I mean we don't care about all paths, we 
care about shortest paths so that gives 

94
00:05:58,930 --> 00:06:02,194
you another notion of importance. 
And you say, well, that's got some 

95
00:06:02,194 --> 00:06:04,750
problems too, what are the properties we 
really want here? 

96
00:06:04,750 --> 00:06:08,050
Well, maybe it kind of captures the 
importance of your friends need to be 

97
00:06:08,050 --> 00:06:11,460
added in there somehow and you can sort 
of walk through this and come up with 

98
00:06:11,460 --> 00:06:15,832
where PageRank came from. 
So the way it's presented, just like a 

99
00:06:15,832 --> 00:06:18,394
lot of these things, are presented in 
terms of a, of a finished formula and 

100
00:06:18,394 --> 00:06:21,082
then you kind of have to work out back, 
you know, reverse engineer where it came 

101
00:06:21,082 --> 00:06:24,858
from. 
But a lot of these things are developed 

102
00:06:24,858 --> 00:06:28,811
very intuitively and the formula is only 
used as a notion to express to intuition 

103
00:06:28,811 --> 00:06:31,530
in a, in a precise way.