  Complexity of dynamical networks can arise not only from the complexity of
the topological structure but also from the time evolution of the topology. In
this paper, we study the synchronous motion of coupled maps in time-varying
complex networks both analytically and numerically. The temporal variation is
rather general and formalized as being driven by a metric dynamical system.
Four network models are discussed in detail in which the interconnections
between vertices vary through time randomly. These models are 1) i.i.d.
sequences of random graphs with fixed wiring probability, 2) groups of graphs
with random switches between the individual graphs, 3) graphs with temporary
random failures of nodes, and 4) the meet-for-dinner model where the vertices
are randomly grouped. We show that the temporal variation and randomness of the
connection topology can enhance synchronizability in many cases; however, there
are also instances where they reduce synchronizability. In analytical terms,
the Hajnal diameter of the coupling matrix sequence is presented as a measure
for the synchronizability of the graph topology. In topological terms, the
decisive criterion for synchronization of coupled chaotic maps is that the
union of the time-varying graphs contains a spanning tree.
