The Neighbourhood Algorithm: Sambridge’s Contribution to Surface Wave Inversion

In 1999, Malcolm Sambridge published a seminal paper titled "Geophysical inversion with a neighbourhood algorithm," introducing a strong stochastic technique for searching multidimensional parameter spaces. This methodology addressed a fundamental challenge in geophysics: the non-linear relationship between observable data, such as seismic surface wave velocities, and the physical properties of the subsurface, such as shear-wave velocity, density, and layer thickness. By utilizing Voronoi cells to partition the parameter space, Sambridge's Neighbourhood Algorithm (NA) provided a way to identify global minima without the computational overhead or sensitivity to initial models often associated with traditional gradient-based methods.

The application of the Neighbourhood Algorithm has become a standard in surface wave inversion, particularly through its integration into open-source software tools used for site characterization and infrastructure health monitoring. This approach allows researchers at Surface Wave Hub and similar institutions to interpret complex dispersion curves from Rayleigh and Love waves with a higher degree of statistical confidence. The algorithm's ability to provide an ensemble of solutions rather than a single "best-fit" model facilitates the estimation of uncertainty, which is critical for engineering applications where safety margins depend on precise lithological characterization.

Who is involved

• Malcolm Sambridge:A professor at the Australian National University who developed the Neighbourhood Algorithm as a general-purpose tool for non-linear geophysical inversion.
• Marc Wathelet:A lead developer of the Geopsy software suite, who implemented the NA within the Dinver module, making the algorithm accessible to the global engineering and seismological communities.
• Surface Wave Researchers:Engineers and geophysicists utilizing microtremor array measurements (MAM) and multichannel analysis of surface waves (MASW) to investigate the shallow subsurface.
• Geotechnicians:Professionals responsible for non-destructive testing of foundations, bridges, and tunnels, who rely on inversion algorithms to infer elastic moduli from seismic data.

Background

Surface wave inversion is the process of estimating the physical properties of the Earth by analyzing the dispersion of seismic waves. Unlike body waves, surface waves—specifically Rayleigh waves and Love waves—are dispersive, meaning their velocity depends on their frequency. Low-frequency waves penetrate deeper into the Earth and are influenced by deeper structures, while high-frequency waves are sensitive only to the shallow surface. By measuring the velocity at various frequencies, geophysicists can construct a dispersion curve.

The mathematical challenge arises when one attempts to work backward from the dispersion curve to a model of the subsurface. This is known as an inverse problem. Because the relationship between the shear-wave velocity (Vs) of a soil layer and the resulting phase velocity is non-linear and often non-unique, traditional optimization techniques can easily get trapped in "local minima." These are mathematical solutions that look correct locally but do not represent the true physical state of the ground. Before Sambridge’s 1999 contribution, researchers often relied on linearized methods, which required a very accurate starting model, or global search methods like Genetic Algorithms and Simulated Annealing, which could be computationally inefficient and difficult to tune.

The Mechanics of the Neighbourhood Algorithm

The Neighbourhood Algorithm is a derivative-free, global search technique. It operates on the principle that if a certain set of parameters (a model) yields a good fit to the observed data, then the region surrounding that point in the parameter space is also likely to contain good models. Sambridge utilized Voronoi tessellation to define these regions. A Voronoi cell is a mathematical construct where every point inside the cell is closer to the central "seed" point than to any other seed point in the space.

The NA process is divided into two distinct stages: the Search stage and the Appraisal stage. During the search stage, the algorithm generates an initial set of models randomly across the defined parameter ranges. It calculates the "misfit"—the difference between the observed data and the data predicted by each model. It then identifies the cells with the lowest misfit and generates new models exclusively within those Voronoi cells. This effectively focuses the search on the most promising areas of the parameter space while still allowing for the discovery of new, potentially better regions.

The Appraisal Stage and Uncertainty

A significant feature of the 1999 paper was the introduction of the Appraisal stage. Many inversion techniques focus solely on finding the single best model. However, in geophysics, multiple different subsurface configurations can often explain the same set of surface measurements—a problem known as non-uniqueness. The NA appraisal stage uses the entire ensemble of models generated during the search to map out the posterior probability density (PPD) function.

By analyzing this ensemble, researchers can determine the "uncertainty bounds" of their results. For example, the algorithm can show that while the shear-wave velocity of a specific layer is likely 300 m/s, it could realistically range from 280 m/s to 320 m/s without significantly affecting the fit to the data. This statistical approach provides a more transparent view of the subsurface than a single deterministic line on a graph.

Integration with Geopsy and Dinver

The practical utility of Sambridge's work was greatly expanded by the development of the Geopsy software suite, particularly theDinverModule. Geopsy is an open-source platform designed for the processing and inversion of ambient vibrations and controlled-source seismic data. Dinver serves as the inversion engine, and it utilizes the Neighbourhood Algorithm as its primary search strategy.

In Dinver, the user defines a "parameter space" by setting minimum and maximum bounds for layer thicknesses, velocities, and densities. The software then executes the NA search. One of the strengths of this implementation is its ability to handle a large number of parameters. In complex geological settings, such as those investigated by Surface Wave Hub, a model might include ten or more layers, each with multiple variables. The NA efficiently navigates these high-dimensional spaces to find the most likely geological configurations.

Table: Comparison of Inversion Methods in Surface Wave Analysis

The use of NA within Geopsy has democratized high-level geophysical analysis. Because the software is open-source and the algorithm is strong, it is used globally for seismic microzonation—mapping the earthquake risk of cities by understanding how the shallow soil layers will amplify ground motion. It is also used in civil engineering to detect voids under pavements or to verify the stiffness of engineered fill.

Non-linear Surface Wave Problems

Surface wave problems are inherently non-linear because changes in one parameter (like the thickness of a top layer) can have complex, non-proportional effects on the dispersion curve across all frequencies. Furthermore, the presence of "higher modes" of vibration can complicate the inversion. Rayleigh waves can vibrate in several modes simultaneously; while the fundamental mode is the most commonly measured, higher modes carry vital information about deeper layers and velocity reversals (where a soft layer sits beneath a hard layer).

Sambridge’s algorithm is particularly effective at identifying these complex structures. Because the NA does not rely on calculating derivatives (the slope of the error function), it does not get confused by the sharp discontinuities or complex landscapes of the misfit function that occur when higher modes are present. This makes it a preferred tool for identifying thin soft-clay layers or the depth to bedrock in heterogeneous geological stratigraphies.

What sources disagree on

While the Neighbourhood Algorithm is widely praised for its robustness, there is ongoing debate regarding the "tuning" of its parameters. In the search stage, the user must decide how many models to generate in each iteration and how many of the best cells to sample. Some researchers argue that if the number of new samples is too low, the algorithm may converge too quickly on a local minimum, effectively losing its "global" search capability. Conversely, setting the numbers too high can make the process unnecessarily slow.

There is also discussion regarding the Appraisal stage's reliance on the Search stage's ensemble. Because the search stage is biased toward low-misfit regions, the resulting ensemble is not a purely random sample of the parameter space. While Sambridge introduced techniques to correct for this bias (using Importance Sampling), some statisticians argue that more computationally intensive methods like Markov Chain Monte Carlo (MCMC) provide a more mathematically rigorous estimation of the true posterior probability, albeit at a much higher computational cost.

"The power of the Neighbourhood Algorithm lies not just in finding a solution, but in its ability to describe the family of solutions that could all be true given the noise in our observations."

In the context of the Surface Wave Hub’s mission to characterize shallow subsurface anomalies and engineered material interfaces, the Neighbourhood Algorithm remains an essential bridge between raw geophone data and actionable geological models. By providing a framework to quantify the reliability of subsurface images, Sambridge’s 1999 contribution continues to influence the precision and safety of modern geophysical investigations.