Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that

We report on some recent developments in the search for optimal network topologies. First we review some basic concepts on spectral graph theory, including adjacency and Laplacian matrices, paying special attention to the topological implications of having large spectral gaps. We also introduce related concepts such as 'expanders', Ramanujan, and Cage graphs. Afterwards, we discuss two different dynamical features of Networks, synchronizability and flow of random walkers, so that they are optimized if the corresponding Laplacian matrix has a large spectral gap. From this, we show, by developing a numerical optimization algorithm, that maximum synchronizability and fast random walk spreading are obtained for a particular type of extremely homogeneous regular networks, with long loops and poor modular structure, that we call entangled networks. These turn out to be related to Ramanujan and Cage graphs. We argue also that these graphs are very good finite-size approximations to Bethe lattices, and provide optimal or almost optimal solutions to many other problems, for instance searchability in the presence of congestion or performance of neural networks. Finally, we study how these results are modified when studying dynamical processes controlled by a normalized ( weighted and directed) dynamics; much more heterogeneous graphs are optimal in this case. Finally, a critical discussion of the limitations and possible extensions of this work is presented.