Structural properties of networked systems with random communication links

The paper deals with the problem of choosing the communication structure of networked systems and shows that a small percentage of all possible communication links suffices to get short paths from the leader to all followers. It considers agents that are connected in a single row and that choose randomly additional communication links within the region of the next M neighbours. Without additional communication links, the path length increases linearly along the row of the agents, which leads to an unsatisfactory performance of agents at the end of the row. The paper derives an analytical expression for the expected path length in the network with the additional links and shows that a small number of additional links considerably shortens the path length from the leader to all followers.