Yog.Property.Clique (YogEx v0.97.0)

Copy Markdown View Source

Clique finding algorithms using the Bron-Kerbosch algorithm.

A clique is a subset of nodes where every pair of nodes is connected by an edge. Cliques represent tightly-knit communities or fully-connected subgraphs.

Algorithms

ProblemAlgorithmFunctionComplexity
Maximum cliqueBron-Kerbosch with pivotmax_clique/1O(3^(n/3))
All maximal cliquesBron-Kerboschall_maximal_cliques/1O(3^(n/3))
k-CliquesBron-Kerbosch with pruningk_cliques/2O(3^(n/3))

Key Concepts

  • Clique: Complete subgraph - every pair of vertices is adjacent
  • Maximal Clique: Cannot be extended by adding another vertex
  • Maximum Clique: Largest clique in the graph (NP-hard to find)
  • Clique Number: Size of the maximum clique, denoted ω(G)
  • Clique Cover: Partition of vertices into cliques

The Bron-Kerbosch Algorithm

A backtracking algorithm that recursively explores potential cliques using three sets:

  • R: Current clique being built
  • P: Candidates that can extend R (connected to all in R)
  • X: Excluded vertices (already processed)

Pivoting optimization: Choose a pivot vertex to reduce recursive calls, achieving the worst-case optimal O(3^(n/3)) bound.

Complexity Notes

Finding the maximum clique is NP-hard. The O(3^(n/3)) bound is tight - there exist graphs with exactly 3^(n/3) maximal cliques (Moon-Moser graphs).

  • Independent Set: Clique in the complement graph
  • Vertex Cover: Related via complement to independent set
  • Graph Coloring: Lower bounded by clique number

Use Cases

  • Social network analysis: Finding tightly-knit friend groups
  • Bioinformatics: Protein interaction clusters
  • Finance: Detecting collusion rings in trading
  • Recommendation: Finding groups with similar preferences
  • Compiler optimization: Register allocation (interference graphs)

Maximum Clique Visualization

A clique is a fully connected subgraph where every node is adjacent to every other node in the set.

graph G { bgcolor="transparent"; node [shape=circle, fontname="inherit"]; edge [fontname="inherit", fontsize=10]; subgraph cluster_clique { label="Maximum Clique (K4)"; color="#6366f1"; style=rounded; C1; C2; C3; C4; } // Clique edges (fully connected) C1 -- C2 [color="#6366f1", penwidth=2.5]; C1 -- C3 [color="#6366f1", penwidth=2.5]; C1 -- C4 [color="#6366f1", penwidth=2.5]; C2 -- C3 [color="#6366f1", penwidth=2.5]; C2 -- C4 [color="#6366f1", penwidth=2.5]; C3 -- C4 [color="#6366f1", penwidth=2.5]; // Other nodes and edges C1 -- O1 [style=dashed, color="#94a3b8"]; C2 -- O2 [style=dashed, color="#94a3b8"]; O1 -- O2 [style=dashed, color="#94a3b8"]; }
iex> alias Yog.Property.Clique
iex> graph = Yog.from_edges(:undirected, [
...>   {"C1", "C2", 1}, {"C1", "C3", 1}, {"C1", "C4", 1},
...>   {"C2", "C3", 1}, {"C2", "C4", 1}, {"C3", "C4", 1},
...>   {"C1", "O1", 1}, {"C2", "O2", 1}, {"O1", "O2", 1}
...> ])
iex> clique = Clique.max_clique(graph)
iex> MapSet.member?(clique, "C1") and MapSet.size(clique) == 4
true

Examples

# Create a complete graph K4
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_node(4, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 1, to: 4, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 4, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
iex> Yog.Property.Clique.max_clique(graph) |> MapSet.size()
4

References

Summary

Functions

all_maximal_cliques(graph)

Finds all maximal cliques in an undirected graph.

k_cliques(graph, k)

Finds all cliques of exactly size k in an undirected graph.

max_clique(graph)

Finds the maximum clique in an undirected graph.

Functions

all_maximal_cliques(graph)

@spec all_maximal_cliques(Yog.graph()) :: [MapSet.t(Yog.node_id())]

Finds all maximal cliques in an undirected graph.

A maximal clique is a clique that cannot be extended by adding another node.

Examples

# Triangle has one maximal clique
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
iex> Yog.Property.Clique.all_maximal_cliques(graph) |> length()
1

# Path graph: each edge is a maximal clique of size 2
iex> path = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> Yog.Property.Clique.all_maximal_cliques(path) |> length()
2
iex> # Empty graph has no cliques
iex> empty = Yog.undirected()
iex> Yog.Property.Clique.all_maximal_cliques(empty)
[]

Time Complexity

O(3^(n/3)) worst case

k_cliques(graph, k)

Finds all cliques of exactly size k in an undirected graph.

Uses a modified Bron-Kerbosch algorithm with early pruning.

Examples

# Complete graph K4 has 4 cliques of size 3 (triangles)
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_node(4, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 1, to: 4, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 4, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
iex> Yog.Property.Clique.k_cliques(graph, 3) |> length()
4
iex> # Find edges (cliques of size 2)
iex> Yog.Property.Clique.k_cliques(graph, 2) |> length()
6
iex> # k <= 0 returns empty list
iex> Yog.Property.Clique.k_cliques(graph, 0)
[]

Time Complexity

O(3^(n/3)) worst case

max_clique(graph)

@spec max_clique(Yog.graph()) :: MapSet.t(Yog.node_id())

Finds the maximum clique in an undirected graph.

Returns the largest subset of nodes where every pair is connected.

Examples

# Triangle (3-clique)
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
iex> Yog.Property.Clique.max_clique(graph) |> MapSet.size()
3

# Path graph (no cliques larger than 2)
iex> path = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> Yog.Property.Clique.max_clique(path) |> MapSet.size()
2

# Empty graph
iex> empty = Yog.undirected()
iex> Yog.Property.Clique.max_clique(empty) |> MapSet.size()
0

Time Complexity

O(3^(n/3)) worst case