Complex Systems

A Small-world Network Where All Nodes Have the Same Connectivity, with Application to the Dynamics of Boolean Interacting Automata Download PDF

Roberto Serra
Corresponding author, electronic mail address:
Department of Statistics,
Ca'Foscari University,
Fondamenta S. Giobbe 873, Cannaregio, Venice, Italy

Marco Villani

Luca Agostini
Montecatini Environmental Research Center (Edison Group),
v. Ciro Menotti 48,
I-48023 Marina di Ravenna (RA), Italy


This paper introduces the equal number of links (ENL) algorithm to generate small-world networks starting from a regular lattice, by randomly rewiring some connections. The approach is similar to the well-known Watts-Strogatz (WS) 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. Motivation for the ENL algorithm stems from 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 are affected by rewiring only (which gives rise to small-world properties) disentangling its effects from those related to modifying the connectivity of some nodes. The ENL 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 of attraction, transient duration) are modified by rewiring. The quantitative differences between the dynamics of an ENL network and a WS network are discussed in detail. Comparisons with scale-free networks of the Barabasi-Albert type and with completely random networks are also given.