cliques {igraph} | R Documentation

## 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)
    largest.cliques(graph)
    maximal.cliques(graph)
    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` and `clique.number` return a list containing numeric vectors of vertex ids. Each list element is a clique.
`clique.number` returns an integer constant.

### Author(s)

Tamas Nepusz ntamas@rmki.kfki.hu and Gabor Csardi csardi@rmki.kfki.hu for the R interface and the manual page.

### See Also

`independent.vertex.sets`

### 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)

[Package igraph version 0.5.2 Index]