Using graph theory in 3D inversion of gravity data to delineate the skeleton of homogeneous subsurface sources

Document Type : Research


1 M.Sc. Student, Department of Earth Physics, Institute of Geophysics, University of Tehran, Tehran, Iran

2 Professor, Department of Earth Physics, Institute of Geophysics, University of Tehran, Tehran, Iran

3 Assistant Professor, Department of Earth Physics, Institute of Geophysics, University of Tehran, Tehran, Iran


In this paper, three-dimensional (3D) inversion of gravity data using graph theory is used. The methodology was initially introduced by Bijani et al. (2015) and, here, we provide more details for the steps and required parameters of the algorithm. An ensemble of simple point masses are used to model a homogenous subsurface body. Then, in the presented inversion methodology, the model parameters are the Cartesian coordinates of point masses and their total mass. Consequently, the algorithm is able to reconstruct the skeleton of the subsurface body and to yield its total mass. Here, the set of point masses is associated to the vertices of a weighted full graph in which the weights are computed by the Euclidean distances separating vertices in pairs. Then, the Kruskal’s algorithm can be used to solve the Minimum Spanning Tree (MST) problem for the graph. A stabilizer, called equidistance function, is obtained using the MST, which computes the statistical variance of the distances among point masses. The function restricts the spatial distribution of points, and suggests a homogeneous distribution for the point masses in the subsurface. Here, a non-linear global objective function for the model parameters comprising data misfit term and equidistance function with balancing provided by a regularization parameter that should be minimized. A genetic algorithm (GA) is used for the minimization of the objective function. GA consists of a random search algorithm based on the mechanism of natural selection and natural genetics. Then, to solve the optimization problem in our algorithm, there is no need to calculate the derivatives of the objective function with respect to model parameters, or any matrix operation. Simulations for two synthetic examples, including a vertical and a dipping dike, demonstrate the efficiency and effectiveness of the implementation of the present algorithm. The skeleton and total mass of the bodies are estimated very accurately. We also show that although the search limits for the model parameters must be used, they are not very limitative. Even with less realistic bounds, acceptable approximations of the body are still obtained. Unlike Bijani et al. (2015) which used the L-curve method for estimating the regularization parameter, here, we present a new strategy to approximate the parameter. We demonstrate that if: 1. the equidistance function converges almost monotonically to zero with increasing numbers of generation; 2. minimum of the objective function at the final iteration becomes small; and 3. the predicted data by the reconstructed model is approximately close to observed data, then, the selected regularization parameter is nearly optimum and the results are reliable. This provides a suitable and inexpensive methodology for estimating the regularization parameter. The method is tested on gravity data from the Mobrun ore body, north east of Noranda, Quebec, Canada. The anomaly is associated with a massive body of base metal sulfide, mainly pyrite, which has displaced volcanic rocks of middle Precambrian age (Grant and West, 1965). With application of the algorithm, a skeleton of the body is obtained which extends about 350 m in the east direction, and shows a maximum extension of 200 m in depth.


Main Subjects

آقاجانی، ح.، مرادزاده، ع. و زنگ، ه.، 1389، برآورد موقعیت افقی و ژرفای بی‏هنجاری‏های گرانی به کمک گرادیان کل بهنجارشده، علوم زمین، 76، 169-176.
Bijani, R., Ponte-Neto, C. F., Carlos, D. U. and Silva Dias, F. J. S., 2015, Three-dimensional gravity inversion using graph theory to delineat the skeleton of homogeneous sources, Geophysics., 80, G53-G66.
Blakely, R. J., 1995, Potential Theory in Gravity and Magnetic Applications, Cambridge University Press, Cambridge.
Boschetti, F., Dentith, M. and List, R., 1995, A staged genetic algorithm for tomographic inversion of seismic refraction data, Exploration Geophysics, 26, 331-335.
Boschetti, F., Dentith, M. and List, R., 1997, Inversion of potential field data by genetic algorithms, Geophysical Prospecting, 45, 461-478.
Bott, M., 1960, The use of rapid digital computing methods for direct gravity interpretation of sedimentary basins, Geophys. J. Int., 3, 63–67.
Boulanger, O. and Chouteau M., 2001, Constraint in 3D gravity inversion, Geophysical Prospecting, 49, 265–280.
Chakravarthi, V. and Sundararajan, N., 2007, 3D gravity inversion of basement relief a depth-dependent density approach, Geophysics, 72, I23-I32.
Deo, N., 1974, Graph theory with applications to engineering and computer science: PHI Learning Pvt. Ltd.
Goldberg, D. E. and Holland, J. H., 1988, Genetic algorithms and machine learning, Machine Learning, 3, 95–99.
Grant, F. S. and West, G. F., 1965, Interpretation Theory in Applied Geophysics, McGraw-Hill.
Kruskal, J. B., Jr., 1956, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7, 48–50.
Last, B. J. and Kubik, K., 1983, Compact gravity inversion, Geophysics, 48, 713–721.
Li, Y. and Oldenburg, D. W., 1998, 3D inversion of gravity data, Geophysics, 63, 109–119.
Martins, C. M., Lima, W. A., Barbosa, V. C. and Silva, J. B., 2011, Total variation regularization for depth-to-basement estimate: Part 1 — Mathematical details and applications, Geophysics, 76, I1–I12.
Montana, D. J., 1994, Strongly typed genetic programming, Evolutionary Computation, 3, 199–230.
Portniaguine, O. and Zhdanov, M. S. 1999, Focusing geophysical inversion images, Geophysics, 64, 874–887.
Vatankhah, S., Ardestani, V. E. and Renaut R. A., 2015, Application of the  principle and unbiased predictive risk estimator for determining the regularization parameter in 3-D focusing gravity inversion, Geophys. J. Int., 200, 265-277.
Vatankhah, S., Renaut, R. A. and Ardestani, V. E., 2017, 3-D Projected L1 inversion of gravity data using truncated unbiased predictive risk estimator for regularization parameter estimation, Geophys. J. Int., 210, 1872-1887.
Zeyen, H. and Pous, J., 1993, 3-D joint inversion of magnetic and gravimetric data with a priori information, Geophys. J. Int., 112, 244–256.