# 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

1 2 3 4 5 6 |

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

`qpCliqueOutput` |
output from a previous call to |

`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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | ```
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
``` |