create.cmst.graph: Construct a Minimal Spanning Tree (MST) Completion Graph

In dgraphs: Data-Derived Graph Construction Utilities

Construct a Minimal Spanning Tree (MST) Completion Graph

Description

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.

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.

Value

An object of class mst_completion_graph, which is a list containing:

mst_adj_list

A list of length n, where element i contains the indices of vertices adjacent to vertex i in the MST.

mst_weight_list

A list of length n, where element i contains the edge weights corresponding to the adjacent vertices in mst_adj_list[[i]].

cmst_adj_list

A list of length n containing adjacency information for the completed MST graph.

cmst_weight_list

A list of length n containing edge weights for the completed MST graph.

mst_edge_weights

Numeric vector containing all unique MST edge weights.

cmst_distance_threshold

Numeric scalar containing the actual Euclidean distance threshold used for completion.

The returned object also has the following attributes:

q_thld

The quantile threshold used for MST completion.

pca

If PCA was applied, a list containing:

• original_dim: The original number of dimensions

• n_components: The number of PCA components used

• variance_explained: The proportion of variance explained

• cumulative_variance: Cumulative variance by component (if applicable)

call

The matched function call.

References

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

See Also

stats::prcomp() for principal component analysis.

Examples

set.seed(123)
X <- matrix(rnorm(60), nrow = 20, ncol = 3)
graph <- create.cmst.graph(X, verbose = FALSE)
graph$n_vertices
graph$n_edges

dgraphs documentation built on Aug. 21, 2026, 1:08 a.m.