EFFICIENT ALGORITHMS FOR CONSTRUCTING PROPER HIGHER ORDER SPATIAL LAG OPERATORS*

Publisher Website
Google Scholar
Abstract
This paper extends the work of Blommestein and Koper (1992)–BK–on the construction of higher‐order spatial lag operators without redundant and circular paths. For the case most relevant in spatial econometrics and spatial statistics, i.e., when contiguity between two observations (locations) is defined in a simple binary fashion, some deficiencies of the BK algorithms are outlined, corrected and an improvement suggested. In addition, three new algorithms are introduced and compared in terms of performance for a number of empirical contiguity structures. Particular attention is paid to a graph theoretic perspective on spatial lag operators and to the most efficient data structures for the storage and manipulation of spatial lags. The new forward iterative algorithm which uses a list form rather than a matrix to store the spatial lag information is shown to be several orders of magnitude faster than the BK solution. This allows the computation of proper higher‐order spatial lags “on the fly” for even moderately large data sets such as 3,111 contiguous U. S. counties, which is not practical with the other algorithms.