Computes the probability that a vertex represents a local maximum given observed function values and density weights. The score measures what proportion of the neighborhood density mass has function values strictly below the vertex value.
For high-performance loops where arguments are pre-validated, use the
internal .maxp_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 maximum. This rigidity creates problems when analyzing functions on graphs derived from continuous spaces, where discretization and estimation noise introduce spurious extrema. The maxp 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 maxp score is: $$\text{maxp}(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 maximum condition due to sampling sparsity rather than true function behavior.
Interpretation of maxp values:
When maxp approaches 1, nearly all neighborhood density mass has values strictly below the vertex value, providing strong evidence for a genuine local maximum. When maxp approaches 0.5, the neighborhood is evenly divided, suggesting the vertex lies on a plateau or ridge. When maxp approaches 0, most neighbors have higher values, indicating the vertex is not a maximum.
Relationship to classical definition:
The classical local maximum requires all neighbors to have strictly lower values, corresponding to maxp = 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.
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
minp for local minimum probability
Examples
# Create simple graph with peak
adj_list <- list(c(2), c(1, 3), c(2, 4), c(3, 5), c(4))
y <- c(1, 2, 3, 2, 1)
# Vertex 3 is a clear local maximum
maxp(3, adj_list[[3]], y) # Returns 1.0
# Vertex 2 is not a maximum (neighbor 3 is higher)
maxp(2, adj_list[[2]], y) # Returns 0.5
# With density weighting to downweight outlier
y_with_outlier <- c(1, 2, 3, 2.5, 1)
rho <- c(1, 1, 1, 0.1, 1)
maxp(3, adj_list[[3]], y_with_outlier, rho) # Returns ~0.91