Identify Basins of Attraction of Local Maxima on a Weighted Graph

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

Usage

# S3 method for class 'basins'
lmax(object, weight.list = NULL, y, lmax.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 negative infinity.

lmax.list

List where each element contains:

lmax:

Index of the local maximum vertex

vertices:

Set of vertices forming the initial basin (usually the local maximum 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 lmax.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 maxima 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.

The algorithm terminates when no new vertices can be added to any basin, ensuring convergence in finite graphs.

See also

set.boundary, lmin.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
)

# Edge weights (optional)
weight.list <- list(
  c(1.0, 0.5),     # weights for edges from vertex 1
  c(1.0, 0.8, 1.2), # weights for edges from vertex 2
  c(0.5, 0.8, 1.0), # weights for edges from vertex 3
  c(1.2, 1.5),      # weights for edges from vertex 4
  c(1.0, 1.5)       # weights for edges from vertex 5
)

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

# Define local maxima
lmax.list <- list(
  list(lmax = 4, vertices = c(4), label = "max1"),
  list(lmax = 5, vertices = c(5), label = "max2")
)

# Compute basins
basins <- lmax.basins(adj.list, weight.list, y, lmax.list, verbose = TRUE)
} # }