1
00:00:08,070 --> 00:00:13,840
Hello. Today we're going to talk about the concept of distance in social networks.

2
00:00:13,840 --> 00:00:15,940
So the idea here is that sometimes we'd like

3
00:00:15,940 --> 00:00:18,100
to know how far nodes are away from each other.

4
00:00:18,100 --> 00:00:24,295
So for example in this network that you see here how far is node A from node H?

5
00:00:24,295 --> 00:00:27,270
Or we'd like to know, for example,

6
00:00:27,270 --> 00:00:29,865
are some nodes far away from

7
00:00:29,865 --> 00:00:34,455
each other and other nodes close to each other in general in this network?

8
00:00:34,455 --> 00:00:37,110
And if so, which nodes are closest and

9
00:00:37,110 --> 00:00:40,365
which nodes are the furthest away from each other in the network?

10
00:00:40,365 --> 00:00:41,955
To answer all these questions,

11
00:00:41,955 --> 00:00:45,390
we need to develop a concept of distance between nodes.

12
00:00:45,390 --> 00:00:48,600
And that's what we're going to do in this video today.

13
00:00:48,600 --> 00:00:50,200
So to answer this question,

14
00:00:50,200 --> 00:00:53,050
the first concept we need is the concept of a path.

15
00:00:53,050 --> 00:00:56,710
A path is simply a sequence of nodes that are connected by an edge.

16
00:00:56,710 --> 00:01:02,140
So for example, we can find paths that go from the node G to the node C.

17
00:01:02,140 --> 00:01:05,970
Here's the path G-F-C.

18
00:01:05,970 --> 00:01:13,555
And you can find different paths so for example here's the path G-F-E-C.

19
00:01:13,555 --> 00:01:16,565
So how far is node A from node H?

20
00:01:16,565 --> 00:01:21,110
Well, we will look at different paths that go from A to H.

21
00:01:21,110 --> 00:01:25,111
So for example, we can find a path A-B-C-E-H.

22
00:01:25,111 --> 00:01:30,220
And notice that this path it takes four hops to get

23
00:01:30,220 --> 00:01:34,510
from A to H. And there are other paths so for example there is

24
00:01:34,510 --> 00:01:39,029
the path A-B-C-F-E-H which takes five hops.

25
00:01:39,029 --> 00:01:40,945
And so for a path,

26
00:01:40,945 --> 00:01:43,180
we're going to define the path length to be the number

27
00:01:43,180 --> 00:01:46,000
of steps that it contains from the beginning to the end.

28
00:01:46,000 --> 00:01:51,160
So in this case path one has length four and path two has length five.

29
00:01:51,160 --> 00:01:57,295
And to define the distance between two nodes,

30
00:01:57,295 --> 00:01:59,570
we're going to define it to be the length of

31
00:01:59,570 --> 00:02:02,450
the shortest possible path between the two nodes.

32
00:02:02,450 --> 00:02:07,160
So going back to the question of what is the distance between node A to node H,

33
00:02:07,160 --> 00:02:10,205
the answer is four, because the shortest path between

34
00:02:10,205 --> 00:02:14,105
A and H has four hops or has length 4.

35
00:02:14,105 --> 00:02:17,540
In network X, you can use the function shortest_path

36
00:02:17,540 --> 00:02:20,810
to find a distance from any node to any other node.

37
00:02:20,810 --> 00:02:23,630
So here in this example finding the distance between

38
00:02:23,630 --> 00:02:28,540
node A and H in the graph G which is the graph that you see here.

39
00:02:28,540 --> 00:02:33,147
And so here you get the shortest path between A

40
00:02:33,147 --> 00:02:35,860
and H. If you're interested in just the length

41
00:02:35,860 --> 00:02:38,735
of this path then you can use the function shortest_path_length,

42
00:02:38,735 --> 00:02:43,136
and this gives you the length of this path which is four.

43
00:02:43,136 --> 00:02:45,950
Okay, so sometimes what we would like to do

44
00:02:45,950 --> 00:02:50,060
when we have real social networks is to find a distance

45
00:02:50,060 --> 00:02:53,690
from a single node to all the other nodes in the network to figure out how

46
00:02:53,690 --> 00:02:57,635
far away are other nodes from this specific route to node, in this case A.

47
00:02:57,635 --> 00:02:59,528
Let's say we're interested in figuring out what distance

48
00:02:59,528 --> 00:03:02,716
from node A to all the other nodes in the network is.

49
00:03:02,716 --> 00:03:05,360
Well, this is something that you can easily

50
00:03:05,360 --> 00:03:08,360
do manually in the network that's very small like this,

51
00:03:08,360 --> 00:03:10,815
but this could become very tedious to do

52
00:03:10,815 --> 00:03:13,935
manually if you have a very large social network.

53
00:03:13,935 --> 00:03:19,665
And so what you can do is you can program a computer to do this.

54
00:03:19,665 --> 00:03:22,557
And so what we're going to do is we're going to talk about one of

55
00:03:22,557 --> 00:03:24,920
the efficient ways that we

56
00:03:24,920 --> 00:03:28,588
have to compute the distances from a given node to all the other nodes.

57
00:03:28,588 --> 00:03:32,600
And this one is called breadth-first search and what it basically does is that you

58
00:03:32,600 --> 00:03:36,815
start at a node and you start kind of discovering different nodes or different layers,

59
00:03:36,815 --> 00:03:38,510
and at each given layer,

60
00:03:38,510 --> 00:03:40,940
you discover the set of nodes that are one

61
00:03:40,940 --> 00:03:44,120
distance away from the nodes that were in the previous layer.

62
00:03:44,120 --> 00:03:48,915
So, I'm going to walk you through an example of how breadth-first search works.

63
00:03:48,915 --> 00:03:51,980
So here we have the network and we're interested in figuring out

64
00:03:51,980 --> 00:03:55,450
the distance from node A to all the other nodes in the network.

65
00:03:55,450 --> 00:03:58,670
So what we're going to do is we're going to start at A and we're going to start

66
00:03:58,670 --> 00:04:02,210
discovering new nodes as we kind of walk through this network.

67
00:04:02,210 --> 00:04:05,445
And we're going to be writing down all the nodes that we discover.

68
00:04:05,445 --> 00:04:10,680
So we start at A and we sort of process the node A by looking at who is connected to A.

69
00:04:10,680 --> 00:04:13,220
In this case, K and B are connected to A and

70
00:04:13,220 --> 00:04:15,770
so those are going to be a distance one away because

71
00:04:15,770 --> 00:04:21,395
they're the shortest path from each one of those nodes to A it's just one hop, right?

72
00:04:21,395 --> 00:04:23,570
A path of length one.

73
00:04:23,570 --> 00:04:28,220
Okay, so now we're going to process each one of the newly discovered nodes and

74
00:04:28,220 --> 00:04:29,870
ask which nodes are connected to

75
00:04:29,870 --> 00:04:33,255
this newly discovered node that we haven't discovered yet?

76
00:04:33,255 --> 00:04:36,220
And those nodes are going to be assigned to the next layer.

77
00:04:36,220 --> 00:04:37,850
So let's say we process node B.

78
00:04:37,850 --> 00:04:41,390
Node B is connected to K, A and C.

79
00:04:41,390 --> 00:04:44,813
But we've already discovered nodes A and K,

80
00:04:44,813 --> 00:04:50,815
so the only node that we discover here is node C. Now we're going to process node K,

81
00:04:50,815 --> 00:04:53,660
and node K is connected to node A and B,

82
00:04:53,660 --> 00:04:55,250
but we've already discovered both of those.

83
00:04:55,250 --> 00:05:00,736
So the only newly discovered node is node C and it's a distance two away from A.

84
00:05:00,736 --> 00:05:05,520
Now we process node C which is connected to B, F, and E.

85
00:05:05,520 --> 00:05:10,215
And here we've already discovered B so the only two nodes that we discover are

86
00:05:10,215 --> 00:05:16,500
F and E and those are a distance three away from A.

87
00:05:16,500 --> 00:05:18,640
Okay, now we're going to process node E.

88
00:05:18,640 --> 00:05:24,800
Okay, node E has five connections and out of those five,

89
00:05:24,800 --> 00:05:26,930
C and F we already discovered.

90
00:05:26,930 --> 00:05:30,140
So the only new ones are the other three which are D,

91
00:05:30,140 --> 00:05:33,945
I and H. So we assign those to the next layer.

92
00:05:33,945 --> 00:05:38,560
Now we process node F which is connected to three nodes G,

93
00:05:38,560 --> 00:05:41,760
C and E. But the only one we haven't discovered yet

94
00:05:41,760 --> 00:05:45,725
out of all those is G so I want this to get assigned to the next layer.

95
00:05:45,725 --> 00:05:49,120
And all of those nodes are a distance four away from A.

96
00:05:49,120 --> 00:05:52,940
Okay, now we have to process each one of those newly discovered nodes.

97
00:05:52,940 --> 00:05:55,950
And by now you can see that we're already almost done here.

98
00:05:55,950 --> 00:06:00,020
So let's process node D which is only

99
00:06:00,020 --> 00:06:05,320
connected to E. But we've already discovered E so D does not discover any new nodes.

100
00:06:05,320 --> 00:06:09,205
Now let's go with I. I is connected to E and J.

101
00:06:09,205 --> 00:06:11,360
And we haven't discovered J yet,

102
00:06:11,360 --> 00:06:15,110
so this one it's assigned to the next layer.

103
00:06:15,110 --> 00:06:20,510
Next we process H which is only connected to E but we already discovered E. And finally,

104
00:06:20,510 --> 00:06:25,340
we process G which is connected to F which you've already discovered.

105
00:06:25,340 --> 00:06:29,210
So, J is a distance five away. All right?

106
00:06:29,210 --> 00:06:31,910
We have to process J, but J is only connected to

107
00:06:31,910 --> 00:06:34,810
I which we already discovered and now we're done.

108
00:06:34,810 --> 00:06:35,955
We've processed all the nodes.

109
00:06:35,955 --> 00:06:38,210
There are no new nodes to discover.

110
00:06:38,210 --> 00:06:41,280
And so here you can see how we efficiently

111
00:06:41,280 --> 00:06:44,875
figure out the distance between A and all the other nodes in the network,

112
00:06:44,875 --> 00:06:47,010
and this is something that you can

113
00:06:47,010 --> 00:06:51,120
program using a computer to do this in an efficient way.

114
00:06:51,120 --> 00:06:53,835
You can use network X to run the breadth-first search

115
00:06:53,835 --> 00:06:58,180
algorithm by using the function bfs_tree.

116
00:06:58,180 --> 00:07:01,110
And what it does is it gives you the tree that we've built.

117
00:07:01,110 --> 00:07:08,770
And this graph that we built here is called a tree,

118
00:07:08,770 --> 00:07:12,250
and is the tree of the nodes that you discovered.

119
00:07:12,250 --> 00:07:14,220
And so with this function,

120
00:07:14,220 --> 00:07:16,770
you're able to obtain this tree.

121
00:07:16,770 --> 00:07:18,510
So if you look at the edges of

122
00:07:18,510 --> 00:07:22,165
the graph t here and you get that these are the edges of that tree.

123
00:07:22,165 --> 00:07:26,700
So there is A-K and A-B and B-C and so on.

124
00:07:26,700 --> 00:07:27,810
Now if you're interested in

125
00:07:27,810 --> 00:07:31,365
not necessarily the tree in the order in which these nodes were discovered,

126
00:07:31,365 --> 00:07:36,410
but just simply the actual distances between A and all the other nodes,

127
00:07:36,410 --> 00:07:40,680
then you can use shortest_path_length and you give it the graph,

128
00:07:40,680 --> 00:07:42,945
which in this case is G, and the root node,

129
00:07:42,945 --> 00:07:44,800
which in this case is A.

130
00:07:44,800 --> 00:07:48,750
And you get a dictionary of all the distances from the node to all the other nodes.

131
00:07:48,750 --> 00:07:51,060
So, A is a distance zero from itself,

132
00:07:51,060 --> 00:07:52,350
a distance one from B,

133
00:07:52,350 --> 00:07:56,315
a distance two from C and so on.

134
00:07:56,315 --> 00:08:00,772
Okay, so we've defined distance between any two nodes in a network,

135
00:08:00,772 --> 00:08:04,480
but if we go back to the original questions we had, in the beginning,

136
00:08:04,480 --> 00:08:07,870
we were interested in, we're characterizing the distances between

137
00:08:07,870 --> 00:08:10,280
all pairs of nodes in the graph.

138
00:08:10,280 --> 00:08:12,310
Our nodes in general close to each other,

139
00:08:12,310 --> 00:08:13,760
far away from each other.

140
00:08:13,760 --> 00:08:15,850
If some are close and some are far,

141
00:08:15,850 --> 00:08:19,080
then how can we figure out, which are close and which are far and so on?

142
00:08:19,080 --> 00:08:21,940
And so, now, we're going to try to answer these questions.

143
00:08:21,940 --> 00:08:23,830
So, the first thing you can do, is you can simply take

144
00:08:23,830 --> 00:08:27,550
the average distance between every pair of nodes in the network.

145
00:08:27,550 --> 00:08:32,030
In network X, you can do that by using the function average shortest path length.

146
00:08:32,030 --> 00:08:33,520
In G, and in this case,

147
00:08:33,520 --> 00:08:37,010
this graph has an average path length of 2.53.

148
00:08:37,010 --> 00:08:39,310
So, that means, that on average any pair of nodes in

149
00:08:39,310 --> 00:08:43,215
this graph are a distance 2.53 from each other.

150
00:08:43,215 --> 00:08:45,550
So, that tells you what sort of,

151
00:08:45,550 --> 00:08:46,860
on average what happens.

152
00:08:46,860 --> 00:08:49,675
Now, what is the maximum possible distance between any two nodes,

153
00:08:49,675 --> 00:08:53,510
that sort of like, what are the two nodes that are furthest away from each other?

154
00:08:53,510 --> 00:08:56,695
How long is that? How far away from each other are they?

155
00:08:56,695 --> 00:08:58,425
This is called the diameter and is

156
00:08:58,425 --> 00:09:01,490
simply the maximum distance between any two pair of nodes.

157
00:09:01,490 --> 00:09:05,016
And in network X, you can use the function diameter to get it,

158
00:09:05,016 --> 00:09:07,600
and in this case the diameter of the graph is

159
00:09:07,600 --> 00:09:12,000
five and you can see that by looking at the distance from K to J,

160
00:09:12,000 --> 00:09:15,115
which has a length of five.

161
00:09:15,115 --> 00:09:19,532
The other thing that is useful to define is the eccentricity of a node.

162
00:09:19,532 --> 00:09:21,840
The eccentricity of a node is the largest distance

163
00:09:21,840 --> 00:09:24,180
between the node and all the other nodes in the network.

164
00:09:24,180 --> 00:09:27,240
So, you take a node, measure the distance from the node to all the other nodes,

165
00:09:27,240 --> 00:09:30,230
and figure out which one of those instances is the largest one of all.

166
00:09:30,230 --> 00:09:35,590
In network X, you can use the function eccentricity to get all those distances,

167
00:09:35,590 --> 00:09:37,180
and here, you can see for example,

168
00:09:37,180 --> 00:09:40,560
that A has an eccentricity of five, as we had seen.

169
00:09:40,560 --> 00:09:43,045
It has a distance five to some node,

170
00:09:43,045 --> 00:09:44,920
which in this case that's J.

171
00:09:44,920 --> 00:09:46,370
So, that's pretty large.

172
00:09:46,370 --> 00:09:48,340
It's actually as big as it could get, right?

173
00:09:48,340 --> 00:09:52,880
Because the diameter, the largest possible distance between two nodes was five.

174
00:09:52,880 --> 00:09:55,360
But, if you think of a node like for example,

175
00:09:55,360 --> 00:10:00,790
node E here, which looks like it's closer to all the other nodes,

176
00:10:00,790 --> 00:10:04,630
then you see that it has a eccentricity of three,

177
00:10:04,630 --> 00:10:09,400
which means that no node in this graph is a distance

178
00:10:09,400 --> 00:10:14,560
larger than three from node E.

179
00:10:14,560 --> 00:10:16,750
And so, now, that you have this eccentricities,

180
00:10:16,750 --> 00:10:20,100
the radius of the graph is the minimum eccentricity in the network.

181
00:10:20,100 --> 00:10:22,575
It basically asks which node or not which node,

182
00:10:22,575 --> 00:10:26,618
but what is the maximum distance that a node has from all the other nodes,

183
00:10:26,618 --> 00:10:31,530
that's eccentricity and the radius takes the smallest one of those.

184
00:10:31,530 --> 00:10:36,460
And in network X, you can use the function radius to get the radius of

185
00:10:36,460 --> 00:10:41,985
the network and as you could see from the dictionary of eccentricities,

186
00:10:41,985 --> 00:10:46,170
the radius of this network is three.

187
00:10:46,170 --> 00:10:49,200
The next question we had was,

188
00:10:49,200 --> 00:10:52,360
now that we know how to calculate distances and now that we have

189
00:10:52,360 --> 00:10:55,568
a sense for what is a large distance in the network, like, the diameter,

190
00:10:55,568 --> 00:10:57,850
what is the short distance, like the radius,

191
00:10:57,850 --> 00:11:01,630
we can try to identify which nodes are sort of far away

192
00:11:01,630 --> 00:11:05,545
from all the other nodes and which nodes are close to all the other nodes.

193
00:11:05,545 --> 00:11:08,470
So, for the first one, we have the periphery,

194
00:11:08,470 --> 00:11:11,050
which is the set of nodes in a graph that have

195
00:11:11,050 --> 00:11:14,155
an eccentricity equals to the diameter of the network,

196
00:11:14,155 --> 00:11:16,910
which is sort of the largest eccentricity that you could have,

197
00:11:16,910 --> 00:11:22,115
since the diameter is the largest distance between any two nodes in the network.

198
00:11:22,115 --> 00:11:24,145
So, if you apply this definition to this graph,

199
00:11:24,145 --> 00:11:29,785
you find that the periphery of this graph are the nodes A, K, and J.

200
00:11:29,785 --> 00:11:33,250
You can get these set of nodes using networks,

201
00:11:33,250 --> 00:11:35,665
network X function periphery.

202
00:11:35,665 --> 00:11:38,950
And as you would sort of imagine these nodes tend to be

203
00:11:38,950 --> 00:11:44,090
sort of on the outskirts of the network far away from all the other nodes.

204
00:11:44,090 --> 00:11:49,296
The opposite concept is the concept of nodes that are central.

205
00:11:49,296 --> 00:11:54,475
So, the center of the graph is a set of nodes that have eccentricity equal to the radius.

206
00:11:54,475 --> 00:11:57,690
And when you check which nodes are in the center in

207
00:11:57,690 --> 00:12:01,280
this graph using the center function network X, you find that C, F,

208
00:12:01,280 --> 00:12:04,070
and E are nodes that are in the center of the graph,

209
00:12:04,070 --> 00:12:05,267
and this is sort of like,

210
00:12:05,267 --> 00:12:08,140
it make sense there in the towards the center of the graph,

211
00:12:08,140 --> 00:12:12,945
they tend to be close to most of the nodes.

212
00:12:12,945 --> 00:12:14,690
Okay, so with these tools, now,

213
00:12:14,690 --> 00:12:16,850
you're able to take a look at a network,

214
00:12:16,850 --> 00:12:18,110
a real social network,

215
00:12:18,110 --> 00:12:23,075
and start to ask questions about how far are these nodes from each other?

216
00:12:23,075 --> 00:12:24,470
Which nodes are central?

217
00:12:24,470 --> 00:12:26,000
Which nodes are not and so on?

218
00:12:26,000 --> 00:12:30,040
So, let's run an example in this using the Karate Club Network,

219
00:12:30,040 --> 00:12:32,030
which we had seen in a previous video.

220
00:12:32,030 --> 00:12:35,580
So, this is a network of friendship in a Karate Club.

221
00:12:35,580 --> 00:12:37,670
And as you may remember, the story here,

222
00:12:37,670 --> 00:12:41,975
is that node one is the instructor of the Karate Club,

223
00:12:41,975 --> 00:12:44,955
and this node 34 is an assistant,

224
00:12:44,955 --> 00:12:46,514
and they have some type of dispute,

225
00:12:46,514 --> 00:12:48,448
they're not friends with each other,

226
00:12:48,448 --> 00:12:51,718
and so the club actually splits into two groups,

227
00:12:51,718 --> 00:12:54,410
and sort of, this is the separation of the two groups.

228
00:12:54,410 --> 00:12:57,370
So one, this set of students on the left go with one of

229
00:12:57,370 --> 00:13:01,960
the instructors or with the assistant and the other ones go with the original instructor.

230
00:13:01,960 --> 00:13:04,310
So, if we take this network and apply

231
00:13:04,310 --> 00:13:07,970
the definitions about distances that we just covered,

232
00:13:07,970 --> 00:13:13,545
we can discover how far nodes are from each other and who's central and who's not.

233
00:13:13,545 --> 00:13:15,800
So, let's begin by loading up this network.

234
00:13:15,800 --> 00:13:18,230
This network is so famous that actually on network X you can

235
00:13:18,230 --> 00:13:21,505
simply load it by using the function karate club graph.

236
00:13:21,505 --> 00:13:24,015
So, that one returns this particular graph.

237
00:13:24,015 --> 00:13:27,590
Now, I'm converting the nodes labels to be integers,

238
00:13:27,590 --> 00:13:30,760
so that they match the figure I have here.

239
00:13:30,760 --> 00:13:33,185
So, that's what I'm doing with that command there,

240
00:13:33,185 --> 00:13:35,360
and then I could ask different questions about the network.

241
00:13:35,360 --> 00:13:36,535
So, in this case,

242
00:13:36,535 --> 00:13:40,565
the average shortest path between the nodes is about 2.41.

243
00:13:40,565 --> 00:13:43,815
The radius of the network is three,

244
00:13:43,815 --> 00:13:45,410
and the diameter is five.

245
00:13:45,410 --> 00:13:47,660
So, meaning there's a pair of nodes here,

246
00:13:47,660 --> 00:13:50,180
there are distance far away

247
00:13:50,180 --> 00:13:53,300
from each other and that's the largest that a distance can be.

248
00:13:53,300 --> 00:13:56,240
And then, we're going to ask who's at the center of this network?

249
00:13:56,240 --> 00:13:58,697
So, here the nodes are in the center,

250
00:13:58,697 --> 00:14:00,395
and here, I'm highlighting them in red.

251
00:14:00,395 --> 00:14:03,550
So, as you can see the instructor is in the center and

252
00:14:03,550 --> 00:14:07,400
all the other nodes are in the center also connected to the instructor,

253
00:14:07,400 --> 00:14:10,450
and they also tend to have high degrees,

254
00:14:10,450 --> 00:14:15,240
so they are easily connected to many other high degree nodes,

255
00:14:15,240 --> 00:14:21,645
and they just have small distances from them to all the other nodes in the network.

256
00:14:21,645 --> 00:14:22,940
Now, when you look at the periphery,

257
00:14:22,940 --> 00:14:24,845
these are the peripheral nodes,

258
00:14:24,845 --> 00:14:28,490
and I'm highlighting them here and in blue and as you can see,

259
00:14:28,490 --> 00:14:29,561
they're kind of on the outside,

260
00:14:29,561 --> 00:14:32,930
they tend to have small number of connections,

261
00:14:32,930 --> 00:14:39,005
and none of them are actually connected to the instructor.

262
00:14:39,005 --> 00:14:40,570
Now, you might look at this and say,

263
00:14:40,570 --> 00:14:42,215
okay, this make sense.

264
00:14:42,215 --> 00:14:44,875
But, for example, this node 34,

265
00:14:44,875 --> 00:14:48,265
was the assistant here,

266
00:14:48,265 --> 00:14:49,985
he seems pretty central.

267
00:14:49,985 --> 00:14:51,840
He's connected to a bunch of nodes,

268
00:14:51,840 --> 00:14:55,490
it seems like he could be close to all the other nodes in the graph as well.

269
00:14:55,490 --> 00:14:58,070
Why is 34 not showing up in the center?

270
00:14:58,070 --> 00:15:01,470
Well, it turns out that if you look carefully,

271
00:15:01,470 --> 00:15:05,340
node 34 has a distance four to node 17, right?

272
00:15:05,340 --> 00:15:14,605
To get from 34 to 17, you have to go 34, 32, 16, and 17, and so,

273
00:15:14,605 --> 00:15:17,235
it couldn't be in the center because the radius of the graph is

274
00:15:17,235 --> 00:15:23,000
three and this one has a node that is the distance four away from it.

275
00:15:23,000 --> 00:15:27,560
Now, it turns out that actually if this node 17 was just a bit closer,

276
00:15:27,560 --> 00:15:30,855
for example, if this node 17 was a distance three away from 34,

277
00:15:30,855 --> 00:15:33,830
then 34 would actually be in the center,

278
00:15:33,830 --> 00:15:40,505
because 34 is a distance at most three to every other node in the network.

279
00:15:40,505 --> 00:15:43,805
And so, this shows that this definition of center

280
00:15:43,805 --> 00:15:47,605
is pretty sensitive to just one node that happens to be far away, right?

281
00:15:47,605 --> 00:15:50,150
So, if you make a very small change to a graph that

282
00:15:50,150 --> 00:15:53,860
makes a particular node far further away from the other,

283
00:15:53,860 --> 00:15:58,135
you can sort of make it or break it for the node to be in the center or not.

284
00:15:58,135 --> 00:16:01,185
And in the future, we'll look at other measures of

285
00:16:01,185 --> 00:16:05,965
centrality for nodes that are less sensitive to small changes like that.

286
00:16:05,965 --> 00:16:11,510
So, to summarize, we've looked at a set of measures.

287
00:16:11,510 --> 00:16:14,990
The first one is the distance between two nodes and that was defined to be the length of

288
00:16:14,990 --> 00:16:19,350
the shortest path between the two nodes and the eccentricity of a node,

289
00:16:19,350 --> 00:16:21,620
which is defined to be the largest distance between

290
00:16:21,620 --> 00:16:24,460
the node and all the other nodes in the network.

291
00:16:24,460 --> 00:16:28,385
Both of those definitions take place at the either node level

292
00:16:28,385 --> 00:16:32,815
or at the pair of nodes level.

293
00:16:32,815 --> 00:16:37,220
We've also looked at definitions that sort of take place at the whole graph level,

294
00:16:37,220 --> 00:16:39,935
they try to characterize the distances in the whole network

295
00:16:39,935 --> 00:16:43,765
and they were the average distance between any two pair of nodes.

296
00:16:43,765 --> 00:16:46,550
The diameter which is the largest distance between any two pair of

297
00:16:46,550 --> 00:16:50,645
nodes and then the radius which was the smallest eccentricity in the graph.

298
00:16:50,645 --> 00:16:55,530
And then, we use those definitions to identify the periphery and the center of the graph,

299
00:16:55,530 --> 00:16:57,120
which is the set of nodes,

300
00:16:57,120 --> 00:17:00,630
the periphery is the sets of nodes with eccentricity equal to

301
00:17:00,630 --> 00:17:05,070
the diameter and the center is a set of nodes with eccentricity equal to the radius.

302
00:17:05,070 --> 00:17:10,000
And that's all for this video and I hope to see you in the next one.