Get startedGet started for free

Maximal cliques

1. Maximal cliques

I hope you had fun cracking the problem of finding open triangles! Now that you've learned about cliques, let's take a quick look at the concept of "maximal cliques".

2. Maximal cliques

Maximal cliques are defined as such: they are a clique, but that clique cannot be extended by adding another node in the graph. For example, the sub-clique of the 3 green nodes can be extended by one blue node to form a larger clique. As such, these 3 green nodes do not form a "maximal clique" in the graph. On the other hand, the four nodes

3. Maximal cliques

connected as a clique together cannot be extended and still remain a clique, as the remaining node is not fully connected to the other four nodes. As such, these four nodes constitute a "maximal clique". The concept of maximal cliques has its

4. Maximal cliques

uses in community finding algorithms. Without going into the myriad of details possible, I hope to define at a basic level

5. Communities

what a community is. Cliques form a good starting point for finding communities, as they are fully connected subgraphs within a larger graph. By identifying these maximal cliques, one naive way of identifying communities might be identifying the unions of maximal cliques that share some number of members, but are also of some minimum size.

6. NetworkX API

NetworkX provides a function for finding all maximal cliques, which is the find_cliques function. Remember this as you go forward, that find_cliques will not just find any clique but the set of maximal cliques.

7. Maximal cliques

Let's bring back the barbell graph from before. If we apply the nx-dot-find_cliques function, we will find that it returns a generator, which we can iterate over, but it doesn't return the list of maximal cliques. To get the list of maximal cliques, we need to cast that as a list.

8. Maximal cliques

It should be clear to you that there are two maximal cliques of size 5 in this graph. What might be less intuitive is that there are

9. Maximal cliques

two maximal cliques of size 2 - these are the edges between nodes 4 and 5, and nodes 5 and 6. Recall that edges are also a clique.

10. Let's practice!

Okay! Now that you've gotten down the basics of finding cliques in a graph, let's go try out the exercises!

Create Your Free Account

or

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.