  An automata network (AN) is a finite graph where each node holds a state from
a finite alphabet and is equipped with a local map defining the evolution of
the state of the node depending on its neighbors. They are studied both from
the dynamical and the computational complexity point of view. Inspired from
well-established notions in the context of cellular automata, we develop a
theory of intrinsic simulations and universality for families of automata
networks. We establish many consequences of intrinsic universality in terms of
complexity of orbits (periods of attractors, transients, etc) as well as
hardness of the standard well-studied decision problems for automata networks
(short/long term prediction, reachability, etc). In the way, we prove
orthogonality results for these problems: the hardness of a single one does not
imply hardness of the others, while intrinsic universality implies hardness of
all of them. As a complement, we develop a proof technique to establish
intrinsic simulation and universality results which is suitable to deal with
families of symmetric networks were connections are non-oriented. It is based
on an operation of glueing of networks, which allows to produce complex orbits
in large networks from compatible pseudo-orbits in small networks. As an
illustration, we give a short proof that the family of networks were each node
obeys the rule of the 'game of life' cellular automaton is strongly universal.
This formalism and proof technique is also applied in a companion paper devoted
to studying the effect of update schedules on intrinsic universality for
concrete symmetric families of automata networks.
