Hierarchical regular small-world networks

Creative Commons License

Boettcher S., Goncalves B., Guclu H.

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, vol.41, no.25, 2008 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Volume: 41 Issue: 25
  • Publication Date: 2008
  • Doi Number: 10.1088/1751-8113/41/25/252001
  • Journal Indexes: Science Citation Index Expanded, Scopus


Two new networks are introduced that resemble small-world properties. These networks are recursively constructed but retain a fixed, regular degree. They possess a unique one-dimensional lattice backbone overlaid by a hierarchical sequence of long-distance links, mixing real-space and small-world features. Both networks, one 3-regular and the other 4-regular, lead to distinct behaviors, as revealed by renormalization group studies. The 3-regular network is planar, has a diameter growing as root N with system size N, and leads to super-diffusion with an exact, anomalous exponent d(w) = 1.306..., but possesses only a trivial fixed point T(c) = 0 for the Ising ferromagnet. In turn, the 4-regular network is non-planar, has a diameter growing as similar to 2 root log(2)N(2), exhibits 'ballistic' diffusion (d(w) = 1), and a non-trivial ferromagnetic transition, T(c) > 0. It suggests that the 3-regular network is still quite 'geometric', while the 4-regular network qualifies as a true small world with mean-field properties. As an engineering application we discuss synchronization of processors on these networks.