1 00:00:07,560 --> 00:00:13,335 Hello. Today, we're going to talk about how to find important nodes in a network. 2 00:00:13,335 --> 00:00:17,705 Recall these friendship network among 34 people in a karate club. 3 00:00:17,705 --> 00:00:19,930 Based on the structure of this network, 4 00:00:19,930 --> 00:00:23,955 which would you say are the five most important nodes in this network? 5 00:00:23,955 --> 00:00:28,580 Of course, there are many ways of thinking about this question and we're going to start 6 00:00:28,580 --> 00:00:30,410 thinking about different ways in which you could 7 00:00:30,410 --> 00:00:32,905 imagine answering this particular question. 8 00:00:32,905 --> 00:00:36,650 So, one way to answer the question would be to say, 9 00:00:36,650 --> 00:00:40,110 well, nodes who have a very high degree, 10 00:00:40,110 --> 00:00:43,080 nodes who have lots of friends are important nodes. 11 00:00:43,080 --> 00:00:45,179 And if we use that definition then we'll find that 12 00:00:45,179 --> 00:00:47,795 the five most important nodes are nodes 34, 13 00:00:47,795 --> 00:00:49,175 1, 33, 3 and 2. 14 00:00:49,175 --> 00:00:52,460 These nodes right here. 15 00:00:52,460 --> 00:00:55,420 There are other ways in which you can imagine answering this question. 16 00:00:55,420 --> 00:00:58,135 Another way would be to say that nodes who are important 17 00:00:58,135 --> 00:01:01,043 are nodes who are very close to other nodes and network, 18 00:01:01,043 --> 00:01:04,185 nodes who have high proximity to other nodes and network. 19 00:01:04,185 --> 00:01:06,130 And if we use that definition, 20 00:01:06,130 --> 00:01:09,825 then the five most important nodes in the network would be notes 1, 21 00:01:09,825 --> 00:01:12,600 3, 34, 32 and 9. 22 00:01:12,600 --> 00:01:16,960 So, instead of having node 33 we'll have node 9 and then instead of having 23 00:01:16,960 --> 00:01:21,845 node 2 we'll have node 32 and all the other ones stay the same. 24 00:01:21,845 --> 00:01:25,830 Yet, another way of thinking about importance would be to say that nodes who are 25 00:01:25,830 --> 00:01:30,345 important are nodes who tend to connect other nodes into network. 26 00:01:30,345 --> 00:01:32,760 And so, we could imagine measuring importance by 27 00:01:32,760 --> 00:01:37,020 the fraction of shortest paths that pass through a particular node. 28 00:01:37,020 --> 00:01:38,085 And if we do that, 29 00:01:38,085 --> 00:01:39,330 if we define in that way, 30 00:01:39,330 --> 00:01:44,140 we find that the five most important nodes in the network are nodes 1,34, 31 00:01:44,140 --> 00:01:46,685 33, 3 and 32. 32 00:01:46,685 --> 00:01:49,200 So, instead of having node number 9, 33 00:01:49,200 --> 00:01:51,330 we'll have node number 33 in 34 00:01:51,330 --> 00:01:56,150 the top five and every all the other nodes will stay the same. 35 00:01:56,150 --> 00:01:57,350 So, at this point, 36 00:01:57,350 --> 00:02:04,850 these three definitions of importance are very informal and the goal of 37 00:02:04,850 --> 00:02:08,120 this video and the following videos is going to be to get 38 00:02:08,120 --> 00:02:13,440 a more precise definitions of how to measure importance in a network. 39 00:02:13,440 --> 00:02:17,090 This general topic is called Network Centrality and these 40 00:02:17,090 --> 00:02:19,490 centrality measures are the ones that allows us to 41 00:02:19,490 --> 00:02:22,530 find the most important nodes in a particular network. 42 00:02:22,530 --> 00:02:26,480 And the cases in which we want to use these techniques is when for example, 43 00:02:26,480 --> 00:02:30,530 sometimes we're interested in finding who the influential nodes in a social network are, 44 00:02:30,530 --> 00:02:34,880 which are the nodes that are very good at disseminating information to many other nodes, 45 00:02:34,880 --> 00:02:36,110 or on the other hand, 46 00:02:36,110 --> 00:02:38,120 which are the nodes that are good at preventing 47 00:02:38,120 --> 00:02:42,760 sort of bad behaviors or epidemics from spreading on a social network? 48 00:02:42,760 --> 00:02:44,625 These can be used in other networks as well, 49 00:02:44,625 --> 00:02:47,090 so we can use a centrality measures to find 50 00:02:47,090 --> 00:02:50,660 hubs in a transportation network or important pages on 51 00:02:50,660 --> 00:02:53,770 the web or more generally these measure 52 00:02:53,770 --> 00:02:57,345 allows us to find nodes that prevent the network from breaking up. 53 00:02:57,345 --> 00:02:59,330 Nodes that if we were to remove them, 54 00:02:59,330 --> 00:03:02,630 they would cause the network from they would cause the network 55 00:03:02,630 --> 00:03:06,865 to fracture and break up into different components. 56 00:03:06,865 --> 00:03:09,890 Here's a list of centrality measures that are commonly used. 57 00:03:09,890 --> 00:03:13,550 We're going to be talking about some of these in this course and in this video, 58 00:03:13,550 --> 00:03:19,174 we're going to be focusing on degree centrality and closeness centrality. 59 00:03:19,174 --> 00:03:24,425 So, degree centrality makes the assumption that important nodes have many connections. 60 00:03:24,425 --> 00:03:28,240 This is the most basic way in which you could define importance or centrality. 61 00:03:28,240 --> 00:03:31,105 Simply, that nodes who have lots of neighbors, 62 00:03:31,105 --> 00:03:33,232 lots of friends are very important, 63 00:03:33,232 --> 00:03:35,470 and it makes sense right? 64 00:03:35,470 --> 00:03:37,600 Of course, depending on the type of network you have 65 00:03:37,600 --> 00:03:39,880 you would have to use different types of degree. 66 00:03:39,880 --> 00:03:42,850 So, if you have an undirected network you can simply use that degree, 67 00:03:42,850 --> 00:03:47,425 but if you have a directed network then you have to choose between using in-degree, 68 00:03:47,425 --> 00:03:50,555 or out-degree, or a combination of both. 69 00:03:50,555 --> 00:03:53,780 So, let's get into exactly how we would define this. 70 00:03:53,780 --> 00:03:58,930 So, we'll say that the degree centrality of a node V is going to be the ratio 71 00:03:58,930 --> 00:04:05,340 between its degree and the number of nodes in the graph minus one. 72 00:04:05,340 --> 00:04:10,420 So, in this case a node would have a centrality of one if it's connected to 73 00:04:10,420 --> 00:04:12,990 every single node in the network and 74 00:04:12,990 --> 00:04:16,685 a centrality of zero if it's connected to no node in the network. 75 00:04:16,685 --> 00:04:18,850 And so, this measure goes between zero and one, 76 00:04:18,850 --> 00:04:22,530 with one being the case where you're most connected. 77 00:04:22,530 --> 00:04:24,490 Let's see how we can use network X to 78 00:04:24,490 --> 00:04:26,950 find the degree centrality of nodes in this network. 79 00:04:26,950 --> 00:04:30,220 So, first let me load up the karate club graph and then let me 80 00:04:30,220 --> 00:04:34,195 convert the labels of the nodes so that they match what we see here in this figure. 81 00:04:34,195 --> 00:04:36,065 And now, we can use the function degree centrality 82 00:04:36,065 --> 00:04:40,385 to measure the centrality of all the nodes in the network. 83 00:04:40,385 --> 00:04:42,880 And so here, these returns a dictionary 84 00:04:42,880 --> 00:04:46,150 of centralities of every node and we can for example, 85 00:04:46,150 --> 00:04:51,820 look at the degree centrality of node number 34 which is 0.515 and that's 86 00:04:51,820 --> 00:04:58,221 because node 34 has 17 connections and there are 34 nodes in the network, 87 00:04:58,221 --> 00:05:00,775 so that is 17 or 33. 88 00:05:00,775 --> 00:05:10,310 The Degree Centrality of note 33 is 0.364 and that is 12 over 33. 89 00:05:10,310 --> 00:05:12,405 Now, like I said in directed networks, 90 00:05:12,405 --> 00:05:16,740 we have the choice of using the in-degree centrality or the out-degree centrality 91 00:05:16,740 --> 00:05:21,090 of a node and everything else is defined in the same way. 92 00:05:21,090 --> 00:05:24,540 So, the in-degree centrality of a node V is going to 93 00:05:24,540 --> 00:05:29,100 be its in-degree divided by the number of nodes in the graph minus one. 94 00:05:29,100 --> 00:05:33,630 And we can use the function in-degree centrality network X to find 95 00:05:33,630 --> 00:05:38,275 the in-degree centrality of all the nodes in a directed network. 96 00:05:38,275 --> 00:05:44,830 And so in this case, A will have in-degree of 0.143 which is two or 14. 97 00:05:44,830 --> 00:05:49,680 There are 15 nodes in this network and L will have a in-degree centrality 98 00:05:49,680 --> 00:05:57,300 of 0.214 which is three over 14 and that's because node L has an in-degree of three. 99 00:05:57,300 --> 00:06:03,060 And the very same way we can define not using the out-degree instead of 100 00:06:03,060 --> 00:06:06,570 the in-degree centrality using the function out-degree centrality 101 00:06:06,570 --> 00:06:11,120 and the out-degree centrality of A is 0.214, 102 00:06:11,120 --> 00:06:18,315 because it has an out-degree of three and the out-degree centrality of node L is 0.071, 103 00:06:18,315 --> 00:06:21,010 because L has an out-degree of one. 104 00:06:21,010 --> 00:06:24,980 Another way of measuring centrality is what we call closeness centrality. 105 00:06:24,980 --> 00:06:28,830 And the assumption here is that nodes that are important are going to 106 00:06:28,830 --> 00:06:33,740 be a short distance away from all other nodes in the network. 107 00:06:33,740 --> 00:06:38,010 Recall that we measure distance between two nodes by looking at the shortest path, 108 00:06:38,010 --> 00:06:40,985 the length of the shortest path between them. 109 00:06:40,985 --> 00:06:44,215 And so, the way we're going to define the closeness centrality of 110 00:06:44,215 --> 00:06:47,660 node V is going to be by taking the ratio of the number of 111 00:06:47,660 --> 00:06:50,780 nodes in the network minus one divided 112 00:06:50,780 --> 00:06:54,325 by the sum over all the other nodes in the network, 113 00:06:54,325 --> 00:06:57,395 and the distance between node V and those nodes. 114 00:06:57,395 --> 00:07:03,035 So, that's the sum and the denominator in the definition of centrality. 115 00:07:03,035 --> 00:07:07,150 Now, so let's say that we want to use network X to find 116 00:07:07,150 --> 00:07:10,650 the closeness centrality of this node 32. 117 00:07:10,650 --> 00:07:13,840 We can use the function closeness centrality which returns the dictionary 118 00:07:13,840 --> 00:07:17,535 of the centrality of the closeness centrality of all the nodes. 119 00:07:17,535 --> 00:07:24,540 And here, we find node 32 has a closeness centrality of 0.541. 120 00:07:24,540 --> 00:07:31,385 So, using the definition of closeness centrality let's see how this 0.541 comes about. 121 00:07:31,385 --> 00:07:34,180 So, first of all let me look at the sum of the length of 122 00:07:34,180 --> 00:07:39,190 the shortest path from node number 32 to all the other nodes in the network. 123 00:07:39,190 --> 00:07:41,560 I'm using here the shortest path length function, 124 00:07:41,560 --> 00:07:42,670 which you've seen before, 125 00:07:42,670 --> 00:07:45,160 which gives you the length of all the shortest path from 126 00:07:45,160 --> 00:07:49,975 the node number 32 to all the other nodes and that sum here is 61. 127 00:07:49,975 --> 00:07:54,040 And so, then if we take the number of nodes in the graph minus 128 00:07:54,040 --> 00:07:58,475 one divided by 61 that's how we get this 0.541. 129 00:07:58,475 --> 00:08:01,700 Of course, we're making 130 00:08:01,700 --> 00:08:06,420 the implicit assumption that all the nodes can actually reach all the other nodes, 131 00:08:06,420 --> 00:08:08,205 but of course, this is not always the case. 132 00:08:08,205 --> 00:08:11,000 In particular, when we have directed graphs, 133 00:08:11,000 --> 00:08:14,210 this is often not the case and even for undirected graphs you can have 134 00:08:14,210 --> 00:08:16,580 multiple connected components and you 135 00:08:16,580 --> 00:08:19,580 can have it so that some nodes cannot reach other nodes. 136 00:08:19,580 --> 00:08:22,040 And so, what happens, how do we measure closeness centrality 137 00:08:22,040 --> 00:08:25,018 when a node cannot actually reach all the other nodes? 138 00:08:25,018 --> 00:08:27,000 Let's take this example, right. 139 00:08:27,000 --> 00:08:30,510 So, node L here can only reach node M. So, 140 00:08:30,510 --> 00:08:31,520 how do we measure its closeness centrality? 141 00:08:31,520 --> 00:08:34,115 We have a couple of options here. 142 00:08:34,115 --> 00:08:37,920 And the first option we can simply only consider the nodes 143 00:08:37,920 --> 00:08:42,720 that L can actually reach in order to measure its closeness centrality. 144 00:08:42,720 --> 00:08:47,010 So, the way this would work is that we define this set RL to 145 00:08:47,010 --> 00:08:51,370 be the set of nodes that L can actually reach and we define 146 00:08:51,370 --> 00:08:57,915 the closeness centrality of L to be the ratio of the number of nodes that L can 147 00:08:57,915 --> 00:09:00,930 reach divided by the sum of 148 00:09:00,930 --> 00:09:05,665 the distances from L to all the nodes that L can actually reach. 149 00:09:05,665 --> 00:09:07,380 And so, for node L here, 150 00:09:07,380 --> 00:09:09,645 this would be simply one, 151 00:09:09,645 --> 00:09:14,100 because L can only reach node M so RL here is just 152 00:09:14,100 --> 00:09:21,415 the set M is just the node M and L can reach M in just one step. 153 00:09:21,415 --> 00:09:24,360 So, the closeness centrality of L here, 154 00:09:24,360 --> 00:09:25,500 would be one over one, 155 00:09:25,500 --> 00:09:30,885 which is one and this is the highest possible centrality a node can have in a network, 156 00:09:30,885 --> 00:09:35,430 which seems a little bit problematic because as node L can only reach 157 00:09:35,430 --> 00:09:37,110 one node and we're saying that it has 158 00:09:37,110 --> 00:09:40,900 the highest possible centrality than any node can have, 159 00:09:40,900 --> 00:09:44,850 this seems an intuitive, right? 160 00:09:44,850 --> 00:09:47,250 So, here's where option 2 comes in. 161 00:09:47,250 --> 00:09:50,885 In option 2, we again only consider the nodes that L can reach, 162 00:09:50,885 --> 00:09:55,270 but then, we normalize by the fraction of nodes that L can reach. 163 00:09:55,270 --> 00:09:59,170 So, the way this looks here is that when we compute the closeness centrality of L, 164 00:09:59,170 --> 00:10:02,590 we have the same ratio of RL over the sum. 165 00:10:02,590 --> 00:10:05,845 But now, we're going to multiply that ratio, 166 00:10:05,845 --> 00:10:09,970 the fraction of nodes that L can reach, 167 00:10:09,970 --> 00:10:14,320 RL, divided by the number of nodes in the graph minus one. 168 00:10:14,320 --> 00:10:17,570 So basically, we're normalizing by the fraction of nodes that L can reach. 169 00:10:17,570 --> 00:10:20,125 And so, if L cannot reach many nodes we're going to be 170 00:10:20,125 --> 00:10:24,335 multiplying these other fraction by a very small number. 171 00:10:24,335 --> 00:10:29,140 And so, in this case if we do that we find that L has a closeness centrality of 0. 172 00:10:29,140 --> 00:10:35,355 071 which is more reasonable than defined to be one. 173 00:10:35,355 --> 00:10:39,915 One thing to note here is that in this new definition when we're normalizing, 174 00:10:39,915 --> 00:10:44,550 we're not changing the definition of closeness centrality when the graph is connected, 175 00:10:44,550 --> 00:10:46,810 where in every node can reach every other node. 176 00:10:46,810 --> 00:10:51,930 That's because when that's the case RL for node L would equal M minus 177 00:10:51,930 --> 00:10:54,450 one and this formula that you see 178 00:10:54,450 --> 00:10:58,075 here would be the exact same formula that we had before. 179 00:10:58,075 --> 00:11:00,060 So, we're not changing the definition. 180 00:11:00,060 --> 00:11:04,995 This definition can still apply even if the graph is completely connected. 181 00:11:04,995 --> 00:11:10,415 Okay. So, how can we use network X to find the closeness centrality? 182 00:11:10,415 --> 00:11:12,780 Well, we can use the function closeness centrality. 183 00:11:12,780 --> 00:11:17,735 And here, you get the option of normalizing or not normalizing. 184 00:11:17,735 --> 00:11:19,110 And so for example, if we choose not to 185 00:11:19,110 --> 00:11:23,430 normalize then the closeness centrality of node L would be one, 186 00:11:23,430 --> 00:11:24,855 as we saw before, 187 00:11:24,855 --> 00:11:30,510 and if we choose to normalize then it's closeness centrality would be 0.071. 188 00:11:30,510 --> 00:11:33,330 So, in summary, today we talked about 189 00:11:33,330 --> 00:11:37,730 centrality measures and how they aim to find the most important nodes in the network. 190 00:11:37,730 --> 00:11:40,725 We said that there are many many different ways of defining centrality 191 00:11:40,725 --> 00:11:44,610 and today we talked about two specific ones. 192 00:11:44,610 --> 00:11:49,140 A very basic definition of degree centrality which makes 193 00:11:49,140 --> 00:11:53,649 the assumption that important nodes are those who have many many connections, 194 00:11:53,649 --> 00:11:58,320 and we use this formula to measure the centrality of a node and it's simply 195 00:11:58,320 --> 00:12:04,230 the ratio between the degree of the node and the number of nodes in the graph minus one. 196 00:12:04,230 --> 00:12:08,100 And depending on whether we have a direct or undirected graph, 197 00:12:08,100 --> 00:12:13,092 we can use the degree of the node or the in-degree or the out-degree, 198 00:12:13,092 --> 00:12:18,140 and these are the different functions that you can use in network X to apply them. 199 00:12:18,140 --> 00:12:22,200 The second centrality measure that we looked at was closeness centrality 200 00:12:22,200 --> 00:12:27,860 and the assumption that it makes is that important nodes are close to other nodes. 201 00:12:27,860 --> 00:12:32,220 And here is the general formula that we use to compute it. 202 00:12:32,220 --> 00:12:36,360 And here, we can choose to normalize or not normalize as we 203 00:12:36,360 --> 00:12:38,960 discussed and the function that we use in 204 00:12:38,960 --> 00:12:43,375 network X to compute it is the function closeness centrality. 205 00:12:43,375 --> 00:12:48,210 This is it for this video and I hope to see you next time. Thanks.