This course will introduce the learner to network analysis through tutorials using the NetworkX library. The course begins with an understanding of what network analysis is and motivations for why we might model phenomena as networks. The second week introduces the concept of connectivity and network robustness. The third week will explore ways of measuring the importance or centrality of a node in a network. The final week will explore the evolution of networks over time and cover models of network generation and the link prediction problem. This course should be taken after: Introduction to Data Science in Python, Applied Plotting, Charting & Data Representation in Python, and Applied Machine Learning in Python.
Network Robustness
Loading...
Do curso por University of Michigan
Applied Social Network Analysis in Python
534 ratings
Na lição
Network Connectivity
In Module Two you'll learn how to analyze the connectivity of a network based on measures of distance, reachability, and redundancy of paths between nodes. In the assignment, you will practice using NetworkX to compute measures of connectivity of a network of email communication among the employees of a mid-size manufacturing company.
Conheça os instrutores
Daniel RomeroAssistant Professor
School of Information
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.
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?
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.
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?
Well, you can use the function edge connectivity and
give it us input the undirected graph.
And it tells us that there are two edges that you need to remove in order to
disconnect this graph.
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.
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.
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.
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.
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.
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.
So, this says that you have to remove at least two nodes and
here are two options for that N and O.
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.
So in summary, in this video, we've talked about node connectivity, and
that is the minimum number of nodes that you need in order to disconnect a graph or
disconnect a particular pair of nodes.
And the functions associated with node connectivity are node_connectivity, which
tells us the smallest number of nodes that you need in order to achieve that.
And minimum_node_cut which actually tells us which are those nodes.
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.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
