In this video we will explore another fundamental property of graphs called Connectivity. We list two important kinds of graph analytic questions that are based on connectivity. In the first case we are asking about the robustness of the network. Suppose we have a computer network with many servers and a hacker is trying to bring the system down, you set a small set of servers that the hacker can target to disrupt the network. What we mean by disrupt is to disconnect a part of the network from the rest. A similar problem may occur in the power distribution network. In that case, an attacker may be able to attack one or two central components so that large portions of the network loses power. I have a geneticist colleague at Tech Graduate Institute who studied the robustness of biological networks. He told me that many biological networks have built in redundancy, so that even if you disrupt one important gene, there are other genes in the network which will support the biological function, possibly through other routes. Therefore a network is robust, if removing one or more edges or nodes still keeps it connected. The second category is about network comparison in terms of their overall connectivity. The two graphs shown here are very different in their structure. What are some parameters by which we can compare them? That to talk about connectivity, we must first define the concept of connectivity. Very simple. A graph is connected if we can reach any node from any other node. Let's look at the crypto graph in the picture, clearly we cannot reach from all nodes to all nodes here because this graph is not connected. However, we can identify four parts of the graph that are themselves connected. These islands of connected parts are called components or connected components of a graph. For directed graphs, we need to be a little more specific about connectivity. We say that the directed graph is strongly connected, if we follow the direction of the edges and still reach every node from every other node. A weaker form of connectivity is if we do not care about the direction of the arrows and can reach every node from every other node. Another way of saying it is that the undirected version of the graph is connected, this is called Weak Connected. Look at the graph that we have seen so many times in this course. Is it strongly connected or weakly connected? This leads to some big graph challenge. Given an arbitrarily large graph, can I find the connected components of the graph efficiently? Second given an arbitrarily large graph, can we find its sub graphs that are strongly connected? We'll touch upon these questions in Module Four.