qpRndGraph {qpgraph} | R Documentation

## Undirected random d-regular graphs

### Description

Samples an undirected d-regular graph approximately uniformly at random.

### Usage

    qpRndGraph(p=6, d=2, labels=1:p, exclude=NULL, verbose=FALSE,
               return.type=c("adjacency.matrix", "edge.list", "graphBAM", "graphNEL"),
               R.code.only=FALSE)

### Arguments

`p` | number of vertices.
`d` | degree of every vertex.
`labels` | vertex labels.
`exclude` | vector of vertices inducing edges that should be excluded from the sampled d-regular graph.
`verbose` | show progress on the calculations.
`return.type` | class of object to be returned by the function
`R.code.only` | logical; if `FALSE` then the faster C implementation is used (default); if `TRUE` then only R code is executed.

### Details

This function implements the algorithm from Steger and Wormald (1999) for sampling undirected d-regular graphs from a probability distribution of all d-regular graphs on p vertices which is approximately uniform. More concretely, for all vertex degree values d that grow as a small power of p, all d-regular graphs on p vertices will have in the limit the same probability as p grows large. Steger and Wormald (1999, pg. 396) believe that for d >> sqrt(p) the resulting probability distribution will no longer be approximately uniform.

This function is provided in order to generate a random undirected graph as input to the function `qpG2Sigma` which samples a random covariance matrix whose inverse (aka, precision matrix) has zeroes on those cells corresponding to the missing edges in the input graph. d-regular graphs are useful for working with synthetic graphical models for two reasons: one is that d-regular graph density is a linear function of d and the other is that the minimum connectivity degree of two disconnected vertices is an upper bound of their outer connectivity (see Castelo and Roverato, 2006, pg. 2646).

### Value

The adjacency matrix of the resulting graph.

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

Steger, A. and Wormald, N.C. Generating random regular graphs quickly, Combinatorics, Probab. and Comput., 8:377-396.

### See Also

`qpG2Sigma`

### Examples

    set.seed(123)

    A <- qpRndGraph(p=50, d=3)

    summary(apply(A, 1, sum))

[Package qpgraph version 2.16.0 Index]