Fast synchronization with directed small-world networks

In different articles it is shown that multi-agent synchronization can be faster under certain undirected network topologies. In this paper, we present an algorithm which generates strongly connected directed small-world networks. The main goal is a further enhancement of convergence speed. The generated graphs solve the consensus problem significantly faster than regular networks with the same number of links. However, the produced structures are generally not balanced, i.e. the out-degree remains constant, while the in-degree can vary. In this case an averaging consensus will not be reached. To solve this inconvenience, we propose a heuristic sorting algorithm to balance the generated directed small-world networks. In addition, balancing has yet another positive influence on the convergence speed. The result is a balanced, directed small-world network which solves the consensus problem faster than undirected small-world networks.