qpClique {qpgraph} | R Documentation

## Complexity of the resulting qp-graphs

### Description

Calculates and plots the size of the largest maximal clique (the so-called clique number or maximum clique size) as function of the non-rejection rate.

### Usage

    qpClique(nrrMatrix, n=NA, threshold.lim=c(0,1), breaks=5, plot=TRUE,
             exact.calculation=TRUE, approx.iter=100,
             qpCliqueOutput=NULL, density.digits=0,
             logscale.clqsize=FALSE,
             titleclq="maximum clique size as function of threshold",
             verbose=FALSE)

### Arguments

`nrrMatrix` | matrix of non-rejection rates.
`n` | number of observations from where the non-rejection rates were estimated.
`threshold.lim` | range of threshold values on the non-rejection rate.
`breaks` | either a number of threshold bins or a vector of threshold breakpoints.
`plot` | logical; if TRUE makes a plot of the result; if FALSE it does not.
`exact.calculation` | logical; if TRUE then the exact clique number is calculated; if FALSE then a lower bound is given instead.
`approx.iter` | number of iterations to be employed in the calculation of the lower bound (i.e., only applies when `exact.calculation=FALSE`).
`qpCliqueOutput` | output from a previous call to `qpClique`. This allows one to plot the result changing some of the plotting parameters without having to do the calculation again.
`density.digits` | number of digits in the reported graph densities.
`logscale.clqsize` | logical; if TRUE then the scale for the maximum clique size is logarithmic which is useful when working with more than 1000 variables; FALSE otherwise (default).
`titleclq` | main title to be shown in the plot.
`verbose` | show progress on calculations.

### Details

The estimate of the complexity of the resulting qp-graphs is calculated as the area enclosed under the curve of maximum clique sizes.

The maximum clique size, or clique number, is obtained by calling the function `qpCliqueNumber` The calculation of the clique number of an undirected graph is an NP-complete problem which means that its computational cost is bounded by an exponential running time (Pardalos and Xue, 1994). Therefore, giving breakpoints between 0.95 and 1.0 may result into very dense graphs which can lead to extremely long execution times. If it is necessary to look at that range of breakpoints it is recommended either to use the lower bound on the clique number (`exact.calculation=FALSE`) or to look at `qpGraphDensity`.

### Value

A list with the maximum clique size and graph density as function of threshold, an estimate of the complexity of the resulting qp-graphs across the thresholds, the threshold on the non-rejection rate that provides a maximum clique size strictly smaller than the sample size n and the resulting maximum clique size.

### Author(s)

R. Castelo and A. Roverato

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

Pardalos, P.M. and Xue, J. The maximum clique problem. J. Global Optim., 4:301-328, 1994.

### See Also

`qpCliqueNumber` `qpGraphDensity`

### Examples

    require(mvtnorm)

    nVar <- 50  ## number of variables
    maxCon <- 5 ## maximum connectivity per variable
    nObs <- 30  ## number of observations to simulate

    set.seed(123)

    A <- qpRndGraph(p=nVar, d=maxCon)
    Sigma <- qpG2Sigma(A, rho=0.5)
    X <- rmvnorm(nObs, sigma=as.matrix(Sigma))

    ## the higher the q the less complex the qp-graph

    nrr.estimates <- qpNrr(X, q=1, verbose=FALSE)

    qpClique(nrr.estimates, plot=FALSE)$complexity

    nrr.estimates <- qpNrr(X, q=5, verbose=FALSE)

    qpClique(nrr.estimates, plot=FALSE)$complexity

[Package qpgraph version 2.14.0 Index]