2008/07/12 by Gabriela Ochoa, Marco Tomassini, Sebástien Vérel +2 · 2 citations
Computer Science · Physics and Astronomy · Social Sciences · #Complex Network Analysis Techniques #Evolutionary Game Theory and Cooperation #Opinion Dynamics and Social Influence #cs.NE
paper · pdf · doi:10.1145/1389095.1389204
published as Genetic And Evolutionary Computation Conference, Atlanta : États-Unis d'Amérique (2008) · best paper nomination
openalex publication_date 2008/07/12 · arxiv created 2008/10/20 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.