  We propose a network characterization of combinatorial fitness landscapes by
adapting the notion of inherent networks proposed for energy surfaces (Doye,
2002). We use the well-known family of $NK$ landscapes as an example. In our
case the inherent network is the graph where the vertices are all the local
maxima and edges mean basin adjacency between two maxima. We exhaustively
extract such networks on representative small NK landscape instances, and show
that they are 'small-worlds'. However, the maxima graphs are not random, since
their clustering coefficients are much larger than those of corresponding
random graphs. Furthermore, the degree distributions are close to exponential
instead of Poissonian. We also describe the nature of the basins of attraction
and their relationship with the local maxima network.
