Local properties of Kauffman’s<i>N</i>-<i>k</i>model: A tunably rugged energy landscape

Abstract

The N-k model is a dilute, k-ary spin glass in which the state of each of the N sites is affected by that site and k of its neighbors. As a function of k for large k, we explicitly compute the number of local minima of the Hamiltonian, the distribution of locally minimal energies and the first two moments of that distribution, and a number of statistical properties of ``downhill'' walks from random starting positions to local optima on these landscapes, including estimates for their length. We suggest some implications of these results for spin-glass physics and for approximating other landscapes that cannot be modeled using more conventional, quadratically coupled spin glasses.