Entangled Networks, Synchronization, and Optimal Network Topology

A new family of graphs, entangled networks, with optimal properties in many respects, is introduced. By definition, their topology is such that it optimizes synchronizability for many dynamical processes. These networks are shown to have an extremely homogeneous structure: degree, node distance, betweenness, and loop distributions are all very narrow. Also, they are characterized by a very interwoven (entangled) structure with short average distances, large loops, and no well-defined community structure. This family of nets exhibits an excellent performance with respect to other flow properties such as robustness against errors and attacks, minimal first-passage time of random walks, efficient communication, etc. These remarkable features convert entangled networks in a useful concept, optimal or almost optimal in many senses, and with plenty of potential applications in computer science or neuroscience.

Figure 1

Eigenvalue ratio $Q$ as a function of the number of algorithmic iterations. Starting from different initial conditions, with $N=50$, and $⟨k⟩=4$, the algorithm converges to networks, as the depicted one (b), with very similar values of $Q$.

Figure 2

Relation between the ratio $Q$ and (i) node-connectivity standard deviation, (ii) betweenness standard deviation, (iii) average node distance, and (iv) average betweenness. The subscript “norm” stands for normalization with respect to the respective mean-values, centering all the measured quantities around 1.

Figure 3

Cage graphs for $k=3$ and (a) $g=5$ (Petersen) and (b) $g=7$ (McGee). (c) Percolation threshold (main) and average first-passage time (inset) as a function of the eigenratio $Q$, as obtained during the optimization of a network with 500 nodes and $⟨k⟩=3$. The initial network corresponds to a 3-regular graph with $N=500$.