Hierarchical, Regular Small-World Networks

Abstract

Two new classes of networks are introduced that resemble small-world properties. These networks are recursively constructed but retain a fixed, regular degree. They consist of a one-dimensional lattice backbone overlayed by a hierarchical sequence of long-distance links. Both types of networks, one 3-regular and the other 4-regular, lead to distinct behaviors, as revealed by renormalization group studies. The 3-regular networks are planar, have a diameter growing as \sqrt{N} with the system size N, and lead to super-diffusion with an exact, anomalous exponent d_w=1.3057581..., but possesses only a trivial fixed point T_c=0 for the Ising ferromagnet. In turn, the 4-regular networks are non-planar, have a diameter growing as ~2^[\sqrt(\log_2 N^2)], exhibit "ballistic" diffusion (d_w=1), and a non-trivial ferromagnetic transition, T_c>0. It suggest that the 3-regular networks are still quite "geometric", while the 4-regular networks qualify as true small-world networks with mean-field properties. As an example of an application we discuss synchronization of processors on these networks.

9 pages, final version for JPA FastTrack, find related articles at http://www.physics.emory.edu/faculty/boettcher

References in corpus (7)

• Random graphs with arbitrary degree distributions and their applications
• Synchronization in small-world systems
• Renormalization group analysis of the small-world network model
• Deterministic Scale-Free Networks
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations
• Anomalous Diffusion on the Hanoi Networks

Cited by in corpus (24)

• Ordinary Percolation with Discontinuous Transitions
• Small-World Bonds and Patchy Percolation on the Hanoi Network
• Random walks in modular scale-free networks with multiple traps
• Anomalous Diffusion on the Hanoi Networks
• Fixed Point Properties of the Ising Ferromagnet on the Hanoi Networks
• Scaling of Clusters near Discontinuous Percolation Transitions in Hyperbolic Networks
• Quantum Transport through Hierarchical Structures
• Geometry and Dynamics for Hierarchical Regular Networks
• Superdiffusion in a class of networks with marginal long-range connections
• Scaling behavior of the contact process in networks with long-range connections
• Structural and spectral properties of a family of deterministic recursive trees: Rigorous solutions
• From explosive to infinite-order transitions on a hyperbolic network
• The rigorous solution for the average distance of a Sierpinski network
• Totally Asymmetric Exclusion Process with Hierarchical Long-Range Connections
• The Griffiths Phase on Hierarchical Modular Networks with Small-world Edges
• Renormalization of the Unitary Evolution Equation for Coined Quantum Walks
• Evaluation of Spectral Zeta-Functions with the Renormalization Group
• Optimal Vertex Cover for the Small-World Hanoi Networks
• Jamming in Hierarchical Networks
• Critical Percolation Phase and Thermal BKT Transition in a Scale-Free Network with Short-Range and Long-Range Random Bonds
• A Quality and Cost Approach for Comparison of Small-World Networks
• Structure Properties of Koch Networks Based on Networks Dynamical Systems
• Renormalization Group Solution of the Chutes&Ladder Model
• Modified Hanoi Towers Groups and Limit Spaces