Construct a Minimal Spanning Tree (MST) Completion Graph

Constructs a completion of the Minimal Spanning Tree (MST) graph from a numeric data matrix. The graph is constructed in two steps: first, a MST is built connecting all data points using minimal total edge length; then, additional edges are added between any pair of points whose Euclidean distance is less than or equal to a quantile threshold based on the MST edge length distribution.

Usage

create.cmst.graph(
  X,
  q.thld = 0.9,
  pca.dim = 100,
  variance.explained = 0.99,
  verbose = TRUE
)

Arguments

X: A numeric matrix or data frame of shape \(n \times d\), where each row represents a data point in d-dimensional space.
q.thld: Numeric scalar between 0 and 1 (exclusive). The quantile threshold for MST completion. Edges are added between points whose distance is less than or equal to the q.thld-quantile of MST edge weights. Default is 0.9.
pca.dim: Positive integer or NULL. If provided and ncol(X) > pca.dim, dimensionality is reduced to this many principal components before graph construction. Must be less than min(n-1, p) where n is the number of observations and p is the number of variables. Default is 100.
variance.explained: Numeric between 0 and 1 (exclusive) or NULL. If provided, selects the minimal number of PCA components such that this proportion of total variance is retained (up to pca.dim components). Ignored if pca.dim is NULL. Default is 0.99.
verbose: Logical. If TRUE, prints progress messages during computation. Default is TRUE.

Value

A dgraph with raw (MST) and final (completed) stages. Use graph accessors to inspect topology and lengths; construction details are in metadata.

Details

The MST completion process enhances connectivity in the original MST by adding edges between vertices that are "close" according to the distance distribution in the MST. This can be useful for creating more robust graph representations of data that maintain local structure while avoiding long-range connections.

When PCA is applied (either through pca.dim or variance.explained), the data is first centered and projected onto the leading principal components before graph construction. This can significantly reduce computation time for high-dimensional data while preserving the most important variation.

References

Gower, J. C., & Ross, G. J. S. (1969). Minimum spanning trees and single linkage cluster analysis. Applied Statistics, 18(1), 54-64.

Examples

set.seed(123)
X <- matrix(rnorm(60), nrow = 20, ncol = 3)
graph <- create.cmst.graph(X, verbose = FALSE)
graph.order(graph)
#> [1] 20
nrow(graph.edges(graph))
#> [1] 42