The paper proposes a method to generate communication structures for networked controllers that have the small-world property. This property, which is known from complex networks, means that in a large ring of agents, a small number of shortcut links substantially improve the performance of the overall system. To investigate the consequences of this property for control systems, the paper considers multi-agent systems with leader-follower structure where additional communication links among the local control stations are selected by the agents in a random way. The performance of the overall system is evaluated in terms of the delay with which the agents react on leader commands. The main result provides a relation between the probability p of the existence of additional edges in the communication graph and the performance of the overall system. It is proved that for any probability p > 0 there exists an upper bound of the performance index and that this bound is independent of the number of agents. Furthermore, a quantitative analysis shows that it is sufficient to connect the agents with a very low probability p approximate to 10% in order to get a satisfactory performance. These results are illustrated by a robot formation example.