1 00:00:07,550 --> 00:00:12,125 Today, we're going to talk about connectivity in networks. 2 00:00:12,125 --> 00:00:15,480 First, we're going to talk about connectivity in undirected graphs. 3 00:00:15,480 --> 00:00:18,400 Those are the ones where the edges don't have a direction. 4 00:00:18,400 --> 00:00:22,650 An undirected graph is said to be connected if for every pair of nodes, 5 00:00:22,650 --> 00:00:24,885 there is a path between the two nodes. 6 00:00:24,885 --> 00:00:27,210 We can use the function is_connected in 7 00:00:27,210 --> 00:00:30,420 network X and give it the undirected graph as input, 8 00:00:30,420 --> 00:00:32,640 and it will tell us whether the graph is connected or not. 9 00:00:32,640 --> 00:00:34,740 In this case, this example, 10 00:00:34,740 --> 00:00:38,730 this graph is connected so it says, true, it is connected. 11 00:00:38,730 --> 00:00:41,850 However, if we were to remove a few of the edges, for example, 12 00:00:41,850 --> 00:00:43,525 if we remove A-G, A-N, 13 00:00:43,525 --> 00:00:47,910 and J-O, then the graph will become disconnected, as you can see. 14 00:00:47,910 --> 00:00:50,940 Now, we have these sort of 15 00:00:50,940 --> 00:00:54,735 three communities such that if you're in a particular community, 16 00:00:54,735 --> 00:00:58,320 you cannot find a path to a node in a different community, 17 00:00:58,320 --> 00:01:02,235 or in a different set of nodes. 18 00:01:02,235 --> 00:01:06,555 Let's try to get at this idea of communities in a more precise way. 19 00:01:06,555 --> 00:01:09,860 We're going to refer to these communities as connected components. 20 00:01:09,860 --> 00:01:13,075 So let me give you a definition of what a connected component is. 21 00:01:13,075 --> 00:01:16,095 A connected component is a subset of nodes 22 00:01:16,095 --> 00:01:19,620 such that there are two conditions this set of nodes satisfy. 23 00:01:19,620 --> 00:01:24,750 First, every node in the subset has to have a path to every other node in the subset. 24 00:01:24,750 --> 00:01:26,715 That's condition number one. 25 00:01:26,715 --> 00:01:30,210 Condition number two would say that no other node outside of 26 00:01:30,210 --> 00:01:33,750 the subset has a path to any node inside the subset. 27 00:01:33,750 --> 00:01:35,925 So condition two kind of makes sure that 28 00:01:35,925 --> 00:01:38,370 you get all the nodes that you could possibly can 29 00:01:38,370 --> 00:01:43,110 so that every node in this subset has a connection to every other node in the subset, 30 00:01:43,110 --> 00:01:46,950 not a subset of the subset that you could potentially get. 31 00:01:46,950 --> 00:01:50,085 So let's see this through examples to make it more clear. 32 00:01:50,085 --> 00:01:52,704 Is the subset of nodes E, A, 33 00:01:52,704 --> 00:01:55,620 G, F a connected component? 34 00:01:55,620 --> 00:01:58,975 So first, let's find these nodes and so here they are. 35 00:01:58,975 --> 00:02:02,690 This is the subset of nodes we're referring to. 36 00:02:02,690 --> 00:02:07,470 And we can clearly see that this is not a connected component because the nodes, 37 00:02:07,470 --> 00:02:09,386 for example, A and F, 38 00:02:09,386 --> 00:02:10,620 cannot reach each other. 39 00:02:10,620 --> 00:02:13,100 There is no path going from A to F, 40 00:02:13,100 --> 00:02:15,605 so condition number one fails. 41 00:02:15,605 --> 00:02:18,090 Okay, let's look at another example. 42 00:02:18,090 --> 00:02:20,165 Is the subset of nodes N, 43 00:02:20,165 --> 00:02:21,870 O, K a connected component? 44 00:02:21,870 --> 00:02:23,855 All right, these are the nodes. 45 00:02:23,855 --> 00:02:26,360 Now in this case, condition number one is actually met. 46 00:02:26,360 --> 00:02:28,900 There is a path from any node in N, 47 00:02:28,900 --> 00:02:30,993 O, K to any other node in N, O, 48 00:02:30,993 --> 00:02:34,545 K. For example, if you wanted to find a path from N to K, 49 00:02:34,545 --> 00:02:35,949 you would go N-O-K. 50 00:02:35,949 --> 00:02:39,375 However, condition number two fails 51 00:02:39,375 --> 00:02:43,130 because there are other nodes that can actually reach nodes in the subset. 52 00:02:43,130 --> 00:02:47,015 For example, L can actually reach N, 53 00:02:47,015 --> 00:02:51,505 O and K, there is a path from L to all three of those nodes. 54 00:02:51,505 --> 00:02:57,955 So therefore, this is not a connected component because condition number two fails. 55 00:02:57,955 --> 00:02:59,630 So if you think about it, 56 00:02:59,630 --> 00:03:02,810 the only things that satisfy the definition of 57 00:03:02,810 --> 00:03:07,190 connected component are the things that we originally started with. 58 00:03:07,190 --> 00:03:09,680 These three communities such that every node is 59 00:03:09,680 --> 00:03:12,860 connected within and no nodes are connected across. 60 00:03:12,860 --> 00:03:17,190 And these are the three connected components in this particular graph. 61 00:03:17,190 --> 00:03:21,300 You can use network X to find the connected components of 62 00:03:21,300 --> 00:03:25,255 an undirected graph by using the function number_connected_components and give it, 63 00:03:25,255 --> 00:03:27,570 the graph, its input and it would tell you how many. 64 00:03:27,570 --> 00:03:29,545 It has, in this case, three. 65 00:03:29,545 --> 00:03:33,719 And you can also ask for which ones 66 00:03:33,719 --> 00:03:38,126 are the actual components by using the function connected_components(G), 67 00:03:38,126 --> 00:03:40,230 and here we tell you which are 68 00:03:40,230 --> 00:03:45,230 the subsets of nodes and which nodes belong to each one of the components. 69 00:03:45,230 --> 00:03:49,320 What you can also do is use the function node_connected_component 70 00:03:49,320 --> 00:03:54,995 with the input G of the graph itself but also a particular node as input, 71 00:03:54,995 --> 00:04:00,100 and this would tell you which connected component this particular node belongs to. 72 00:04:00,100 --> 00:04:01,620 So in this case, for example, 73 00:04:01,620 --> 00:04:05,565 if you ask for the component in which M belongs, 74 00:04:05,565 --> 00:04:10,540 then it would tell you that it belongs to a component K, L, M, N, O. 75 00:04:10,540 --> 00:04:14,950 So these are useful things to use in network X. 76 00:04:14,950 --> 00:04:17,785 Now, let's talk about connectivity in directed graphs. 77 00:04:17,785 --> 00:04:21,835 Remember, directed graphs are those that have edges where the edges have direction, 78 00:04:21,835 --> 00:04:24,280 so there is a source and a destination. 79 00:04:24,280 --> 00:04:27,105 And so, here is an example of a directed graph. 80 00:04:27,105 --> 00:04:29,670 We would like to come up with definitions of 81 00:04:29,670 --> 00:04:33,210 connected and connected components that apply to directed graphs, 82 00:04:33,210 --> 00:04:35,495 but because paths have a different definition in 83 00:04:35,495 --> 00:04:37,815 directed graphs than they do in undirected graphs, 84 00:04:37,815 --> 00:04:42,060 then we need to adjust our definitions accordingly. 85 00:04:42,060 --> 00:04:44,310 And actually, what happens is that we will have 86 00:04:44,310 --> 00:04:47,695 two types of definitions for each one of the two concepts. 87 00:04:47,695 --> 00:04:50,380 So let's start with the concept of connected. 88 00:04:50,380 --> 00:04:53,400 The first type is we're going to say that a direct graph is 89 00:04:53,400 --> 00:04:56,451 strongly connected if for every pair of nodes, 90 00:04:56,451 --> 00:05:00,080 say U and V, there is a directed path that goes from U 91 00:05:00,080 --> 00:05:03,890 to V and another directed path that goes from V to U. 92 00:05:03,890 --> 00:05:08,175 That, if a directed graph has a has a property, 93 00:05:08,175 --> 00:05:10,890 then we say it's strongly connected. 94 00:05:10,890 --> 00:05:13,230 We can use the function is_strongly_connected in 95 00:05:13,230 --> 00:05:16,840 network X to ask whether this particular directed graph, G, 96 00:05:16,840 --> 00:05:21,300 is strongly connected and it would say false because if you look carefully, 97 00:05:21,300 --> 00:05:25,080 there is no path that goes from A to H, for example. 98 00:05:25,080 --> 00:05:26,735 There are many other examples of pairs of 99 00:05:26,735 --> 00:05:29,095 nodes for which there is no path, where here is one, 100 00:05:29,095 --> 00:05:31,230 there is no path from A to H, so therefore, 101 00:05:31,230 --> 00:05:35,225 this graph is not strongly connected. 102 00:05:35,225 --> 00:05:39,390 The second definition for connected is weakly connected. 103 00:05:39,390 --> 00:05:42,510 And the way weakly connected works is that the first thing you do is you 104 00:05:42,510 --> 00:05:47,010 replace all the directed edges and you make them undirected. 105 00:05:47,010 --> 00:05:49,290 So every edge, you could sort of ignore 106 00:05:49,290 --> 00:05:52,740 the direction and you make him into a undirected edge, 107 00:05:52,740 --> 00:05:55,630 and now this graph becomes undirected. 108 00:05:55,630 --> 00:06:00,705 And now, you ask the question that you already applied to undirected graphs, 109 00:06:00,705 --> 00:06:03,090 is this graph connected or not? 110 00:06:03,090 --> 00:06:07,380 And if it is, then we say that the original directed graph is weakly connected. 111 00:06:07,380 --> 00:06:10,980 So in this case, if we use the function is_weakly_connected, 112 00:06:10,980 --> 00:06:12,505 network X would say yes, 113 00:06:12,505 --> 00:06:16,770 this graph is weakly connected because once you turn it into an undirected graph, 114 00:06:16,770 --> 00:06:21,225 this undirected graph is connected. 115 00:06:21,225 --> 00:06:24,890 All right, now let's talk about the connected component definition. 116 00:06:24,890 --> 00:06:26,650 Again, we're going to have two types. 117 00:06:26,650 --> 00:06:29,285 The first one is strongly connected components 118 00:06:29,285 --> 00:06:33,485 and the definition mirrors the definition for undirected. 119 00:06:33,485 --> 00:06:36,735 It's just that now, you have to find paths that are directed, 120 00:06:36,735 --> 00:06:39,665 so it would have the two conditions for a subset of nodes to be 121 00:06:39,665 --> 00:06:43,490 connected component are that every node in the subset has a directed path to 122 00:06:43,490 --> 00:06:46,730 every other node in this subset and that no node outside 123 00:06:46,730 --> 00:06:52,065 the subset has a directed path to and from every node inside the subset. 124 00:06:52,065 --> 00:06:53,480 And so in this case, 125 00:06:53,480 --> 00:06:57,785 what are the strongly connected components of this graph? 126 00:06:57,785 --> 00:07:00,285 It's actually not that easy to tell visually. 127 00:07:00,285 --> 00:07:02,510 It's a little tricky, though you could try to 128 00:07:02,510 --> 00:07:05,510 pause the video and try and see if you can find what they are. 129 00:07:05,510 --> 00:07:09,455 But if we use the function strongly_connected_components, 130 00:07:09,455 --> 00:07:11,145 it will tell us what they are. 131 00:07:11,145 --> 00:07:15,712 And in this case, it turns out that these are the strongly connected components. 132 00:07:15,712 --> 00:07:17,510 And so, as you can see, 133 00:07:17,510 --> 00:07:20,330 for example, you find that N, node M, 134 00:07:20,330 --> 00:07:23,030 and node L are in different components 135 00:07:23,030 --> 00:07:26,720 and that's because even though you can go from L to M, 136 00:07:26,720 --> 00:07:29,918 you cannot go from M to L, right? 137 00:07:29,918 --> 00:07:31,895 And same thing with, for example, 138 00:07:31,895 --> 00:07:35,050 H, I are sort of in their own component, 139 00:07:35,050 --> 00:07:39,115 and that's because while they can reach other nodes like G and J, 140 00:07:39,115 --> 00:07:41,615 none of those nodes seem that they can reach them. 141 00:07:41,615 --> 00:07:46,160 And so, these live in their own separate, strongly connected component. 142 00:07:46,160 --> 00:07:48,420 And of course, we would have 143 00:07:48,420 --> 00:07:53,970 the weakly connected component version which works in the same way that it did before. 144 00:07:53,970 --> 00:07:57,615 So first, we would make all the directed edges undirected, 145 00:07:57,615 --> 00:08:02,040 and then we would find the connected components in the new undirected graph. 146 00:08:02,040 --> 00:08:04,170 Now, because this graph is weakly connected, 147 00:08:04,170 --> 00:08:07,245 that means that when you make all the direct edges undirected, 148 00:08:07,245 --> 00:08:09,255 it becomes a connected graph. 149 00:08:09,255 --> 00:08:13,095 Then this particular graph has only one weakly connected component, 150 00:08:13,095 --> 00:08:14,645 which is the whole graph. 151 00:08:14,645 --> 00:08:17,310 And so, to summarize, 152 00:08:17,310 --> 00:08:20,550 we talked about undirected graphs and directed graphs and we were 153 00:08:20,550 --> 00:08:24,190 talking about a couple of definitions of connectivity. 154 00:08:24,190 --> 00:08:25,320 So for underactive graphs, 155 00:08:25,320 --> 00:08:29,320 we said that an undirected graph is connected if for every pair of nodes, 156 00:08:29,320 --> 00:08:31,256 there is a path between them. 157 00:08:31,256 --> 00:08:34,890 And we talked about connected components and we said that we could 158 00:08:34,890 --> 00:08:38,580 use the function connected_components to find these connected components, 159 00:08:38,580 --> 00:08:40,690 so here's an example. 160 00:08:40,690 --> 00:08:42,540 Now, for the directed case, 161 00:08:42,540 --> 00:08:44,520 we had two types of definitions, 162 00:08:44,520 --> 00:08:46,020 the strong and the weak. 163 00:08:46,020 --> 00:08:48,265 For the strongly connected, 164 00:08:48,265 --> 00:08:52,140 we said that our graph is strongly connected if every pair of nodes, 165 00:08:52,140 --> 00:08:56,220 they have a directed path from one node to the other and from the other node to the one, 166 00:08:56,220 --> 00:09:00,285 and you could use the function strongly_connected_components 167 00:09:00,285 --> 00:09:02,555 to find what these components were. 168 00:09:02,555 --> 00:09:06,070 And both of these had the corresponding weak definitions, 169 00:09:06,070 --> 00:09:08,580 so weakly connected and weakly connected components. 170 00:09:08,580 --> 00:09:12,670 And the way that those work is by making the direct edges undirected, 171 00:09:12,670 --> 00:09:15,145 and then applying the same definitions that we had from 172 00:09:15,145 --> 00:09:19,730 undirected graphs to the new undirected graph that comes from the directed graph. 173 00:09:19,730 --> 00:09:23,720 Thank you for watching and we'll see you next time.