Nature has inspired many algorithms for solving complex problems. Understanding how and why these natural models work leads not only to new insights about nature, but also to an understanding of deep relationships between familiar algorithms. Here, we show that network properties underlie and define a whole family of nature-inspired algorithms. In particular, the network defined by neighbor hoods within landscapes (real or virtual) underlies the searches and phase transitions mediate between local and global search. Three paradigms drawn from computer science—dual-phase evolution, evolutionary dynamics and generalized local search machines—provide theoretical foundations for understanding how nature-inspired algorithms function. Several algorithms provide useful examples, especially genetic algorithms, ant colony optimization and simulated annealing.