Maximal Cliques

Version 1.8.0.0 (3.55 KB) by Ahmad
Finds all the maximal complete sub-graphs (maximal cliques) in a graph
3.3
(4)
3.5K Downloads
Updated 31 May 2010

View License

The graph passed must be an upper rectangular square matrix. Each row of a matrix denotes the presence of an edge with 1, and an absence of it with 0. The row and col no. of an edge denotes the connecting nodes. Given this matrix, this function finds all the maximal complete sub-graph (a set of nodes amongst all the nodes which form a complete sub-graph i.e. every node connects to every other) also known as cliques. A maximal graph is returned since every complete sub-graph will also have smaller complete sub-graphs inside itself. NOTE: this function would not return single node sub-graphs, although every isolated node, in concept, also forms a complete sub-graph.

The function returns all the sub-graphs in a cell-array, where each row denotes a new sub-graph

Cite As

Ahmad (2024). Maximal Cliques (https://www.mathworks.com/matlabcentral/fileexchange/19889-maximal-cliques), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2009b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Graph and Network Algorithms in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Version Published Release Notes
1.8.0.0

Complete revamp of the algorithm. Affords computation on bigger graphs + on average 70% speedup on both sparse and dense adjacency graphs! Plus now the user can provide the maximum graph size wanted for maximal cliques.
1.7.0.0

Some speedups!
1.6.0.0

Fixed some critical problems which didn't give the full set of maximal cliques (thanks Carlos). Although the code is now becoming slow - so tune in later for a revamp of the algo.
1.5.0.0

Was missing some maximal cliques whose nodes were part of some overlapping cliques. Thanks to Matej
1.2.0.0

Fixed bug ... was missing some maximal cliques whose nodes were part of some overlapping cliques. Thanks to
1.1.0.0

Bug in nchoosek, while looping to get connecting nodes.
Plus put a warning if a large computation is given for nchoosek
1.0.0.0

Fixed critical bug