1 00:00:08,501 --> 00:00:11,405 Today we're going to talk about another way of measuring centrality in a network. 2 00:00:11,405 --> 00:00:14,110 This one is called betweenness centrality. 3 00:00:14,110 --> 00:00:17,550 And it makes the assumption that important nodes are those who connect other nodes. 4 00:00:19,090 --> 00:00:22,080 Recall that the distance between two nodes is the length of the shortest 5 00:00:22,080 --> 00:00:23,040 path between them. 6 00:00:23,040 --> 00:00:28,195 So for example, in this network, nodes 34 and 2 have a distance 7 00:00:28,195 --> 00:00:34,285 2 because there are multiple ways of getting from node 34 to 2 in two steps. 8 00:00:34,285 --> 00:00:38,651 For example, we can take the path 34, 31, and 2. 9 00:00:38,651 --> 00:00:42,540 We can take the path 34, 14, 2. 10 00:00:42,540 --> 00:00:47,392 Or we can take the path 34, 20, and 2. 11 00:00:47,392 --> 00:00:53,505 Notice that nodes 31, 14, and 20 are in the shortest paths between node 34 and 2. 12 00:00:53,505 --> 00:00:58,080 And so, this is the kind of question we're looking at with betweeness centrality. 13 00:00:58,080 --> 00:01:01,990 What are the nodes that show up in the shortest paths between 14 00:01:01,990 --> 00:01:02,770 two different nodes? 15 00:01:05,080 --> 00:01:08,389 The way we are going to measure centrality, 16 00:01:08,389 --> 00:01:12,862 the betweenness centrality of a node v is by taking nodes s, 17 00:01:12,862 --> 00:01:17,260 t and finding all the shortest paths between nodes s and t. 18 00:01:17,260 --> 00:01:19,728 That, we're going to call sigma s, t. 19 00:01:19,728 --> 00:01:24,397 Sigma s, t is going to be the number of shortest paths between nodes s, t. 20 00:01:24,397 --> 00:01:29,185 And then, we're going to look at how many of those shortest paths actually 21 00:01:29,185 --> 00:01:31,085 contain node v in the middle? 22 00:01:31,085 --> 00:01:33,010 That's this value here. 23 00:01:33,010 --> 00:01:36,764 So, sigma s, t is the number of shortest paths between nodes s and t. 24 00:01:36,764 --> 00:01:42,180 And sigma s, t(v) is going to be the number of shortest paths between s and 25 00:01:42,180 --> 00:01:44,620 t that contain node v. 26 00:01:44,620 --> 00:01:49,441 And the betweenness centrality of node v is going to be the sum of these 27 00:01:49,441 --> 00:01:52,030 ratios overall possible s and t's. 28 00:01:52,030 --> 00:01:56,316 Actually, we're going to find that there are different ways in which we can pick 29 00:01:56,316 --> 00:01:59,923 the specific s and t's that we use to compute the centrality node v. 30 00:01:59,923 --> 00:02:02,400 But we'll talk about that next. 31 00:02:02,400 --> 00:02:07,510 Basic idea here is that a node v has high betweenness centrality 32 00:02:07,510 --> 00:02:12,086 if it shows up in many of the shortest paths of nodes s and t. 33 00:02:12,086 --> 00:02:17,750 One of the questions, one of the options that we have when we do this is whether or 34 00:02:17,750 --> 00:02:22,330 not we actually include node v as a possible node s or t. 35 00:02:23,480 --> 00:02:29,820 Let's say for example that we exclude node v from being a possible node s or t. 36 00:02:29,820 --> 00:02:30,505 So then we'll have the following. 37 00:02:30,505 --> 00:02:34,978 If we measure the betweenness centrality of node B in this simple network, 38 00:02:34,978 --> 00:02:38,580 we'll find that is the sum of three different things. 39 00:02:38,580 --> 00:02:44,340 First, we're going to have the number of shortest paths between nodes A and D. 40 00:02:44,340 --> 00:02:48,860 And there is only one shortest path between node A and D, which is the path A, 41 00:02:48,860 --> 00:02:50,460 B, and D. 42 00:02:50,460 --> 00:02:55,522 And so because B is involved in this path, then that is going to have value 1 over 1. 43 00:02:57,770 --> 00:03:01,860 Next, we look at the two nodes A, C. 44 00:03:01,860 --> 00:03:08,850 And we find that the shortest path between notes A and C is the path A, B, C. 45 00:03:08,850 --> 00:03:13,057 And of course, that involves node B, so that contributes the value of 1 over 1. 46 00:03:13,057 --> 00:03:18,098 Finally, if we look at the pair of nodes C and D, we find that its shortest 47 00:03:18,098 --> 00:03:23,653 path is just simply going from node C to D directly, since they're connected. 48 00:03:23,653 --> 00:03:28,232 And that does not involve node B, so that contributes 0. 49 00:03:28,232 --> 00:03:33,346 And so betweenness centrality of node B when we exclude B from playing 50 00:03:33,346 --> 00:03:38,472 the role of s and t, we find that it has betweenness centrality of 2. 51 00:03:38,472 --> 00:03:43,008 Now if we actually include node v as one of the endpoints here, 52 00:03:43,008 --> 00:03:47,730 then we find that there are many more options to look at, right. 53 00:03:47,730 --> 00:03:51,294 So first, we have to look at the pair of nodes A and B, 54 00:03:51,294 --> 00:03:55,277 which of course involves node B, so that contributes 1. 55 00:03:55,277 --> 00:04:00,831 We look at A, C, which has the shortest path A, B, C. 56 00:04:00,831 --> 00:04:05,692 And that involves B, therefore that contributes 1. 57 00:04:05,692 --> 00:04:09,992 A, D also passes through node B, so that contributes 1. 58 00:04:09,992 --> 00:04:14,565 B, C, well, this one involves the node B itself, so of course node B is 59 00:04:14,565 --> 00:04:19,396 involved in the shortest path from node B to C, and so that contributes 1. 60 00:04:19,396 --> 00:04:24,022 B, D same story, it's one of the endpoints, so it contributes 1. 61 00:04:24,022 --> 00:04:25,820 And then finally, C, D. 62 00:04:25,820 --> 00:04:28,620 C, D, again, they're connected to each other. 63 00:04:28,620 --> 00:04:32,090 So to get from one to the other, they don't have to pass through node B and so 64 00:04:32,090 --> 00:04:33,090 that contributes 0. 65 00:04:33,090 --> 00:04:35,676 And so when we include node B in the computation, 66 00:04:35,676 --> 00:04:39,414 we find that it has a higher betweenness centrality, in this case 5. 67 00:04:39,414 --> 00:04:43,876 We'll find that when we use network x to compute this, 68 00:04:43,876 --> 00:04:47,562 we'll have the option of either including or 69 00:04:47,562 --> 00:04:52,717 excluding the node as one of the endpoints in the pair of nodes. 70 00:04:52,717 --> 00:04:56,750 Now, here we have another concern, which is that sometimes some pairs of nodes 71 00:04:56,750 --> 00:05:00,495 are actually not connected to each other, they cannot reach each other. 72 00:05:00,495 --> 00:05:05,020 So what happens to the computation when we have this case? 73 00:05:05,020 --> 00:05:08,444 Again, this tends to happen more often in graphs that are directed. 74 00:05:08,444 --> 00:05:10,176 And so let's look at this example. 75 00:05:10,176 --> 00:05:15,202 Note here that node D has no nodes that are actually pointing to it. 76 00:05:15,202 --> 00:05:17,647 So actually, no node can actually reach node D. 77 00:05:17,647 --> 00:05:23,825 And so how do we compute this given that no node can actually reach D? 78 00:05:23,825 --> 00:05:27,927 If we were simply to apply the definition as we stated it and 79 00:05:27,927 --> 00:05:32,110 we actually include pairs for example A, D, then sigma A, 80 00:05:32,110 --> 00:05:36,653 D would be 0 because they're no shortest paths between A and D. 81 00:05:36,653 --> 00:05:40,460 And we have that sigma A, D in the definition a=is in the denominator. 82 00:05:40,460 --> 00:05:44,970 And so this would make this undefined. 83 00:05:44,970 --> 00:05:47,600 And so, we have to fix that in some way. 84 00:05:48,890 --> 00:05:53,975 And what we do is that we simply only consider the nodes that actually have at 85 00:05:53,975 --> 00:05:59,156 least one shortest path between them when we're considering nodes s and t. 86 00:05:59,156 --> 00:06:03,250 So, in this case, what is there betweenness centrality of node B? 87 00:06:03,250 --> 00:06:07,176 Let's say we're not including node B in the computation as one of the endpoints. 88 00:06:07,176 --> 00:06:11,837 Well, then we have to see which ones are the nodes that actually have at 89 00:06:11,837 --> 00:06:14,449 least one shortest path between them. 90 00:06:14,449 --> 00:06:16,109 And we'll use those in the computation. 91 00:06:16,109 --> 00:06:21,490 So A, C has a shortest path, thus A,B, C. 92 00:06:21,490 --> 00:06:26,905 And B involved in that, so that it contributes 1. 93 00:06:26,905 --> 00:06:35,700 C, A, C can reach A in just one step by connecting directly to it. 94 00:06:35,700 --> 00:06:38,588 That does not involve node B, so that contributes 0 to the computation. 95 00:06:38,588 --> 00:06:43,041 D, C, again, they're connected without including B, so 96 00:06:43,041 --> 00:06:46,371 that's contributes 0 to the computation. 97 00:06:46,371 --> 00:06:51,062 And then D to A, that has the shortest path D, C, 98 00:06:51,062 --> 00:06:54,387 A, which does not involve node B. 99 00:06:54,387 --> 00:06:57,246 And therefore, it contributes 0 to the computation. 100 00:06:57,246 --> 00:07:02,037 Notice that you can also go from D to A passing through B. 101 00:07:02,037 --> 00:07:04,067 You can go D, B, C, A. 102 00:07:04,067 --> 00:07:07,940 But that is a longer path, so it's not the shortest path. 103 00:07:07,940 --> 00:07:10,552 And so B is not involved in the shortest path between D and A. 104 00:07:10,552 --> 00:07:15,090 And so in this case, node B has a centrality of 1. 105 00:07:17,270 --> 00:07:18,652 Let's look at the same question for node C. 106 00:07:18,652 --> 00:07:23,423 And so again, we have to look at all the pairs of nodes that actually have 107 00:07:23,423 --> 00:07:26,100 a shortest path between them. 108 00:07:26,100 --> 00:07:28,107 And we're not including C as one of the endpoints. 109 00:07:28,107 --> 00:07:33,302 And so the first one is A, B, which there is a direct connection between them, 110 00:07:33,302 --> 00:07:36,553 and does not involve C, so that contributes 0. 111 00:07:36,553 --> 00:07:41,456 B to A, the shortest path from B to A is B, C, A. 112 00:07:41,456 --> 00:07:46,420 And that involves node C so it contributes 1 to the centrality of C. 113 00:07:46,420 --> 00:07:51,605 There's D, B, they're directly connected, so that contributes 0. 114 00:07:51,605 --> 00:07:54,542 And then there is D, A. 115 00:07:54,542 --> 00:07:59,132 And again the path from D to A, the shortest path passes through node C, so 116 00:07:59,132 --> 00:08:01,734 that contributes 1 to the computation. 117 00:08:01,734 --> 00:08:06,453 And overall we've find that node C has a betweenness centrality of 2. 118 00:08:09,649 --> 00:08:12,550 So, so far we haven't talked about normalizing the betweenness 119 00:08:12,550 --> 00:08:13,614 centrality in any way. 120 00:08:13,614 --> 00:08:18,156 And the problem with this is that nodes that are in graphs that have 121 00:08:18,156 --> 00:08:23,029 a larger number of nodes will tend to have higher centrality than nodes 122 00:08:23,029 --> 00:08:27,099 of graphs that are smaller in terms of the number of nodes. 123 00:08:27,099 --> 00:08:30,647 That's simply because in large graphs, there are more nodes, s and t, 124 00:08:30,647 --> 00:08:33,340 to choose from to compute the centrality of the nodes. 125 00:08:33,340 --> 00:08:37,635 And so for example, if we look at these friendship network in the 34 126 00:08:37,635 --> 00:08:42,078 person karate club, the nodes there are going to have lower centrality 127 00:08:42,078 --> 00:08:45,731 than the nodes in this larger network of 2200 people. 128 00:08:45,731 --> 00:08:50,479 And so, sometimes if we want to compare betweenness centrality across networks, 129 00:08:50,479 --> 00:08:52,140 it's useful to normalize. 130 00:08:53,140 --> 00:08:57,304 And the way we normalize is simply by dividing the betweenness centrality of our 131 00:08:57,304 --> 00:09:00,536 node v by the number of possible pairs of nodes in the network, 132 00:09:00,536 --> 00:09:01,737 not including node v. 133 00:09:01,737 --> 00:09:03,486 So for undirected graphs, 134 00:09:03,486 --> 00:09:08,870 you would divide them betweenness centrality of v by (N-1)(N-2) over 2. 135 00:09:08,870 --> 00:09:11,670 That's the number of pairs that you could have in an undirected 136 00:09:11,670 --> 00:09:15,760 graph excluding the node that you're currently looking at. 137 00:09:16,830 --> 00:09:21,350 And in directed graphs, you have twice the number of pairs because for 138 00:09:21,350 --> 00:09:24,639 any pair s, t, you could have a path from s to t, but 139 00:09:24,639 --> 00:09:27,642 also a potentially different path from t to s. 140 00:09:27,642 --> 00:09:33,623 So you would divide the betweenness centrality of node v by (N-1)(N-2). 141 00:09:33,623 --> 00:09:38,086 And in network x, you can use the function betweenness 142 00:09:38,086 --> 00:09:43,335 centrality to find the centrality of every node in the network. 143 00:09:43,335 --> 00:09:47,190 And you have the various options that we've discussed here. 144 00:09:47,190 --> 00:09:48,976 So for example, you can choose to normalize or not. 145 00:09:48,976 --> 00:09:52,104 And you can also choose the question of the endpoints, 146 00:09:52,104 --> 00:09:56,320 whether you use the node that you're computing the centrality of as one of 147 00:09:56,320 --> 00:09:59,393 the endpoints in the computation of its centrality. 148 00:09:59,393 --> 00:10:05,430 So you can choose to do this in any way you want here. 149 00:10:05,430 --> 00:10:09,947 So for example, if we look at the karate club and look at betweenness centrality, 150 00:10:09,947 --> 00:10:14,593 compute the betweenness centrality of all the nodes and then find the five largest, 151 00:10:14,593 --> 00:10:17,800 the five nodes with the largest betweenness centrality, 152 00:10:17,800 --> 00:10:21,417 we find that these are the nodes 1, 34, 33, 3, and 32. 153 00:10:21,417 --> 00:10:26,149 Now one of the issues with betweenness centrality is that it can be 154 00:10:26,149 --> 00:10:28,741 very computationally expensive. 155 00:10:28,741 --> 00:10:31,683 Depending on the specific algorithm you're using, 156 00:10:31,683 --> 00:10:35,288 this computation can take up to order number of nodes cubed time. 157 00:10:35,288 --> 00:10:39,140 And just for us to get some idea about this, 158 00:10:39,140 --> 00:10:43,956 look at the network of friendship, marital tie, and 159 00:10:43,956 --> 00:10:47,984 family tie among these 2,200 people. 160 00:10:47,984 --> 00:10:52,794 This is a relatively small network, yet when you look at the number pairs of nodes 161 00:10:52,794 --> 00:10:57,059 that it can have, you have a new order of 4.8 million pairs of nodes. 162 00:10:57,059 --> 00:11:01,427 And so even small networks have lots and lots and lots of pairs of nodes. 163 00:11:01,427 --> 00:11:04,307 And so computing the betweenness centrality of these networks becomes 164 00:11:04,307 --> 00:11:05,124 pretty expensive. 165 00:11:05,124 --> 00:11:09,690 So one of the things that you can do is rather than the computing betweenness 166 00:11:09,690 --> 00:11:13,821 centrality based on all the nodes s and t, all the possible nodes s, 167 00:11:13,821 --> 00:11:18,533 t in the network, you can approximate it by just looking at a sample of nodes, 168 00:11:18,533 --> 00:11:20,816 instead of looking at all the nodes. 169 00:11:20,816 --> 00:11:26,910 And in network x, you can do this by using the parameter k 170 00:11:26,910 --> 00:11:31,070 that says how many nodes you should use to compute the betweenness centrality. 171 00:11:31,070 --> 00:11:35,633 And so here, I'm computing the betweenness centrality of the nodes in 172 00:11:35,633 --> 00:11:40,135 the karate club network using only 10 nodes rather than 34 nodes. 173 00:11:40,135 --> 00:11:42,342 And so this gives you an approximation for 174 00:11:42,342 --> 00:11:45,504 what the betweenness centrality of the nodes actually is. 175 00:11:45,504 --> 00:11:49,956 And if I look at the five nodes with the largest 176 00:11:49,956 --> 00:11:54,059 approximated betweenness centrality, 177 00:11:54,059 --> 00:11:59,931 we find that these are nodes 1, 34, 32, 3, and 2. 178 00:11:59,931 --> 00:12:05,163 So we get almost exactly the same list as we did when we didn't approximate, 179 00:12:05,163 --> 00:12:10,070 when we find the actual betweenness centrality, except that we now get 180 00:12:10,070 --> 00:12:14,270 2 as one of the top five and we lose 33 as one of the top five. 181 00:12:14,270 --> 00:12:19,070 So it gives us something that is close to the actual. 182 00:12:19,070 --> 00:12:21,900 But of course, there can be some differences since now 183 00:12:21,900 --> 00:12:25,666 you're only using 10 rather than 34 nodes to compute the centrality 184 00:12:28,828 --> 00:12:33,703 The other thing that sometimes is useful is that sometimes you rather compute 185 00:12:33,703 --> 00:12:37,978 the betweenness centrality based on two subgroups in the network, 186 00:12:37,978 --> 00:12:41,660 not necessarily looking at all potential pairs of nodes. 187 00:12:41,660 --> 00:12:46,760 But you maybe really care about two groups communicating with each other. 188 00:12:46,760 --> 00:12:51,013 So you want to find what are the most important nodes in this network that tend 189 00:12:51,013 --> 00:12:54,726 to show up in the shortest paths between a group of source nodes and 190 00:12:54,726 --> 00:12:56,158 a group of target nodes? 191 00:12:56,158 --> 00:13:00,941 And so to do this in network x, you can use the function betweenness centrality 192 00:13:00,941 --> 00:13:05,721 subset, in which you pass the graph and then you pass the set of source nodes and 193 00:13:05,721 --> 00:13:07,264 the set of target nodes. 194 00:13:07,264 --> 00:13:09,823 And you can choose to normalize or not. 195 00:13:09,823 --> 00:13:10,797 In this case, I'm normalizing. 196 00:13:10,797 --> 00:13:14,795 And I'm just sort of here selecting two groups of nodes, pretty arbitrarily, 197 00:13:14,795 --> 00:13:16,834 just to kind of give you an example here. 198 00:13:16,834 --> 00:13:21,359 So we're going to see, based on these source nodes and target nodes, 199 00:13:21,359 --> 00:13:24,180 what are the most important nodes? 200 00:13:24,180 --> 00:13:27,279 And again, here what the meaning of these source nodes and 201 00:13:27,279 --> 00:13:31,389 target nodes is that when we select the nodes s, t to compute the centrality of 202 00:13:31,389 --> 00:13:35,437 all the nodes, we're always going to choose s from the set of source nodes, 203 00:13:35,437 --> 00:13:39,644 and t from the set of target nodes, rather than selecting all possible pairs. 204 00:13:39,644 --> 00:13:44,566 And so when we find the top nodes here with the highest betweenness centrality 205 00:13:44,566 --> 00:13:48,655 in this setup, with these source nodes and these target nodes, 206 00:13:48,655 --> 00:13:53,667 we find that nodes 1, 34, 3, 33, and 9 are the most important nodes. 207 00:13:53,667 --> 00:13:58,039 Now notice that these tend to be the nodes that also have highest centrality when you 208 00:13:58,039 --> 00:14:01,485 don't restrict to source and subset of source and target nodes. 209 00:14:01,485 --> 00:14:03,286 But there are some changes. 210 00:14:03,286 --> 00:14:07,225 So for example, we had not seen that node number 9 was important before. 211 00:14:07,225 --> 00:14:11,213 Now we see that it's important in connecting this particular sets of nodes. 212 00:14:15,664 --> 00:14:20,016 The other thing you can do is you can define the betweenness centrality of 213 00:14:20,016 --> 00:14:23,652 an edge, rather than the betweenness centrality of a node, 214 00:14:23,652 --> 00:14:28,026 in much the same way that you defined betweenness centrality for a node. 215 00:14:28,026 --> 00:14:31,663 So if you're defining the betweenness centrality of an edge, 216 00:14:31,663 --> 00:14:34,554 you're going to again look at pairs of nodes as t. 217 00:14:34,554 --> 00:14:41,255 And you're going to take the ratio of the number of shortest paths in going from 218 00:14:41,255 --> 00:14:48,071 s to t that involve the edge e divided by all shortest paths between nodes s and t. 219 00:14:48,071 --> 00:14:50,557 So it is the exact same definition. 220 00:14:50,557 --> 00:14:54,190 But now rather than asking is this particular 221 00:14:54,190 --> 00:14:58,394 node showing up in the shortest path between s and t, 222 00:14:58,394 --> 00:15:04,050 we are asking is this particular edge showing up in the shortest path? 223 00:15:04,050 --> 00:15:08,624 And in network x, you can use the function edge betweenness centrality to find 224 00:15:08,624 --> 00:15:12,170 the betweenness centrality of all the edges in the network. 225 00:15:13,224 --> 00:15:18,620 And so here, if we find the top five edges with the highest betweenness centrality, 226 00:15:18,620 --> 00:15:20,250 we find that these are it. 227 00:15:20,250 --> 00:15:23,893 So they all tend to be edges that are connected to node number 1, 228 00:15:23,893 --> 00:15:28,485 which if you remember, node number 1 here is the instructor of the karate club. 229 00:15:30,202 --> 00:15:34,510 In the same way that you could define a specific set of source nodes and 230 00:15:34,510 --> 00:15:39,040 a specific set of target nodes, you can do the same thing when you compute 231 00:15:39,040 --> 00:15:43,887 the edge betweenness centrality rather than node betweenness centrality. 232 00:15:43,887 --> 00:15:47,654 And for this, you can use the function edge betweenness centrality subset. 233 00:15:47,654 --> 00:15:52,516 And you pass again the graph and the source nodes and the target nodes. 234 00:15:52,516 --> 00:15:56,888 And if we find here the top five edges with the highest betweenness 235 00:15:56,888 --> 00:16:01,421 centrality for this particular choice of source and target nodes, 236 00:16:01,421 --> 00:16:04,855 we find that these are the the most important ones. 237 00:16:04,855 --> 00:16:10,256 And notice that most of them tend to be edges that go from inside the target or 238 00:16:10,256 --> 00:16:13,130 inside the source set to the outside. 239 00:16:13,130 --> 00:16:17,300 And that make sense because these are the ones that actually end 240 00:16:17,300 --> 00:16:20,820 up showing up in the shortest paths between the source and the targets. 241 00:16:22,040 --> 00:16:26,277 And they also tend to be connected to very important nodes in the network, namely 242 00:16:26,277 --> 00:16:30,512 node number 1, which is the instructor of the karate club and node number 34, 243 00:16:30,512 --> 00:16:34,600 which is the instructor of the new karate club after these club splits in two. 244 00:16:37,559 --> 00:16:41,527 So in summary, we say that betweenness centrality makes the assumption that 245 00:16:41,527 --> 00:16:44,650 important nodes tend to connect the other nodes. 246 00:16:44,650 --> 00:16:47,966 And this is the formula that we use to compute it. 247 00:16:47,966 --> 00:16:51,844 In general, it's the sum of the fraction of the number 248 00:16:51,844 --> 00:16:56,398 of shortest paths that involve a particular node v divided by all 249 00:16:56,398 --> 00:17:00,301 the possible shortest paths between the nodes s and t. 250 00:17:00,301 --> 00:17:04,725 We talked about normalizing this, especially if we're comparing betweenness 251 00:17:04,725 --> 00:17:07,989 centrality among different networks of different sizes. 252 00:17:07,989 --> 00:17:10,265 So we divide by the number of pair of nodes. 253 00:17:10,265 --> 00:17:15,480 We also talked about approximating this because sometimes we're unable 254 00:17:15,480 --> 00:17:20,200 compute it exactly because it can be computationally expensive. 255 00:17:20,200 --> 00:17:25,320 So we can approximate it by selecting a subset of nodes rather than all the nodes. 256 00:17:25,320 --> 00:17:27,336 And we showed you how to do this in network x. 257 00:17:27,336 --> 00:17:31,686 We also talked about choosing specific sets of target nodes and 258 00:17:31,686 --> 00:17:36,630 specific sets of source nodes rather than using all possible pairs. 259 00:17:36,630 --> 00:17:41,117 That's if you have a particular sets of nodes that you care about and 260 00:17:41,117 --> 00:17:44,660 that you want to know, who are the important nodes that 261 00:17:44,660 --> 00:17:47,899 are connecting nodes in this two specific sets. 262 00:17:47,899 --> 00:17:51,464 And then we talked about how we can generalize this a bit more and 263 00:17:51,464 --> 00:17:56,115 talked about the betweenness centrality of not only the nodes but also the edges. 264 00:17:56,115 --> 00:17:59,472 Much in the same way that we define it for nodes, we can also define for edge. 265 00:17:59,472 --> 00:18:02,570 This is all for this video. 266 00:18:02,570 --> 00:18:04,640 Thank you for watching and I see you next time.