[SOUND] So that egonet example, that egonet task you have to do is kind of your warm up task. Now, let's get into a bit of a meatier example, which is writing an algorithm and some code to find the strongly connected components in a graph. So by the end of this video, you will be able to define what strongly connected components are and identify them in a graph and then you'll be able to write an algorithm that will extract the subgraphs which are strongly connected components from a given graph. So to motivate this example, let's go back to that Twitter data that we talked about, this retweet graph because strongly connected components only make sense on directed graphs. So we don't want to use that Facebook data. So we've got our Twitter retweet graph here and just to remind you of what this is, every note in the graph has edges to other notes when it has, at some point in the past, retweeted some message from that other person who's on Twitter. So for example, in this case, 25 has at some point retweeted a message from 23, from 18 and from 65. And this is a directive graph because retweets happen just in one direction and they're not always reciprocated. So a question we might ask about this graph is, are there communities of retweeters, basically people who are kind of grouped together and they're all kind of sharing each other's tweets around? So I retweet Mia, Mia retweets Leo, Leo retweets me, and vise versa maybe I retweet Leo also, and so then there's this kind of grouped together behavior who are all kind of passing information around. So we want to find those communities of retweeters. This is actually a problem known as a problem of extracting the strongly connected components from this graph, but before we can get into what strongly connected components are, let me take a moment to explain what a strongly connected graph is as a whole. So a strongly connected graph is a directed graph such that for every pair of vertices, there's a path from one vertex to the other, and then from the other vertex back to the first one, so you choose any two arbitrary vertices in the graph, you can get from one to the other and then back again. It doesn't necessarily have to be a single edge, it just have to be some path somehow through the graph. Now, you can see pretty easily this graph is not strongly connected. So we have, for example, node 18 and node 50. I am yet to node 50 from node 18. But once of 50 I can't get back to node 18. So because there's a pair of vertices that you can't go in both directions, there's not a path in both directions, this graph is not strongly connected. So just a question to make sure you understand this concept of strongly connected graphs. I'd like you to tell me, is this graph strongly connected? Hopefully, the answer you got was yes. Because if you choose any two vertices there is a path in both directions. So let's see how that's true. So if we look at vertex 25 and 23, well, that's trivially true since there's edges in both directions between those nodes. Let's look at node 25 and node 65. While you can directly from 25 to 65 and to get from 65 back to 25 I just have to go via node 23. That's no problem. And then, node 65 and 23 are connected in both directions in the same way. Directly from 65 to 23 I can get back to 65 by going through 25. So this is a strongly connected graph. Now, let's put that into the context of strongly connect components. So strongly connected components in graphs are subgraphs, such that the subgraph itself is a strongly connected graph, and that subgraph is maximal. Now, what does it mean to be maximal? That means that there's no other nodes and edges that we could add and still have a strongly connected graph. So if there's any other nodes or edges I could add to the my subgraph such that it would still be strongly connected, then that thing that I was originally looking at is not a strongly connected component. So let me have you try this out for yourself. Let's take this subgraph here that you see in yellow. And I want you to tell me, is this a strongly connected component of the entire graph? So to answer this question, you had to answer two different questions. This first question is, is it a strongly connected graph and this is the same graph we look at before so yes this graph is strongly connected. Now, the other question we have to ask is, is it maximal? Are there any other nodes we could add to this subgraph such that it would still be strongly connected? And hopefully you found that node 18 can also be added to the subgraph and it would still be a strongly connected graph, because you can get two any other node, in the subgraph, from node 18. And you can get from any other node in the subgraph to node 18 via some path in the subgraph. So this original set of nodes in yellow is not a strongly connected component. But if I add node 18 then it is a strongly connected component. Take a moment to find the other strongly connected components in this entire graph. And if you can't find them all right now, that's okay, we'll be coming back to it as we trace through the algorithm for finding the strongly connected components.