FindClique

FindClique[g]

finds a largest clique in the graph g.

FindClique[g,n]

finds a clique containing at most n vertices.

FindClique[g,{n}]

finds a clique containing exactly n vertices.

FindClique[g,{n_min,n_max}]

finds a clique containing between n_min and n_max vertices.

FindClique[g,nspec,s]

finds at most s cliques.

FindClique[{g,v},…]

finds cliques that include the vertex v only.

FindClique[{vw,…},…]

uses rules vw to specify the graph g.

Details

A clique is a maximal set of vertices where the corresponding subgraph is a complete graph.

FindClique returns a list of cliques.
FindClique will return an empty list if there is no clique.
FindClique[…,nspec,All] finds all the cliques.
For weighted graphs, FindClique gives a set of vertices with maximum sum of vertex weights.
FindClique works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.

Background & Context

FindClique finds a set of maximal cliques of specified size in a graph, returned as a list of vertex lists. Here, a clique is a subset of vertices such that the corresponding induced subgraph is a complete graph. Cliques are used in project selection, pattern matching, finance, and network analysis. In general, FindClique[g,nspec,s] finds a set of s maximal cliques of specified size nspec in a graph g.
There are two especially important types of cliques: maximum and maximal. Note these are not equivalent. A maximum clique is a clique containing the largest possible number of vertices for a given graph. In contrast, a maximal clique set is a clique that cannot be extended by including one more adjacent vertices, meaning it is not a subset of a larger clique. A maximum clique is therefore always maximal (since it obviously cannot be extended if it is already of the maximum size), but the converse is not necessarily true. To confuse the terminology even more, some authors refer to maximum cliques simply as "cliques".
FindClique can find maximal cliques of different sizes. FindClique can also find a single maximal clique of specified size, a specified number of cliques, or all such cliques.
FindClique[g] finds a single maximum clique of a graph g, FindClique[g,Length/@FindClique[g],s] finds at most s, and FindClique[g,Length/@FindClique[g],All] finds all such cliques. The size of a maximum clique of a graph g is known as its clique number, and the problem of finding the size of a maximum clique for a given graph is NP-complete, meaning computation can be exponentially slow.
FindClique[g,Infinity] finds a single maximal clique of a graph g, FindClique[g,Infinity,s] finds at most s, and FindClique[g,Infinity,All] finds all such cliques. Maximal cliques are important in graph theoretic applications, including graph coloring and fractional graph coloring.
Not-necessarily-maximal cliques cannot be found directly using FindClique but can be simplistically enumerated by taking the union over the collection of all subsets of all maximal cliques.
A maximal independent vertex set (which can be found using FindIndependentVertexSet) of a graph is equivalent to a maximal clique on its GraphComplement. A collection of vertices vlist of a graph g can be tested to see if it is a clique (without the requirement that it also be maximal) using CompleteGraphQ[g,vlist]. FindKClique, FindKClan, and FindKClub find clique-like structures that allow less-than-complete connections in subgraphs.

Examples

open allclose all

Basic Examples (2)

Find a largest clique in a graph:

Show the clique:

Find all cliques:

Scope (14)

Specification (8)

FindClique works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Mixed graphs:

Find a largest clique:

Use rules to specify the graph:

FindClique works with large graphs:

Enumeration (6)

A clique containing exactly 3 vertices:

A clique containing at most 2 vertices:

A clique containing between 3 and 5 vertices:

A largest clique that includes a given vertex:

Find all cliques in a graph:

FindClique gives an empty list if there is no clique:

Applications (5)

Highlight all cliques in a graph:

Find a largest immediate family in a network consisting of the closest relatives, including parents, siblings, and children:

Highlight the clique:

A network of books linked by the same buyers on Amazon.com. Find a largest selection of books frequently bought together that includes The Clinton Wars:

Find terrorist cells in the 1998 East Africa embassy attack network:

Show cooperating terrorist cells:

Find external contacts to isolate the Dar es Salaam attack cell:

Find members of the Dow Jones Industrial Average whose returns tend to move in sync:

First compute the correlation of returns since the beginning of this year:

Build a graph with edges between stocks having a correlation coefficient above a chosen :