0:08

Last time we talked about connectivity in networks.

Â Today we're going to talk about how connectivity relates

Â to the robustness of a network.

Â So, what is network robustness?

Â The way we loosely define network robustness is the ability

Â of a network to maintain its general structure, or

Â its general functions when it faces failures or attacks.

Â So what kind of attacks are we talking about here?

Â Well, we're going to talk about attacks that are in the form of removal of

Â nodes or edges.

Â This could be somebody purposely trying to remove a node or an edge from a network,

Â or maybe, just random failures that the network may have.

Â And then what are the general properties that we are going to be discussing?

Â In this case we're going to be talking about connectivity, so

Â robustness is going to be the network's ability to maintain its connectivity.

Â When it loses some of its nodes or some of its edges.

Â So why is this relevant?

Â Why is this important?

Â Let's look at some examples of networks that often lose nodes or edges.

Â And these things affect the function.

Â So one example is the air transportation network,

Â where the nodes are airports and the edges are connections between airports.

Â Well, sometimes airports have to close down for many different reasons.

Â And when this happens of course, transportation is affected.

Â And so you would like for the transportation network to be robust to

Â closures of airports, so that the general connectivity or the general function of

Â the network is still maintained even after it might have lost one particular airport.

Â Or maybe it's not an airport, maybe it's a connection between an airport or

Â some other airport.

Â Maybe both airports are open but they're not able to fly to each other for

Â whatever reason.

Â That is the case where the network might have lost an edge rather than a node, and

Â you would like for the network to still maintain its connectivity or functions.

Â There are plenty of other examples like Internet router failures or

Â power line failure and so on.

Â And so for all of these, this idea of removing nodes or

Â edges are things that actually happen, and

Â for all of this maintaining connectivity is very important.

Â 2:16

So let's begin looking at our

Â sort of toy example of graph here that we've been looking at.

Â And we'll start with an undirected graph, and

Â ask what is the smallest number of nodes that I would need to remove

Â from this graph in order in order to make it disconnected?

Â 2:34

And so we can actually use a function in network X that's node connectivity,

Â and the input will be the undirected graph here, G_un.

Â And it says that if I just remove one node,

Â I would be able to disconnect the graph completely.

Â You can try and see if you can figure out which node that is.

Â Or you can use the function_minimum_node_cut, and

Â then give it us input the undirected graph.

Â And it would tell you which nodes are the ones that you can remove in

Â order to disconnect the graph.

Â And in this case, it's node A.

Â 3:10

So you can see that if you were to remove node A,

Â then this graph goes from being connected to being disconnected.

Â So now there are two subsets of nodes that cannot reach each other, and

Â in the airport example this would be really bad, right?

Â If one airport was responsible for connecting two major parts of the world,

Â that's something you probably wouldn't want to have.

Â Now let's ask the question for edges.

Â What is the smallest number of edges, instead of nodes, that we would need to

Â remove from this graph in order to completely disconnect it?

Â 3:55

Well, which 2 edges are there?

Â You can try to figure it out in your own, or you can use the function,

Â minimum_edge_cut, and give it us input the undirected graph.

Â And it tells you that the edges that you need to remove are, A, G and O, J.

Â And you can see that if you remove those two edges,

Â you indeed make the network disconnected.

Â And there are two clusters,

Â two subsets of nodes that cannot reach each other anymore.

Â Of course, it's possible that there are other options of edges that do this.

Â But the fact that the edge connectivity is

Â two tells us that the smallest number of edges that you have to remove is two.

Â Now the particular choice of A, G and O, J may not be unique.

Â There may be other options,

Â other pairs of edges that achieve the same goal of disconnecting the network.

Â 4:44

Robust networks are those that have a large minimum node and edge cuts.

Â That is those for which you would have to remove a lot of nodes or

Â edges in order to be able to disconnect them.

Â That's a very desirable property, because you don't want your network to

Â be easily disconnected by just removing a few nodes or a few edges.

Â 5:05

Okay, now let's look at a different scenario.

Â First of all, let's now look at a directed graph,

Â those that have edges that have a source and a destination.

Â And now let's think about a different setting.

Â Now, let's think about these nodes as nodes that want to communicate with each

Â other, that want to pass messages to each other.

Â These could be maybe routers, or these could be people who are trying to pass

Â a rumor or pass an important message to each other, right?

Â And so imagine that node G here wants to send a message to node L by

Â passing it along to other nodes in this network.

Â So, basically what G wants to do is to find the paths that

Â could take a message from G all the way to L.

Â 5:51

What options does G have in order to do this?

Â What are those paths that G can use?

Â Well, if you use the function all_simple_paths with input G, the graph

Â and then the two nodes that source in the destination, in this case G and L.

Â Then you get all the paths.

Â Let's look at each one of those paths.

Â So first one is G, A, N, L.

Â The second one is slightly longer is G, A, N, O, K, L.

Â You could also go G, A, N, O, L or G, J, O, K, L.

Â Or you could go with a shorter path, G, J, O, L.

Â So these are all the options that G has.

Â 6:33

Okay, now let's imagine that there's some attacker,

Â some person that wants to actually block the message that's going from G to L.

Â This attacker is no longer interested in just disconnecting the network

Â in any particular way, it's interested in

Â particularly disrupting the communication that's going from G to L.

Â We could ask the question if this person was going to try to do this by removing

Â node, how many nodes would this attack I need to remove in order to block G from L.

Â 7:05

We can use the same function, node connectivity as we did before, but

Â now we give this input not only the graph G, but also the source and

Â the destination, G and L.

Â And it would tell us how many nodes you would need in order to achieve that.

Â And in this case, you would need to remove two nodes from the network.

Â Which nodes are they?

Â Again, we can use the same function as we used before, minimum_note_cut,

Â and give it the graph, the source and the destination as input, and

Â he would tell us which are the two nodes.

Â In this case the nodes are N and O.

Â 7:43

Now let's do some sanity checking here.

Â What if we were only to remove node N,

Â then can we still find a path that goes from G to L?

Â And the answer is yes, you could take the path G, J, O, K, L.

Â On the other hand, if we were to only remove node O,

Â then can the message still make it?

Â And the answer is yes.

Â You could go G, A, N, L.

Â So this shows that it's not enough to remove one of these two nodes.

Â And you can check on your own that when you actually remove both of these and

Â O, then there is no longer any path that can go from G to L.

Â So you need two, and these are two that achieve that.

Â We can ask the same question as we did before for edges.

Â Now the attacker, let's say, is only able to remove edges,

Â not completely remove nodes.

Â How many edges would this attacker need to remove in order to block G from L?

Â We can use the function edge_connectivity with the input, the graph, the source and

Â destination.

Â And it tells us that It needs two edges in order to be able to achieve this.

Â And to figure out which edges they are, we can use again

Â the minimum_edge_cut function with the graph, the source and the destination.

Â And it tells us that the two edges are A, N and J, O, and so

Â here they are shown in red.

Â And you can check that if you were to remove those two edges indeed,

Â G would no longer be able to send the message to L.

Â 9:41

And then you have a similar definition for edge connectivity,

Â which is the minimum number of edges that you need in order to disconnect the graph,

Â or to disconnect any pair of nodes.

Â And the functions they use are edge_connectivity and minimum_edge_cut.

Â And the takeaway here is that graph with large node or

Â large edge connectivity are more robust to the loss of nodes and edges.

Â And they're able to keep their connectivity even if

Â some number of edges and nodes are removed from the network.

Â And for many applications, this is a very desirable property for networks to have.

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

Â