On The Eigenvalue Distribution Of Adjacency Matrices For Connected Planar Graphs
PDF

Keywords

adjacency matrix
connected graph
eigenvalue distribution
planar graph
serial structure

How to Cite

Griffith, D. A. (2015). On The Eigenvalue Distribution Of Adjacency Matrices For Connected Planar Graphs. Quaestiones Geographicae, 34(4), 39–60. https://doi.org/10.1515/quageo-2015-0035

Abstract

This paper describes the previously unknown statistical distribution of adjacency matrix spectra for planar graphs, also known as spatial weights matrices, in terms of the following three readily available eigenvalue properties: extremes, rank orderings, and sums of powers. This distribution is governed by at most six parameters that, once known, allow accurate approximations of eigenvalues to be computed without resorting to numerical matrix methods applied on a case-by-case basis. Parameter estimates for illustrative real-world examples are obtained using nonlinear least squares regression techniques. Three conjectures are proposed, and graphical and trend results are reported for a diverse set of planar graph-based matrices.

https://doi.org/10.1515/quageo-2015-0035
PDF

References

Adler M., van Moerbeke P., 2001. Hermitian, symmetric and symplectic random ensembles: PDEs for the distribution of the spectrum. Annals of Mathematics 153: 149–189.

Barry R., Pace R., 1999. Monte Carlo estimates of the log determinant of large sparse matrices. Linear Algebra and Its Applications 289: 41–54.

Box G., Jenkins G., 1976. Time series analysis: Forecasting, and control. Holden Day, San Francisco.

Brouwer A., Haemers W., 2012. Spectra of graphs. Springer, New York.

Cao D., Yuan H., 1993. Graphs characterized by the second eigenvalue. Journal of Graph Theory 17: 25–331.

Cao D., Yuan H., 1995. The distribution of eigenvalues of graphs. Linear Algebra and its Applications 216: 211–224.

Chung F., 1997. Spectral graph theory. American Mathematical Society, Providence, RI.

Chung F., Lu L., Vu V., 2003. Spectra of random graphs with given expected degrees. Proceedings of the National Academy of Sciences 100: 6313–6318.

Cressie N., 1993. Statistics for spatial data. Wiley, New York.

Faloutsos M., Faloutsos P., Faloutsos C., 1999. On power-law relationships of the internet topology. ACM SIGCOM Computer Communication Review 29: 251–262.

Farrell P., Ehsanes Saleh A., Zhang Z., 2011. Methods of moments estimation in finite mixtures. Sankhyā: The Indian Journal of Statistics 73-A, Part 2: 218–230.

Fefferman C., Phong D., 1980. On the asymptotic eigenvalue distribution of a pseudo-differential operation. Proceedings of the National Academy of Sciences 77: 5622–5625.

Golub G., van der Vorst H., 2000. Numerical progress in eigenvalue computation in the 20th century. J. of Computational and Applied Mathematics 123: 35–65.

Griffith D., 2000. Eigenfunction properties and approximations of selected incidence matrices employed in spatial analyses. Linear Algebra and its Applications 321: 95–112.

Griffith D., 2003. Spatial autocorrelation and spatial filtering: Gaining understanding through theory and scientific visualization. Springer, New York.

Griffith D., 2004. Extreme eigenfunctions of adjacency matrices for planar graphs employed in spatial analyses. Linear Algebra and Its Applications 388: 201–219.

Griffith D., Luhanga U., 2011. Approximating the inertia of the adjacency matrix of a connected planar graph that is the dual of a geographic surface partitioning. Geographical Analysis 43: 383–402.

Hams A., de Raedt H., 2000. Fast algorithm for finding the eigenvalue distribution of very large matrices. Physical review, E: Statistical physics, plasmas, fluids, and related interdisciplinary topics 62 (#3): 4365–4377.

Henson J., Reise S., Kim K., 2007. Detecting mixtures from structural model differences using latent variable mixture modeling: A comparison of relative model fit statistics. Structural Equation Modeling 14 (2): 202–226.

Huffer F., Wu H., 1998. Markov chain Monte Carlo for autologistic regression models with application to the distribution of plant species. Biometrics 54: 509–524.

Hyndman J., Kostenko A., 2007. Minimum sample size requirements for seasonal forecasting models. Foresight 6: 12–15.

Khorunzhy O., Shcherbina M., Vengerovsky V., 2004. Eigenvalue distribution of large weighted random graphs. Journal of Mathematical Physics 45 (#4): 1648–1672.

Liu B., Bo Z., 2000. On the third largest eigenvalue of a graph. Linear Algebra and its Applications 317: 193–200.

Martin R., Griffith D., 1998. Fast methods for fitting one-parameter spatial models. Department of Geography, Syracuse University Syracuse, NY (unpublished paper).

Sylvester J., 1852. A demonstration of the theorem that every homogeneous quadratic polynomial is reducible by real orthogonal substitutions to the form of a sum of positive and negative squares. Philosophical Magazine Series 4, 4 (23): 138–142.

Tse R., 1997. An application of the ARIMA model to real estate prices in Hong Kong. Journal of Property Finance 8: 152–163.

Yong X., 1999. On the distribution of eigenvalues of a simple undirected graph. Linear Algebra and its Applications 295: 73–80.