qpGetCliques {qpgraph}R Documentation

Clique list

Description

Finds the set of (maximal) cliques of a given undirected graph.

Usage

qpGetCliques(g, clqspervtx=FALSE, verbose=TRUE)

Arguments

g either a graphNEL object or an incidence matrix of the given undirected graph.
clqspervtx logical; if TRUE then the resulting list returned by the function includes additionally p entries at the beginning (p=number of variables) each corresponding to a vertex in the graph and containing the indices of the cliques where that vertex belongs to; if FALSE these additional entries are not included (default).
verbose show progress on calculations.

Details

To find the list of all (maximal) cliques in an undirected graph is an NP-complete problem which means that its computational cost is bounded by an exponential running time (Karp, 1972). For this reason, this is an extremely time and memory consuming computation for large dense graphs. The current implementation uses C code from the GNU GPL Cliquer library by Niskanen and Ostergard (2003).

Value

A list of maximal cliques. When clqspervtx=TRUE the first p entries (p=number of variables) contain, each of them, the indices of the cliques where that particular vertex belongs to.

Author(s)

R. Castelo

References

Castelo, R. and Roverato, A. A robust procedure for Gaussian graphical model search from microarray data with p larger than n. J. Mach. Learn. Res., 7:2621-2650, 2006.

Niskanen, S. Ostergard, P. Cliquer User's Guide, Version 1.0. Communications Laboratory, Helsinki University of Technology, Espoo, Finland, Tech. Rep. T48, 2003. (http://users.tkk.fi/~pat/cliquer.html)

Karp, R.M. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher (eds.): Complexity of Computer Computations, 85-103, New York: Plenum, 1972.

See Also

qpCliqueNumber qpIPF

Examples

nVertices <- 50 # number of vertices
maxCon <- 5  # maximum connectivity per vertex

I <- qpRndGraph(n.vtx=nVertices, n.bd=maxCon)

clqs <- qpGetCliques(I, verbose=FALSE)

summary(unlist(lapply(clqs, length)))

maxCon <- 10  # maximum connectivity per vertex

I <- qpRndGraph(n.vtx=nVertices, n.bd=maxCon)

clqs <- qpGetCliques(I, verbose=FALSE)

summary(unlist(lapply(clqs, length)))


[Package qpgraph version 1.0.0 Index]