Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that

Abstract

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, and paying special attention to the topological implications of having large spectral gaps. We also introduce related concepts as ``expanders'', Ramanujan, and Cage graphs. Afterwards, we discuss two different dynamical feautures of networks: synchronizability and flow of random walkers and so that they are optimized if the corresponding Laplacian matrix have 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 almost or almost optimal solutions to many other problems as, 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.

17 pages. 11 figures. Small corrections and a new reference. Accepted for pub. in JSTAT

References in corpus (21)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Synchronization in small-world systems
• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• Optimal network topologies for local search with congestion
• Network Synchronization, Diffusion, and the Paradox of Heterogeneity
• Synchronization on small-world networks
• Detecting Network Communities: a new systematic and efficient algorithm
• Entangled networks, synchronization, and optimal network topology
• Enhancing complex-network synchronization
• Factors that predict better synchronizability on complex networks
• Performance of networks of artificial neurons: The role of clustering
• Two-Peak and Three-Peak Optimal Complex Networks
• Clustering and Synchronization of Oscillator Networks
• Effect of congestion costs on shortest paths through complex networks
• Network Structures from Selection Principles
• Weighted networks are more synchronizable: how and why
• Improved spectral algorithm for the detection of network communities
• Phase ordering on small-world networks with nearest-neighbor edges

Cited by in corpus (31)

• Random walks and diffusion on networks
• Complex network analysis of water distribution systems
• Temporal networks: slowing down diffusion by long lasting interactions
• Synchronization of interconnected networks: the role of connector nodes
• Robustness of onion-like correlated networks against targeted attacks
• Frustrated hierarchical synchronization and emergent complexity in the human connectome network
• Dynamical and spectral properties of complex networks
• Collective Relaxation Dynamics of Small-World Networks
• Enhancing the spectral gap of networks by node removal
• Does the brain behave like a (complex) network? I. Dynamics
• Bounding network spectra for network design
• Multiequilibria analysis for a class of collective decision-making networked systems
• Network synchronization: Optimal and Pessimal Scale-Free Topologies
• Localization transition, Lifschitz tails and rare-region effects in network models
• Probability of graphs with large spectral gap by multicanonical Monte Carlo
• Topological dimension tunes activity patterns in hierarchical modular network models
• Networks with many structural scales: a Renormalization Group perspective
• Evolution in the Debian GNU/Linux software network: analogies and differences with gene regulatory networks
• Optimal spatial transportation networks where link-costs are sublinear in link-capacity
• Thermodynamics of network model fitting with spectral entropies
• Topological properties of hierarchical networks
• Preferential Detachment in Broadcast Signaling Networks: Connectivity and Cost Trade-off
• Graph Partitioning Induced Phase Transitions
• Entangled gene regulatory networks with cooperative expression endow robust adaptive responses to unforeseen environmental changes
• Graphs (networks) with golden spectral ratio
• "Clumpiness" Mixing in Complex Networks
• Optimal Networks from Error Correcting Codes
• Symmetry-based coarse-graining of evolved dynamical networks
• Topologically protected synchronization in networks
• Large algebraic connectivity fluctuations in spatial network ensembles imply a predictive advantage from node location information
• Metanetworks of artificially evolved regulatory networks