A small-world network where all nodes have the same connectivity, with application to the dynamics of boolean interacting automata

In this paper a new algorithm (called ENL) is introduced, which generates a small-world network starting from a regular lattice, by randomly rewiring some connections. The approach is similar to the well-known Watts-Strogatz model, but the present method is different as it leaves the number of connections k of each node unchanged, while the WS algorithm gives rise to a Poisson distribution of connectivities. The motivation for the ENL algorithm stems from the interest in studying the dynamics of interacting oscillators or automata (associated to the nodes of the network): indeed, leaving k unaltered allows one to study how the dynamics of these networks is affected by rewiring only (which gives rise to small-world properties) disentangling its effects from those related to the modification of the connectivity of some nodes. The new algorithm is compared with that of Watts and Strogatz, by studying the topological properties of the network as a function of the number of rewirings. The effects on the dynamics are tested in the case of the majority rule, and it is shown that key dynamical properties (i.e. number of attractors, size of basins attraction, transient duration) are modified by rewiring. The quantitative differences between the dynamics on a ENL network and a WS one are discussed in detail. A comparison with scale-free networks of the Barabasi-Albert type and with completely random networks is also given.