How does the value of K determine number of local optima in NK model?

Question

BACKGROUND

The NK model of fitness landscape considers N states which can interact with K other states. For example N is the total number of genes in a haploid genome and K is the number of other genes that each gene may interact with.

In this article Kaufman says:

The fully connected NK model yields a completely random fitness landscape. For K = N - 1, the fitness contribution of each site depends on all of the other sites in the sequence and therefore altering any site from one to the other value, 0-1, alters the fitness contribution of each site to a new random value. Thus the fitness of any 1-mutant neighboring sequence is completely random with respect to the initial sequence. The landscape is fully random. As was shown in Kauffman & Levin (1987), Weinberger (1988), and Macken & Pereison (1989), such random landscapes have very many local optima, on average, 2^N/(N +1).

I did not read the references mentioned in the text but I read the related section in Kaufman's book: Origins of Order: Self-Organization and Selection in Evolution.

In the book he says that the fitness of a genotype can be ordered and given ranks; the probability that a genotype is fitter than its neighbours (local optima) is same as its probability of ranking higher than its N neighbours. So this probability:

$$P_m=\frac{1}{N+1}$$

and if each gene can have only two states lets say on or off then the expected number of optima with respect to one-mutants (i.e. the difference between a gene and its neighbour is just one mutation) would be:

$$M_1=\frac{2^N}{N+1}$$

What I don't understand is the role of K in this expression. This reason should be valid for any number of K (See the quote above). Even in the book this explanation is given in the case where K is maximum i.e. N-1. I can understand that K can affect the ruggedness of the landscape but can anyone explain how K affects the number of optima? (or are they just two separate statements written together, which is confusing me)

Answer 1

Let's take the opposite extreme, $K=0$, so that each site has an independent effect on fitness. Without loss of generality, we can say that at each locus $n$, the $1$ allele confers an advantage $s_n$ over the $0$ allele. Then there is just one local optimum, the global optimum, at $\vec{1}$, so $M_1=1$ (and $P_m=2^{-N}$).

The key difference is that in the $K=0$ case each fitness comparison of a focal genotype with a neighbor is independent of the rest: the fact that mutating the first gene decreases fitness, for instance, doesn't make it any more likely that mutating the second gene will decrease fitness. For any $K$, it is necessarily true that the focal genotype has a probability $1/(N+1)$ of being fitter than all of a set of $N$ other randomly chosen genotypes, but we're interested in comparing it to its neighbors, which are not a random selection, and are only equivalent to a random selection when $K=N-1$.