Farey Graphs as Models for Complex Networks

Abstract

Farey sequences of irreducible fractions between 0 and 1 can be related to graph constructions known as Farey graphs. These graphs were first introduced by Matula and Kornerup in 1979 and further studied by Colbourn in 1982 and they have many interesting properties: they are minimally 3-colorable, uniquely Hamiltonian, maximally outerplanar and perfect. In this paper we introduce a simple generation method for a Farey graph family, and we study analytically relevant topological properties: order, size, degree distribution and correlation, clustering, transitivity, diameter and average distance. We show that the graphs are a good model for networks associated with some complex systems.

Definitive version published in Theoretical Computer Science

References in corpus (13)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Assortative mixing in networks
• Evolution of networks
• Specificity and stability in topology of protein networks
• Hierarchical Organization in Complex Networks
• Dynamical and correlation properties of the Internet
• Pseudofractal Scale-free Web
• A Geometric Fractal Growth Model for Scale Free Networks
• A deterministic small-world network created by edge iterations
• Recursive graphs with small-world scale-free properties
• Evolving small-world networks with geographical attachment preference
• A geometric growth model interpolating between regular and small-world networks

Cited by in corpus (13)

• Topological Percolation on Hyperbolic Simplicial Complexes
• Counting spanning trees in a small-world Farey graph
• The number and degree distribution of spanning trees in the Tower of Hanoi graph
• Renormalization group for link percolation on planar hyperbolic manifolds
• Transition-type change between an inverted Berezinskii-Kosterlitz-Thouless transition and an abrupt transition in the bond percolation on a random hierarchical small-world network
• Corona graphs as a model of small-world networks
• Tutte polynomial of a small-world farey graph
• Maximum matchings in scale-free networks with identical degree distribution
• Coherence Scaling of Noisy Second-Order Scale-Free Consensus Networks
• Spectra, hitting times, and resistance distances of $q$-subdivision graphs
• Renormalization-group theory of the abnormal singularities at the critical-order transition in bond percolation on pointed hierarchical graphs
• Extended corona product as an exactly tractable model for weighted heterogeneous networks
• Scale-free Loopy Structure is Resistant to Noise in Consensus Dynamics in Complex Networks