Get cliques of an undirected graph

Return a list of (maximal) cliques of an undirected graph.

get_cliques(object)

max_cliqueMAT(amat)

getCliques(object)

maxCliqueMAT(amat)

maxClique(object)

Arguments

object

An undirected graph represented either as an igraph object, a (dense) matrix, a (sparse) dgCMatrix

amat

An adjacency matrix.

Value

A list.

Details

In graph theory, a clique is often a complete subset of a graph. A maximal clique is a clique which can not be enlarged. In statistics (and that is the convention we follow here) a clique is usually understood to be a maximal clique.

Finding the cliques of a general graph is an NP complete problem. Finding the cliques of triangualted graph is linear in the number of cliques.

The workhorse is the max_cliqueMAT function which calls the maxClique function in the RBGL package.

Synonymous functions

For backward compatibility with downstream packages we have the following synonymous functions:

• getCliques = get_cliques

• maxCliqueMAT = max_cliqueMAT

See also

ug, dag, mcs, mcsMAT, rip, ripMAT, moralize, moralizeMAT

Author

Søren Højsgaard, sorenh@math.aau.dk

Examples

uG0 <- ug(~a:b + b:c + c:d + d:e + e:f + f:a)
get_cliques(uG0)
#> [[1]]
#> [1] "a" "f"
#> 
#> [[2]]
#> [1] "a" "b"
#> 
#> [[3]]
#> [1] "b" "c"
#> 
#> [[4]]
#> [1] "c" "d"
#> 
#> [[5]]
#> [1] "d" "e"
#> 
#> [[6]]
#> [1] "e" "f"
#> 

uG1 <- as(uG0, "igraph")
get_cliques(uG1)
#> [[1]]
#> [1] "a" "f"
#> 
#> [[2]]
#> [1] "a" "b"
#> 
#> [[3]]
#> [1] "b" "c"
#> 
#> [[4]]
#> [1] "c" "d"
#> 
#> [[5]]
#> [1] "d" "e"
#> 
#> [[6]]
#> [1] "e" "f"
#> 

uG2 <- as(uG0, "matrix") 
get_cliques(uG2)
#> [[1]]
#> [1] "a" "f"
#> 
#> [[2]]
#> [1] "a" "b"
#> 
#> [[3]]
#> [1] "b" "c"
#> 
#> [[4]]
#> [1] "c" "d"
#> 
#> [[5]]
#> [1] "d" "e"
#> 
#> [[6]]
#> [1] "e" "f"
#> 

uG3 <- as(uG1, "dgCMatrix") 
get_cliques(uG3)
#> [[1]]
#> [1] "a" "f"
#> 
#> [[2]]
#> [1] "a" "b"
#> 
#> [[3]]
#> [1] "b" "c"
#> 
#> [[4]]
#> [1] "c" "d"
#> 
#> [[5]]
#> [1] "d" "e"
#> 
#> [[6]]
#> [1] "e" "f"
#>