qpClique: Complexity of the resulting qp-graphs

In rcastelo/qpgraph: Estimation of genetic and molecular regulatory networks from high-throughput genomics data

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

rcastelo/qpgraph documentation built on Oct. 28, 2024, 5:15 a.m.