1. Communities & cliques
Awesome progress! I hope you're feeling challenged and energized for the coming set of ideas! We're now going to explore the concepts of structures and subgraphs, using NetworkX. A lot of this is going to leverage what you've learned in the second chapter, particularly on path finding and the use of neighbors. Before we go to the technical stuff, let's think about a real-life scenario.
2. Cliques
Have you ever been in a clique? How would you characterize the clique? It probably was comprised of people who knew everybody else in the group to a pretty strong degree, right? Now imagine if there was another new person not originally part of the clique that joined in - now, in this group, it wouldn't feel like a "clique", because the new person doesn't really know everyone else, and vice versa. In network theory, a "clique" is essentially defined on the social version of a clique: that is, a set of nodes that are completely connected by an edge to every other node in the set. It is, then, a completely connected graph. What might be the "simplest clique"?
3. Cliques
By the definition of a clique, an edge is the simplest clique possible. Now, what would be the simplest "complex clique"? Pause the video and give it a thought. Did you answer, "3 nodes fully connected", or, in other words, "a triangle"? If you did, then you got this question correct too! Great work!
4. Triangle Applications
What are some applications of finding "triangles" in a network? Well, one example may be in friend recommendation systems. For example, if A knows B and A knows C, but B and C are not yet connected, then there's a good chance that B knows C as well, and may want to be connected online, by doing what we call triangle closures.
5. Clique Code
How might you write code that finds all triangles that a node is involved in? That will be the exercise that you're going to go through, but I will give you a few coding hints to launch you into them. Suppose you had a graph G, and you wanted to iterate over every pair of nodes, and not only every edge. Rather than writing a double for-loop, you might want to use the combinations function from the Python itertools module. In this way, your for loop can iterate over every pair of nodes in the network, by using the following code: for n1, n2 in combinations(sequence, size of combinations) - so in this case it's G-dot-nodes and 2 because we wanted pairs of nodes. In the logical code block just after, we can do whatever we need to do with the pairs of nodes. In this demo above, I've just decided to print them.
6. Let's practice!
Alright, I think you're ready to go onto the exercises! Go forth and have fun!