Formulating the Seismic Association Problem Using Graph Theory, Applications to Estimating an Efficient Solution with Quantum Computers

Abstract:

Locating seismic sources with heterogeneous networks of sensors remains a significant challenge in earthquake sciences, geophysical monitoring efforts, and other fields rooted in seismological observation. Traditional techniques that address the association problem grid the Earth at spatially variable resolutions and implement a complicated set of rules to build events (associate them) from waveform arrivals. Some recent associators have used Bayesian methods or Machine Learning (ML) techniques. These advancements, however, are most effective when faced with similar events with semi-predictable locations, either by the inclusion of prior information (Bayesian) or implicitly through training data set selection (ML). Our work investigates reformulating the association problem using graph theory. We define a series of nodes and edges and compute the maximum ‘cliques’ of arrivals that define hypocenter locations. Estimating the maximum clique of a graph is one of Karp’s (1972) list of NP-complete problems. Solutions using small data sets (with several 10s of nodes) can be estimated using a suite of approximations or exhaustive search algorithms. These techniques quickly become unfeasible for large-scale implementation and will benefit from developing technologies in quantum computing. This work attempts to demonstrate that finding the maximum clique of a graph of arrival nodes and their connecting edges is an effective solution to hypocenter identification. This new framework has applicability to an assortment of geophysical monitoring problems, including improving earthquake hazard estimates and enhancing fossil energy extraction.