Adaptive walk on complex networks.

We investigate the properties of adaptive walks on an uncorrelated fitness landscape which is established in sequence spaces of complex structure. In particular, we perform numerical simulations of adaptive walks on random graphs and scale-free networks. For the former, we also derive some analytical approximations for the density of local optima of the fitness landscape and the mean length walk. We compare our results with those obtained for regular lattices. We obtain that the density of local optima decreases as 1/z, where z is the mean connectivity, for all networks we have investigated. In random graphs, the mean length walk L reaches the asymptotic value e - 1 for large z, which corresponds to the result for regular networks. Although we could not find an exact estimate, we derive an underestimated value for L. Unlike random graphs, scale-free networks show an upper asymptotic value of L.