Complex-network analysis of combinatorial spaces: Thelandscape case
- 24 December 2008
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 78 (6) , 066114
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 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 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 landscapes with varying values of .
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Complex network analysis of free-energy landscapesProceedings of the National Academy of Sciences, 2007
- Characterizing the network topology of the energy landscapes of atomic clustersThe Journal of Chemical Physics, 2005
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Network Topology of a Potential Energy Landscape: A Static Scale-Free NetworkPhysical Review Letters, 2002
- Small-world networks and the conformation space of a short lattice polymer chainEurophysics Letters, 2001
- Efficiency of Local Search with Multiple Local OptimaSIAM Journal on Discrete Mathematics, 2001
- Local properties of Kauffman’sN-kmodel: A tunably rugged energy landscapePhysical Review A, 1991
- The simplest spin glassNuclear Physics B, 1984
- Packing Structures and Transitions in Liquids and SolidsScience, 1984
- Random-energy model: An exactly solvable model of disordered systemsPhysical Review B, 1981