Efficient rewirings for enhancing synchronizability of dynamical networks

Abstract

In this paper, we present an algorithm for optimizing synchronizability of complex dynamical networks. Starting with an undirected and unweighted network, we end up with an undirected and unweighted network with the same number of nodes and edges having enhanced synchronizability. To this end, based on some network properties, rewirings, i.e., eliminating an edge and creating a new edge elsewhere, are performed iteratively avoiding always self-loops and multiple edges between the same nodes. We show that the method is able to enhance the synchronizability of networks of any size and topological properties in a small number of steps that scales with the network size. For numerical simulations, an optimization algorithm based on simulated annealing is used. Also, the evolution of different topological properties of the network such as distribution of node degree, node and edge betweenness centrality is tracked with the iteration steps. We use networks such as scale-free, Strogatz-Watts and random to start with and we show that regardless of the initial network, the final optimized network becomes homogeneous. In other words, in the network with high synchronizability, parameters, such as, degree, shortest distance, node, and edge betweenness centralities are almost homogeneously distributed. Also, parameters, such as, maximum node and edge betweenness centralities are small for the rewired network. Although we take the eigenratio of the Laplacian as the target function for optimization, we show that it is also possible to choose other appropriate target functions exhibiting almost the same performance. Furthermore, we show that even if the network is optimized taking into account another interpretation of synchronizability, i.e., synchronization cost, the optimal network has the same synchronization properties. Indeed, in networks with optimized synchronizability, different interpretations of synchronizability coincide. The optimized networks are Ramanujan graphs, and thus, this rewiring algorithm could be used to produce Ramanujan graphs of any size and average degree.