igraph: cliques – R documentation

Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!

cliques

The functions find cliques, ie. complete subgraphs in a graph

Description

These functions find all, the largest or all the maximal cliques in an undirected graph. The size of the largest clique can also be calculated.

Usage

cliques(graph, min = NULL, max = NULL)

max_cliques(graph, min = NULL, max = NULL, subset = NULL, file = NULL)

Arguments

`graph`	The input graph, directed graphs will be considered as undirected ones, multiple edges and loops are ignored.
`min`	Numeric constant, lower limit on the size of the cliques to find. `NULL` means no limit, ie. it is the same as 0.
`max`	Numeric constant, upper limit on the size of the cliques to find. `NULL` means no limit.
`subset`	If not `NULL`, then it must be a vector of vertex ids, numeric or symbolic if the graph is named. The algorithm is run from these vertices only, so only a subset of all maximal cliques is returned. See the Eppstein paper for details. This argument makes it possible to easily parallelize the finding of maximal cliques.
`file`	If not `NULL`, then it must be a file name, i.e. a character scalar. The output of the algorithm is written to this file. (If it exists, then it will be overwritten.) Each clique will be a separate line in the file, given with the numeric ids of its vertices, separated by whitespace.

Details

cliques find all complete subgraphs in the input graph, obeying the size limitations given in the min and max arguments.

largest_cliques finds all largest cliques in the input graph. A clique is largest if there is no other clique including more vertices.

max_cliques finds all maximal cliques in the input graph. A clique in maximal if it cannot be extended to a larger clique. The largest cliques are always maximal, but a maximal clique is not necessarily the largest.

count_max_cliques counts the maximal cliques.

clique_num calculates the size of the largest clique(s).

The current implementation of these functions searches for maximal independent vertex sets (see ivs) in the complementer graph.

Value

cliques, largest_cliques and clique_num return a list containing numeric vectors of vertex ids. Each list element is a clique, i.e. a vertex sequence of class igraph.vs.

max_cliques returns NULL, invisibly, if its file argument is not NULL. The output is written to the specified file in this case.

clique_num and count_max_cliques return an integer scalar.

Author(s)

Tamas Nepusz ntamas@gmail.com and Gabor Csardi csardi.gabor@gmail.com

References

For maximal cliques the following algorithm is implemented: David Eppstein, Maarten Loffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time. https://arxiv.org/abs/1006.5440

Examples

# this usually contains cliques of size six
g <- sample_gnp(100, 0.3)
clique_num(g)
cliques(g, min=6)
largest_cliques(g)

# To have a bit less maximal cliques, about 100-200 usually
g <- sample_gnp(100, 0.03)
max_cliques(g)

igraph

Network Analysis and Visualization

v1.2.10

GPL (>= 2)

Authors

See AUTHORS file.

Initial release