After having recalled the basic properties of the nontrivial collective dynamics exhibited by lattices of maps with local coupling and synchronous updating, we present the behavior of the same models in which all the connections are random. The mean-field, synchronized limit is shown to be reached only for large enough connectivities and sufficiently strong local chaos. Intermediate models, in which only a few of the connections of each site are taken at random, are then considered. Preliminary results indicate that the nontrivial collective behaviors shown by the regularly connected models may be robust to a small proportion of nonlocal, random connections.