create.cknn.graph: Compute a Continuous-kNN Graph

In dgraphs: Data-Derived Graph Construction Utilities

Compute a Continuous-kNN Graph

Description

Creates an undirected continuous-kNN graph using local scale distances. Let \sigma_i be the distance from observation i to its k.scale-th non-self nearest neighbor. Vertices are adjacent when

\|x_i - x_j\|_2 \le \delta \sqrt{\sigma_i\sigma_j}.

This is a convenience wrapper around create.rknn.graph() with type = "adaptive.radius" and radius.rule = "geomean". It is useful as a named data-derived graph construction in geodesic reconstruction benchmarks.

Usage

create.cknn.graph(
  X,
  k.scale,
  delta = 1,
  radius.search = c("ann", "all.pairs"),
  return.timing = FALSE,
  graph.detail = c("full", "minimal"),
  prune.method = c("none", "local.geodesic", "global.geodesic.ratio"),
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  prune.tau = 1.05,
  prune.local.k = NULL,
  with.pruned.edge.stats = FALSE,
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

Arguments

X	Numeric matrix or data frame with observations in rows.
k.scale	Positive integer smaller than nrow(X). Defines local scale distances \sigma_i.
delta	Positive numeric scalar multiplying the geometric-mean adaptive radius.
radius.search	Character scalar. "ann" uses the bundled ANN kd-tree exact radius-search backend inherited from create.rknn.graph(). "all.pairs" uses the direct O(n^2) reference path.
return.timing	Logical scalar. If TRUE, attach the same construction timing table returned by create.rknn.graph(), including ANN setup, local-scale search, fixed-radius candidate search, edge materialization, and graph finalization when radius.search = "ann".
graph.detail	Character scalar. "full" returns the complete graph lifecycle object. "minimal" returns only core graph fields and is allowed only with prune.method = "none" and connect.components = FALSE.
prune.method	Character scalar. "none" disables geometric pruning. "local.geodesic" applies the experimental local geometric pruning stage before optional MST connectivity repair. "global.geodesic.ratio" applies whole-graph geodesic-ratio pruning before optional MST connectivity repair.
max.path.edge.ratio.deviation.thld	Numeric scalar in ⁠[0, 0.2)⁠. For prune.method = "global.geodesic.ratio", an edge may be removed when the shortest alternative path is at most 1 + max.path.edge.ratio.deviation.thld times the direct edge length.
path.edge.ratio.percentile	Numeric scalar in ⁠[0, 1]⁠. For prune.method = "global.geodesic.ratio", only edges at or above this edge length percentile are considered.
prune.tau	Numeric scalar greater than 1. For local geometric pruning, an edge may be removed when a retained local alternative path is at most this multiplicative factor times the direct edge length.
prune.local.k	Integer scalar or NULL. Number of nearest neighbors used to form local neighborhoods for pruning. For fixed-radius graphs, NULL uses the median positive raw graph degree, clipped to ⁠[1, n - 1]⁠. For adaptive-radius graphs, NULL defaults to k.scale.
with.pruned.edge.stats	Logical scalar. If TRUE, return a data frame with one row per locally pruned edge.
connect.components	Logical scalar. If TRUE, add MST bridge edges so the final graph is connected whenever possible.
connect.method	Character scalar. "component.mst" adds exact shortest inter-component bridges. "component.mst.ann" tries sparse ANN bridge candidates before automatic exact fallback. "global.mst" unions the graph with the full Euclidean MST.
bridge.k	Integer scalar or NULL. Initial ANN bridge neighborhood size for connect.method = "component.mst.ann".
bridge.k.max	Integer scalar or NULL. Maximum ANN bridge neighborhood size before exact fallback.
bridge.growth	Numeric scalar greater than 1. Multiplicative growth factor for ANN bridge neighborhoods.

Value

A list inheriting from "cknn_graph" and "adaptive_radius_graph". It contains the same lifecycle fields as create.rknn.graph() with type = "adaptive.radius", radius_rule = "geomean", radius_factor = delta, and graph_rule = "continuous.knn".

Examples

X <- matrix(c(0, 1, 3), ncol = 1)
create.cknn.graph(X, k.scale = 1, delta = 1)$edge_matrix

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