Groupe d’études et de recherche en analyse des décisions

G-2009-61

Design of Highly-Synchronizable and Robust Networks

, et

In this work we develop new methods and algorithms for building networks with high synchronizability of dynamical processes occurring at their nodes. In addition, these networks are highly robust to random failures and intentional attacks against their nodes and links. The construction methods developed here are based on the concept of golden spectral graphs (GSGs). They include several analytical results that allow to building a new GSG from a known one as well as a computer program which is able to find automatically regular bipartite GSGs. GSGs are graphs for which the spectral spread (the difference between the largest and smallest eigenvalues of the adjacency matrix) is equal to the spectral gap (the difference between the two largest eigenvalues of the adjacency matrix) multiplied by the square of the golden ratio. We prove here that GSGs are “small-world”, homogeneous networks with large isoperimetric (expansion) constant and high synchronizability. In particular, the regular bipartite GSGs, reported here by the first time, are Ramanujan graphs for a wide range of degrees. These graphs have the best possible expansion and consequently are the most robust ones against node/links failures or attacks.

, 17 pages