0:07

Today, we're going to talk about connectivity in networks.

Â First, we're going to talk about connectivity in undirected graphs.

Â Those are the ones where the edges don't have a direction.

Â An undirected graph is said to be connected if for every pair of nodes,

Â there is a path between the two nodes.

Â We can use the function is_connected in

Â network X and give it the undirected graph as input,

Â and it will tell us whether the graph is connected or not.

Â In this case, this example,

Â this graph is connected so it says, true, it is connected.

Â However, if we were to remove a few of the edges, for example,

Â if we remove A-G, A-N,

Â and J-O, then the graph will become disconnected, as you can see.

Â Now, we have these sort of

Â three communities such that if you're in a particular community,

Â you cannot find a path to a node in a different community,

Â or in a different set of nodes.

Â Let's try to get at this idea of communities in a more precise way.

Â We're going to refer to these communities as connected components.

Â So let me give you a definition of what a connected component is.

Â A connected component is a subset of nodes

Â such that there are two conditions this set of nodes satisfy.

Â First, every node in the subset has to have a path to every other node in the subset.

Â That's condition number one.

Â Condition number two would say that no other node outside of

Â the subset has a path to any node inside the subset.

Â So condition two kind of makes sure that

Â you get all the nodes that you could possibly can

Â so that every node in this subset has a connection to every other node in the subset,

Â not a subset of the subset that you could potentially get.

Â So let's see this through examples to make it more clear.

Â Is the subset of nodes E, A,

Â G, F a connected component?

Â So first, let's find these nodes and so here they are.

Â This is the subset of nodes we're referring to.

Â And we can clearly see that this is not a connected component because the nodes,

Â for example, A and F,

Â cannot reach each other.

Â There is no path going from A to F,

Â so condition number one fails.

Â Okay, let's look at another example.

Â Is the subset of nodes N,

Â O, K a connected component?

Â All right, these are the nodes.

Â Now in this case, condition number one is actually met.

Â There is a path from any node in N,

Â O, K to any other node in N, O,

Â K. For example, if you wanted to find a path from N to K,

Â you would go N-O-K.

Â However, condition number two fails

Â because there are other nodes that can actually reach nodes in the subset.

Â For example, L can actually reach N,

Â O and K, there is a path from L to all three of those nodes.

Â So therefore, this is not a connected component because condition number two fails.

Â So if you think about it,

Â the only things that satisfy the definition of

Â connected component are the things that we originally started with.

Â These three communities such that every node is

Â connected within and no nodes are connected across.

Â And these are the three connected components in this particular graph.

Â You can use network X to find the connected components of

Â an undirected graph by using the function number_connected_components and give it,

Â the graph, its input and it would tell you how many.

Â It has, in this case, three.

Â And you can also ask for which ones

Â are the actual components by using the function connected_components(G),

Â and here we tell you which are

Â the subsets of nodes and which nodes belong to each one of the components.

Â What you can also do is use the function node_connected_component

Â with the input G of the graph itself but also a particular node as input,

Â and this would tell you which connected component this particular node belongs to.

Â So in this case, for example,

Â if you ask for the component in which M belongs,

Â then it would tell you that it belongs to a component K, L, M, N, O.

Â So these are useful things to use in network X.

Â Now, let's talk about connectivity in directed graphs.

Â Remember, directed graphs are those that have edges where the edges have direction,

Â so there is a source and a destination.

Â And so, here is an example of a directed graph.

Â We would like to come up with definitions of

Â connected and connected components that apply to directed graphs,

Â but because paths have a different definition in

Â directed graphs than they do in undirected graphs,

Â then we need to adjust our definitions accordingly.

Â And actually, what happens is that we will have

Â two types of definitions for each one of the two concepts.

Â So let's start with the concept of connected.

Â The first type is we're going to say that a direct graph is

Â strongly connected if for every pair of nodes,

Â say U and V, there is a directed path that goes from U

Â to V and another directed path that goes from V to U.

Â That, if a directed graph has a has a property,

Â then we say it's strongly connected.

Â We can use the function is_strongly_connected in

Â network X to ask whether this particular directed graph, G,

Â is strongly connected and it would say false because if you look carefully,

Â there is no path that goes from A to H, for example.

Â There are many other examples of pairs of

Â nodes for which there is no path, where here is one,

Â there is no path from A to H, so therefore,

Â this graph is not strongly connected.

Â The second definition for connected is weakly connected.

Â And the way weakly connected works is that the first thing you do is you

Â replace all the directed edges and you make them undirected.

Â So every edge, you could sort of ignore

Â the direction and you make him into a undirected edge,

Â and now this graph becomes undirected.

Â And now, you ask the question that you already applied to undirected graphs,

Â is this graph connected or not?

Â And if it is, then we say that the original directed graph is weakly connected.

Â So in this case, if we use the function is_weakly_connected,

Â network X would say yes,

Â this graph is weakly connected because once you turn it into an undirected graph,

Â this undirected graph is connected.

Â All right, now let's talk about the connected component definition.

Â Again, we're going to have two types.

Â The first one is strongly connected components

Â and the definition mirrors the definition for undirected.

Â It's just that now, you have to find paths that are directed,

Â so it would have the two conditions for a subset of nodes to be

Â connected component are that every node in the subset has a directed path to

Â every other node in this subset and that no node outside

Â the subset has a directed path to and from every node inside the subset.

Â And so in this case,

Â what are the strongly connected components of this graph?

Â It's actually not that easy to tell visually.

Â It's a little tricky, though you could try to

Â pause the video and try and see if you can find what they are.

Â But if we use the function strongly_connected_components,

Â it will tell us what they are.

Â And in this case, it turns out that these are the strongly connected components.

Â And so, as you can see,

Â for example, you find that N, node M,

Â and node L are in different components

Â and that's because even though you can go from L to M,

Â you cannot go from M to L, right?

Â And same thing with, for example,

Â H, I are sort of in their own component,

Â and that's because while they can reach other nodes like G and J,

Â none of those nodes seem that they can reach them.

Â And so, these live in their own separate, strongly connected component.

Â And of course, we would have

Â the weakly connected component version which works in the same way that it did before.

Â So first, we would make all the directed edges undirected,

Â and then we would find the connected components in the new undirected graph.

Â Now, because this graph is weakly connected,

Â that means that when you make all the direct edges undirected,

Â it becomes a connected graph.

Â Then this particular graph has only one weakly connected component,

Â which is the whole graph.

Â And so, to summarize,

Â we talked about undirected graphs and directed graphs and we were

Â talking about a couple of definitions of connectivity.

Â So for underactive graphs,

Â we said that an undirected graph is connected if for every pair of nodes,

Â there is a path between them.

Â And we talked about connected components and we said that we could

Â use the function connected_components to find these connected components,

Â so here's an example.

Â Now, for the directed case,

Â we had two types of definitions,

Â the strong and the weak.

Â For the strongly connected,

Â we said that our graph is strongly connected if every pair of nodes,

Â they have a directed path from one node to the other and from the other node to the one,

Â and you could use the function strongly_connected_components

Â to find what these components were.

Â And both of these had the corresponding weak definitions,

Â so weakly connected and weakly connected components.

Â And the way that those work is by making the direct edges undirected,

Â and then applying the same definitions that we had from

Â undirected graphs to the new undirected graph that comes from the directed graph.

Â Thank you for watching and we'll see you next time.

Â