Use this if you are using igraph from R
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.
cliques(graph, min = NULL, max = NULL) max_cliques(graph, min = NULL, max = NULL, subset = NULL, file = NULL)
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.
|
max |
Numeric constant, upper limit on the size of the cliques to find.
|
subset |
If not |
file |
If not |
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 neccessarily 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.
cliques
, largest_cliques
and clique_num
return a list containing numeric vectors of vertex ids. Each list element is
a clique.
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.
Tamas Nepusz ntamas@gmail.com and Gabor Csardi csardi.gabor@gmail.com
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
# 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)