cliques
The functions find cliques, ie. complete subgraphs in a graph
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.
- Keywords
- graphs
Usage
cliques(graph, min=NULL, max=NULL)
largest.cliques(graph)
maximal.cliques(graph, min=NULL, max=NULL)
clique.number(graph)
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.
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.
maximal.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.
clique.number
calculates the size of the largest clique(s).
The current implementation of these functions searches
for maximal independent vertex sets (see
independent.vertex.sets
) in the complementer graph.
Value
cliques
,largest.cliques
andclique.number
return a list containing numeric vectors of vertex ids. Each list element is a clique.clique.number
returns an integer constant.
concept
- Clique
- Maximal clique
- Largest clique
See Also
Examples
# this usually contains cliques of size six
g <- erdos.renyi.game(100, 0.3)
clique.number(g)
cliques(g, min=6)
largest.cliques(g)
# To have a bit less maximal cliques, about 100-200 usually
g <- erdos.renyi.game(100, 0.03)
maximal.cliques(g)