Computes the probability that a vertex represents a local minimum given observed function values and density weights. The score measures what proportion of the neighborhood density mass has function values strictly above the vertex value.
For high-performance loops where arguments are pre-validated, use the
internal .minp_no_check() function which skips argument checking.
Arguments
- i
Integer scalar giving the vertex index for which to compute the score.
- nbrs
Integer vector of neighbor vertex indices. Must be a subset of
1:length(y).- y
Numeric vector of function values at all vertices. Must have the same length as
rho.- rho
Numeric vector of density values at all vertices. Must be non-negative. Default is uniform density (all vertices weighted equally).
Details
The classical notion of local extremum in discrete graphs is binary: a vertex either is or is not a local minimum. This rigidity creates problems when analyzing functions on graphs derived from continuous spaces, where discretization and estimation noise introduce spurious extrema. The minp score generalizes the binary classification to a continuous score in \([0,1]\).
For a vertex \(i\) with neighbors \(N(i)\), where each vertex \(j\) carries density weight \(\rho(j) > 0\), the minp score is: $$\text{minp}(i|\hat{y},\rho) = \frac{\sum_{j \in N(i): \hat{y}(i) < \hat{y}(j)} \rho(j)}{\sum_{j \in N(i)} \rho(j)}$$
The density weighting downweights contributions from isolated outlier neighbors that may violate the minimum condition due to sampling sparsity rather than true function behavior.
Interpretation of minp values:
When minp approaches 1, nearly all neighborhood density mass has values strictly above the vertex value, providing strong evidence for a genuine local minimum. When minp approaches 0.5, the neighborhood is evenly divided, suggesting the vertex lies on a plateau or saddle. When minp approaches 0, most neighbors have lower values, indicating the vertex is not a minimum.
Relationship to classical definition:
The classical local minimum requires all neighbors to have strictly higher values, corresponding to minp = 1 with uniform density. The probabilistic version relaxes this requirement, allowing some neighbors to violate the condition if they have low density weight. This accommodates isolated outlier neighbors and vertices near the boundary of extremum regions.
Both maxp and minp are needed for complete Morse-Smale decomposition, which requires identifying all critical points (both maxima and minima) to construct the gradient flow structure connecting them.
Computational complexity:
The function performs a single pass over the neighborhood \(N(i)\), requiring \(O(|N(i)|)\) operations. For k-nearest neighbor graphs, this is \(O(k)\) per vertex.
See also
maxp for local maximum probability
Examples
# Create simple graph with valley
adj_list <- list(c(2), c(1, 3), c(2, 4), c(3, 5), c(4))
y <- c(3, 2, 1, 2, 3)
# Vertex 3 is a clear local minimum
minp(3, adj_list[[3]], y) # Returns 1.0
# Vertex 2 is not a minimum (neighbor 3 is lower)
minp(2, adj_list[[2]], y) # Returns 0.5
# With density weighting to downweight outlier
y_with_outlier <- c(3, 2, 1, 1.5, 3)
rho <- c(1, 1, 1, 0.1, 1)
minp(3, adj_list[[3]], y_with_outlier, rho) # Returns ~0.91