Complex-network analysis of combinatorial spaces: The NK landscape case

Abstract

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces. We use the well-known family of NK landscapes as an example. In our case the inherent network is the graph whose vertices represent the local maxima in the landscape, and the edges account for the transition probabilities between their corresponding basins of attraction. We exhaustively extracted such networks on representative NK landscape instances, and performed a statistical characterization of their properties. We found that most of these network properties are related to the search difficulty on the underlying NK landscapes with varying values of K.

arXiv admin note: substantial text overlap with arXiv:0810.3492, arXiv:0810.3484

References in corpus (6)

• The structure and function of complex networks
• Characterization and Modeling of weighted networks
• The network topology of a potential energy landscape: A static scale-free network
• A Study of NK Landscapes' Basins and Local Optima Networks
• Small-world networks and the conformation space of a lattice polymer chain
• Characterizing the network topology of the energy landscapes of atomic clusters

Cited by in corpus (10)

• Local Optima Networks: A New Model of Combinatorial Fitness Landscapes
• Universality classes of interaction structures for NK fitness landscapes
• Local optima networks and the performance of iterated local search
• Local Optima Networks, Landscape Autocorrelation and Heuristic Search Performance
• A Local Optima Network View of Real Function Fitness Landscapes
• Clustering of Local Optima in Combinatorial Fitness Landscapes
• Complexity and accessibility of random landscapes
• Communities of Minima in Local Optima Networks of Combinatorial Spaces
• First-improvement vs. Best-improvement Local Optima Networks of NK Landscapes
• Local Optima Networks of NK Landscapes with Neutrality