Compute a Radius-kNN Graph

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

A dgraph, with constructor class radius_graph for fixed radii or adaptive_radius_graph for adaptive radii. Use graph accessors for topology, lengths and retained stages; construction diagnostics are in metadata.

Examples

X <- matrix(c(0, 1, 3), ncol = 1)
as.matrix(graph.edges(create.rknn.graph(X, type = "fixed", radius = 1.1))[, c("from", "to")])
#>      from to
#> [1,]    1  2
as.matrix(graph.edges(create.rknn.graph(X, type = "adaptive.radius", k.scale = 1))[, c("from",
"to")])
#>      from to
#> [1,]    1  2
#> [2,]    2  3