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

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

2006-05-23

arxiv.org/abs/cond-mat/0605565v2

J. of Stat. Mech. P08007 (2006).

Physics

Condensed Matter

Other Condensed Matter

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

Scientific paper

10.1088/1742-5468/2006/08/P08007

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.

Affiliated with

Also associated with

No associations

Rating

Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-181731