Social Network Analysis Part7: Cliques.

A group of nodes that are completely connected to one another.

Introduction.

Recap.

Over the previous blogs:

• In Part 1, we established the foundations of graph theory, exploring how networks are structured using nodes and edges, the differences between graph types, and how link prediction can forecast future relationships.
• In Part 2, we moved beyond messy “hairball” diagrams and learned how to visualize network patterns using structured techniques e.g., Matrix Plots, Arc Plots, and Circos Plots.
• In Part 3, we began quantifying network structures using fundamental centrality measures e.g., Degree Centrality to count direct connections and Betweenness Centrality to get the number of shortest paths in a graph that pass through a node.
• In Part4, we explored how each of these measures of Closeness Centrality, Eigenvector Centrality, and PageRank work, and understood that not all central nodes are important for the same reason. A node might be important because it is close to everyone else, because it is connected to other influential nodes, or because it receives links from highly important nodes. We understood the intuition behind their mathematical definitions, visualized them using simple network examples.
• In Part5, we provided an overview of the most common pathfinding algorithms in SNA. We explored how these algorithms work, their strengths and weaknesses.

This blog, we’ll learn about essential concepts such as cliques. where we’ll leverage all of the skills you acquired in Part3, Part4 and Part5, particularly on path finding and the use of neighbors.
By the end of this blog, we’ll be ready to apply the concepts we’ve learned to a real-world case study.

What is a Clique?

In Social Network Analysis (SNA), a clique represents a group of nodes that are completely connected to one another.

Network cliques: completely connected graphs

If nodes represent people and edges represent friendship, communication, collaboration, or another relationship, then a clique is a group where every person is directly connected to every other person.

In simpler terms: Everyone in the group has a direct connection with everyone else in the group.
This is the maximum possible internal connectivity for an undirected network. (cs.cornell.edu).
I.e., imagine a group of 4 friends: A, B, C, D. Where every possible pair has a connection. I.e., A ↔ B, A ↔ C, A ↔ D, B ↔ C, B ↔ D and C↔ D.

n(n−1)/2

Cliques are often described according to their number of nodes.
By the definition of a clique, an edge is the simplest clique possible. Technically, an edge forms a clique of size 2, although SNA analyses often focus on cliques of size 3 or greater. (csd.uwo.ca)

This group forms a 4-clique, because there’re 4 nodes and every pair of nodes is connected. For n nodes, a clique contains: n(n−1)/2 internal edges.
Therefore, a 4-clique contains: 4(4−1)/2= 6 edges.

The key condition about what makes a group a clique is that Every pair of nodes must be directly connected. Consider these 2 groups:

• Group A = {A ↔ B, A ↔ C, B ↔ C} This is a 3-clique.
• Group B= {A ↔ B, A ↔ C, B ↔ C, C ↔ D, A ↔ D}

If D is also connected to B, then A, B, C, D form a 4-clique. But if B and D are not connected, then A, B, C, D cannot be a clique.
That single missing edge breaks the clique.

This is an important distinction: A clique is not simply a group of highly connected people. It requires complete internal connectivity.
A normal community can have missing connections; a strict clique cannot. (cs.cornell.edu)

Why cliques are so important in SNA 🤔?

Cliques are useful because they identify very tightly connected subgroups within a larger network. I.e., imagine a university social network:

The entire network might contain hundreds or thousands of students.
Within that network, you might discover a small group where everyone communicates and collaborates with everyone.

That subgroup could constitute a clique. This can reveal highly cohesive structures hidden inside a larger network.

Triangle Clique.

3-clique: 3 nodes where every pair is connected: A−B, A−C, B−C.
This forms a triangle. Triangles are the simplest non-trivial cliques. (cs.cornell.edu)

Some applications of finding “triangles” in a SN is friend recommendation systems. I.e., 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.

Friend recommendation systems

So as the nodes in a clique becomes larger, the number of required connections increases rapidly.

Maximal Clique

This is one of the most important concepts. A maximal clique is a clique that cannot be expanded by adding another node while preserving complete connectivity. (ona-book.org)

Suppose {A,B,C,D} is a clique. Now suppose node E is connected to A, B, and C, but not D. You cannot add E to the clique because E−D∉ E.
Therefore, {A,B,C,D} is a maximal clique with respect to that surrounding graph.

Important note: Maximal does NOT necessarily mean largest.
A maximal clique simply means: “I cannot add another node to this clique.”
It does not mean: “This is the biggest clique in the entire network.”

a clique that, when extended by one node is no longer a clique

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 4 nodes 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 uses in community finding algorithms. Without going into the myriad of details possible, I hope to define at a basic level

Maximal clique: A clique that cannot be extended by adding another node.
Maximum clique: A clique having the largest number of nodes in the entire network.

I.e., imagine a network contains:

• maximal clique A → 4 nodes
• maximal clique B → 5 nodes
• maximal clique C → 3 nodes

All 3 can be maximal cliques. But the 5-node clique is the maximum clique because it has the greatest size.

So, Maximum is the largest size. While Maximal cannot be extended

Cliques can overlap

An interesting property of social networks is that one person can belong to multiple cliques.

Suppose: C1={A,B,C,D} and C2={C,D,E,F}. Then: C1∩C2={C,D}. Which means that C and D belong to both cliques. This is particularly meaningful in social networks.

Get AI & Data Science 604’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

I.e., a person might simultaneously belong to a group of university friends, a research group, a work team and a family/ social group.

Clique-based approaches can therefore represent overlapping community structures, rather than forcing every node into exactly one community.

Cliques in a real social network

A useful real-world example is Zachary’s Karate Club network, a classic SNA dataset. It represents relationships among members of a university karate club.
Researchers can search this network for tightly connected groups and identify cliques within the larger network.

For example, one visualization of the Karate Club network highlights a 5-node largest clique.

This illustrates an important idea:

Large Social Network → Find Fully Connected Subgroups →Analyze Their Structure

Clique detection

If we have a graph G=(V,E). We can use algorithms to find its cliques.

One well-known algorithm is the Bron–Kerbosch algorithm, which is commonly used to enumerate maximal cliques. (cs.cornell.edu)

Conceptually:

Social Network
      │
      ▼
   Graph G
      │
      ▼
Clique Detection
      │
      ├── Clique 1
      ├── Clique 2
      ├── Clique 3
      └── ...

In Python/NetworkX, maximal cliques can be obtained with:

import networkx as nx

cliques = list(nx.find_cliques(G))
for clique in cliques:
    print(clique)

You can then analyze:

• clique size.
• clique membership.
• overlapping cliques.
• number of cliques.
• largest clique.
• nodes participating in many cliques.

Why clique detection becomes difficult

There is an important computational issue.

Finding cliques — particularly finding the maximum clique or enumerating all maximal cliques — can become computationally expensive for large graphs. The general clique problem is NP-complete. (cs.cornell.edu)

Why? Because the number of possible node subsets grows exponentially.

For n nodes, there are: 2^n possible subsets. The algorithm potentially has to consider many combinations to determine whether they form cliques.

This becomes particularly challenging for large social networks, dense graphs, millions of users and rapidly changing networks.

The limitation of strict cliques

There is an important conceptual limitation. Real social networks are rarely perfectly connected. Imagine 5 researchers:

A ─── B
│ \   │
│  \  │
C ─── D ─── E

They might form a very cohesive research group, even though not everyone communicates directly with everyone else. Under the strict clique definition, however, this is not a clique.
This is why researchers developed relaxed clique concepts, including:

• n-cliques
• n-clans
• n-clubs
• k-plexes

These allow some missing direct connections while preserving the idea of a cohesive subgroup. (cs.cornell.edu)

This is an important distinction between mathematical clique and real-world social community.

A clique has perfect internal connectivity, while a social community can be highly cohesive without being complete. (cs.cornell.edu)

The key idea to remember, if you’re studying Social Network Analysis, remember this definition:

A clique is a subset of nodes in which every pair of nodes is directly connected to each other.

And the hierarchy is:

Social Network → Subgroup → Clique → Maximal Clique → Maximum Clique

with the crucial distinction:

Clique vs. Community Detection

You can think about the relationship like this:

SOCIAL NETWORK
                          │
              ┌───────────┴───────────┐
              │                       │
          Communities              Cliques
              │                       │
     Dense / cohesive          Completely connected
              │                       │
    Connections may be missing   No internal edges missing
              │                       │
       More realistic            More restrictive
       for large networks        but highly cohesive

Clique-based methods can also be used as a building block for community detection. For example, approaches based on kk-cliques connect kk-cliques that overlap sufficiently and use those structures to identify communities. (Springer Link)

Clique vs. ordinary community

This distinction is very important in Social Network Analysis. Suppose we have a community of 10 people. They may interact frequently, but perhaps not everyone knows everyone else. That can still be a community.

A clique is much stricter: Every member must have a direct connection with every other member.

You can think of community as a Highly connected group
but some connections may be missing.
Whereas Clique is Completely connected group where NO internal connection is missing

A clique therefore has an internal edge density of Density=1 or 100%. because all possible internal edges exist. (ona-book.org)