Cluster Local Extrema Based on Basin Overlap

Identifies clusters of local extrema (either maxima or minima) whose basins of attraction exhibit substantial overlap or containment relationships. The function uses basin labels from summary.basins_of_attraction to ensure consistency with other analyses and returns both numeric cluster assignments and a convenient cluster membership list.

Usage

cluster.local.extrema(
  basins.obj,
  adj.list,
  edgelen.list,
  extrema.type = "max",
  overlap.threshold = 0.1
)

Arguments

basins.obj: An object of class "basins_of_attraction" returned by compute.basins.of.attraction. This object contains the complete basin structure for both local minima and local maxima.
adj.list: Adjacency list of the graph.
edgelen.list: A list of numeric vectors containing edge lengths. Element i contains the lengths of edges incident to vertex i. Must have length equal to the number of vertices in the graph. This parameter is passed to summary.basins_of_attraction to generate consistent basin labels and compute basin characteristics.
extrema.type: Character string specifying which type of extrema to cluster. Must be either "max" for local maxima (descending basins) or "min" for local minima (ascending basins). Default is "max".
overlap.threshold: Numeric value in the interval $[0, 1]$ specifying the threshold for the overlap distance below which basins are considered similar and connected in the clustering graph. Smaller values produce more conservative clustering with tighter similarity requirements. For example, a threshold of 0.15 requires that basins share at least 85% overlap relative to the smaller basin. Default is 0.1, corresponding to 90% overlap.

Value

A list containing the clustering results with the following components:

cluster.assignments: Named integer vector where names are basin labels from summary.basins_of_attraction (M1, M2, ... for maxima or m1, m2, ... for minima) and values are cluster identifiers. Basins with the same cluster identifier belong to the same cluster.
clusters: Named list where names are cluster identifiers (as character strings) and values are character vectors of basin labels belonging to each cluster. This provides a convenient inverse mapping from clusters to their member basins.
overlap.distances: Symmetric matrix of pairwise overlap distances between all basins. Rows and columns are labeled with basin identifiers from summary.basins_of_attraction. Diagonal entries are zero.
basin.vertices: Named list where each element contains the integer vector of vertex indices belonging to the corresponding basin. Names match basin labels from summary.basins_of_attraction.
overlap.graph: List with components adj_list and weight_list representing the overlap graph structure. In this graph, vertices correspond to basins and edges connect basins whose overlap distance is below the threshold. Edge weights are the overlap distances. Vertex names in the adjacency list match basin labels.
basin.summary: Data frame from summary.basins_of_attraction filtered to include only the extrema of the specified type. Contains detailed information about each basin including label, vertex, value, basin size, and density metrics.
n.clusters: Integer scalar giving the total number of distinct clusters identified.

Details

The clustering problem arises naturally in Morse-Smale analysis when multiple local extrema are positioned close together in the function landscape, creating basins that either overlap substantially or exhibit containment relationships where a smaller basin lies entirely within a larger one. Traditional similarity measures like the Jaccard index may fail to detect such containment patterns because they normalize by the union size rather than the smaller set size.

We address this by employing the overlap coefficient, also known as the Szymkiewicz-Simpson index, which measures basin similarity through the ratio of intersection size to the minimum basin size. For two basins $A$ and $B$, the overlap coefficient is defined as $$\text{OC}(A,B) = \frac{|A \cap B|}{\min(|A|, |B|)}$$ This measure equals one when either basin is completely contained in the other, making it ideal for detecting nested or highly overlapping basin structures.

The overlap distance, given by $d(A,B) = 1 - \text{OC}(A,B)$, converts this similarity into a proper metric. We construct a threshold graph where basins are connected by edges whenever their overlap distance falls below the specified threshold. Connected components of this graph define clusters of similar basins. Within each cluster, basins likely represent the same or closely related features in the underlying function landscape.

The function internally calls summary.basins_of_attraction to obtain consistent basin labels. These labels follow the convention that minima are labeled m1, m2, ... in order of increasing function value (so m1 is the global minimum), while maxima are labeled M1, M2, ... in order of decreasing function value (so M1 is the global maximum). This labeling scheme ensures that clustering results align with other basin analyses.

The function operates exclusively on basins of a single extremum type to maintain the interpretability of clusters. Mixing ascending and descending basins would conflate fundamentally different topological features.

The overlap graph returned by the function can be visualized using standard graph visualization tools to examine the structure of basin relationships.

Examples

if (FALSE) { # \dontrun{
# Compute basins of attraction for a function on a graph
basins <- compute.basins.of.attraction(adj.list, adj.list, weight.list, y)

# Generate basin summary with consistent labels
basin.df <- summary(basins, adj.list, edgelen.list)
print(basin.df)

# Cluster local maxima using the same labels
max.clusters <- cluster.local.extrema(basins,
                                      adj.list,
                                      edgelen.list,
                                      extrema.type = "max",
                                      overlap.threshold = 0.15)

# Report clustering results
cat("Found", max.clusters$n.clusters, "clusters among",
    nrow(max.clusters$basin.summary), "maxima\n")

# Examine cluster assignments
print(max.clusters$cluster.assignments)

# View clusters and their members
print(max.clusters$clusters)

# Identify multi-basin clusters
multi.basin.clusters <- Filter(function(x) length(x) > 1,
                               max.clusters$clusters)
if (length(multi.basin.clusters) > 0) {
  cat("\nClusters with multiple basins:\n")
  for (cluster.id in names(multi.basin.clusters)) {
    cat("Cluster", cluster.id, ":",
        paste(multi.basin.clusters[[cluster.id]], collapse = ", "), "\n")
  }
}

# Inspect basin characteristics for clustered maxima
clustered.labels <- unlist(multi.basin.clusters)
clustered.basins <- max.clusters$basin.summary[
  max.clusters$basin.summary$label %in% clustered.labels,
]
print(clustered.basins[, c("label", "vertex", "value", "basin.size")])

# Check overlap distances
print(round(max.clusters$overlap.distances, 3))

# Visualize the overlap graph
library(igraph)
n.basins <- length(max.clusters$overlap.graph$adj_list)
edge.list <- matrix(nrow = 0, ncol = 2)
edge.weights <- numeric(0)
for (i in seq_len(n.basins)) {
  neighbors <- max.clusters$overlap.graph$adj_list[[i]]
  if (length(neighbors) > 0) {
    for (j in seq_along(neighbors)) {
      neighbor <- neighbors[j]
      if (i < neighbor) {  # Avoid duplicate edges
        edge.list <- rbind(edge.list, c(i, neighbor))
        edge.weights <- c(edge.weights,
                         max.clusters$overlap.graph$weight_list[[i]][j])
      }
    }
  }
}
if (nrow(edge.list) > 0) {
  g <- graph_from_edgelist(edge.list, directed = FALSE)
  V(g)$name <- names(max.clusters$overlap.graph$adj_list)
  E(g)$weight <- edge.weights
  plot(g, vertex.label = V(g)$name,
       edge.label = round(E(g)$weight, 2),
       main = "Basin Overlap Graph")
}

# Similarly cluster local minima
min.clusters <- cluster.local.extrema(basins,
                                      adj.list,
                                      edgelen.list,
                                      extrema.type = "min",
                                      overlap.threshold = 0.15)
print(min.clusters$clusters)
} # }

Usage

Arguments

Value

Details

See also

Examples