  It is well known that many complex systems, both in technology and nature,
exhibit hierarchical modularity: smaller modules, each of them providing a
certain function, are used within larger modules that perform more complex
functions. What is not well understood however is how this hierarchical
structure (which is fundamentally a network property) emerges, and how it
evolves over time. We propose a modeling framework, referred to as Evo-Lexis,
that provides insight to some fundamental questions about evolving hierarchical
systems. Evo-Lexis models the most elementary modules of the system as symbols
("sources") and the modules at the highest level of the hierarchy as sequences
of those symbols ("targets"). Evo-Lexis computes the optimized adjustment of a
given hierarchy when the set of targets changes over time by additions and
removals (a process referred to as "incremental design"). In this paper we use
computation modeling to show that:
  - Low-cost and deep hierarchies emerge when the population of target
sequences evolves through tinkering and mutation. - Strong selection on the
cost of new candidate targets results in reuse of more complex (longer) nodes
in an optimized hierarchy. - The bias towards reuse of complex nodes results in
an "hourglass architecture" (i.e., few intermediate nodes that cover almost all
source-target paths). - With such bias, the core nodes are conserved for
relatively long time periods although still being vulnerable to major
transitions and punctuated equilibria. - Finally, we analyze the differences in
terms of cost and structure between incrementally designed hierarchies and the
corresponding "clean-slate" hierarchies which result when the system is
designed from scratch after a change.
