Identify Basins of Attraction of Local Minima on a Weighted Graph

Computes the basins of attraction for local minima on a weighted graph using a gradient flow algorithm. Each basin consists of vertices that would flow towards a particular local minimum following the steepest descent path.

Usage

# S3 method for class 'basins'
lmin(object, weight.list = NULL, y, lmin.list, verbose = FALSE, ...)

Arguments

object

List where object[[i]] contains indices of vertices adjacent to vertex i. Must be a valid adjacency list representation.

weight.list

List where weight.list[[i]] contains positive weights of edges from vertex i to corresponding vertices in object[[i]]. If NULL, uniform weights of 1 are used.

y

Numeric vector of values at each vertex. Must have the same length as object. Can contain NA values which are treated as positive infinity.

lmin.list

List where each element contains:

lmin:

Index of the local minimum vertex

vertices:

Set of vertices forming the initial basin (usually the local minimum and its neighborhood)

label:

Character label for the basin

verbose

Logical; if TRUE, prints progress messages during computation. Default is FALSE.

...

Additional arguments (currently ignored).

Value

A named list of basins of attraction, where names correspond to labels in lmin.list. Each element is an integer vector of vertex indices belonging to that basin, sorted in ascending order.

Details

The algorithm expands basins iteratively from local minima by examining boundary vertices and adding neighboring vertices that satisfy a threshold criterion. The threshold is computed as a weighted average of values at vertices already in the basin.

Edge weights influence both the threshold calculation and the decision to include new vertices. Higher weights indicate stronger connections and give more influence in the weighted averaging process.

For local minima, vertices are added if their values are above the threshold, representing flow towards lower values.

See also

set.boundary, lmax.basins, compute.graph.gradient.flow

Examples

if (FALSE) { # \dontrun{
# Create a weighted graph
adj.list <- list(
  c(2, 3),      # vertex 1 neighbors
  c(1, 3, 4),   # vertex 2 neighbors
  c(1, 2, 5),   # vertex 3 neighbors
  c(2, 5),      # vertex 4 neighbors
  c(3, 4)       # vertex 5 neighbors
)

# Values at vertices
y <- c(0.5, 0.8, 0.3, 1.2, 0.2)

# Define local minima
lmin.list <- list(
  list(lmin = 5, vertices = c(5), label = "min1"),
  list(lmin = 3, vertices = c(3), label = "min2")
)

# Compute basins
basins <- lmin.basins(adj.list, weight.list = NULL, y, lmin.list)
} # }