cliques

0th

Percentile

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

concept

  • Clique
  • Maximal clique
  • Largest clique

See Also

independent.vertex.sets

Aliases
  • cliques
  • largest.cliques
  • maximal.cliques
  • clique.number
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)
Documentation reproduced from package igraph, version 0.5.2-2, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.