create.rknn.graph: Compute a Radius-kNN Graph

In dgraphs: Data-Derived Graph Construction Utilities

Compute a Radius-kNN Graph

Description

Creates an undirected Euclidean radius graph from a numeric data matrix. Use type = "fixed" for a fixed-radius graph, where vertices i and j are adjacent exactly when their Euclidean distance is at most radius. Use type = "adaptive.radius" for an adaptive-radius graph based on observation-specific local scale distances.

Usage

create.rknn.graph(
  X,
  type = c("fixed", "adaptive.radius"),
  radius = NULL,
  k.scale = NULL,
  radius.factor = 1,
  radius.rule = c("max", "min", "geomean"),
  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.
type	Character scalar. "fixed" builds a fixed-radius graph using radius. "adaptive.radius" builds an adaptive-radius graph using k.scale, radius.factor, and radius.rule.
radius	Positive numeric scalar. Edges are included when \|x_i - x_j\|_2 \le radius. Required for type = "fixed".
k.scale	Positive integer smaller than nrow(X). Defines local scale distances \sigma_i. Required for type = "adaptive.radius".
radius.factor	Positive numeric scalar multiplying the adaptive radius.
radius.rule	Character scalar. "max" uses d_{ij} \le radius.factor \max(\sigma_i,\sigma_j); "min" uses d_{ij} \le radius.factor \min(\sigma_i,\sigma_j); and "geomean" uses d_{ij} \le radius.factor \sqrt{\sigma_i\sigma_j}. The "geomean" rule is the continuous-kNN support rule.
radius.search	Character scalar. "ann" uses the bundled ANN kd-tree to perform exact fixed-radius candidate searches before applying the pair-specific adaptive-radius rule. "all.pairs" uses the direct O(n^2) pair scan and is retained as a reference path. Used only for type = "adaptive.radius".
return.timing	Logical scalar. If TRUE, attach a construction timing table for adaptive-radius graphs.
graph.detail	Character scalar. "full" returns the complete graph lifecycle object for adaptive-radius graphs. "minimal" returns only the graph fields needed by fitting code and is currently allowed only for adaptive-radius graphs 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

For type = "fixed", a list of class "radius_graph". For type = "adaptive.radius", a list of class "adaptive_radius_graph". Both contain adjacency lists, edge weights, edge matrix, and component diagnostics. The final graph is stored in adj_list/weight_list; raw and pruned lifecycle graph stages are stored in corresponding ⁠raw_*⁠/⁠pruned_*⁠ fields when graph.detail = "full".

Examples

X <- matrix(c(0, 1, 3), ncol = 1)
create.rknn.graph(X, type = "fixed", radius = 1.1)$edge_matrix
create.rknn.graph(X, type = "adaptive.radius", k.scale = 1)$edge_matrix

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