Contact graphs of disk packings as a model of spatial planar networks

Abstract

Spatially constrained planar networks are frequently encountered in real-life systems. In this paper, based on a space-filling disk packing we propose a minimal model for spatial maximal planar networks, which is similar to but different from the model for Apollonian networks [J. S. Andrade, Jr. et al., Phys. Rev. Lett. {\bf 94}, 018702 (2005)]. We present an exhaustive analysis of various properties of our model, and obtain the analytic solutions for most of the features, including degree distribution, clustering coefficient, average path length, and degree correlations. The model recovers some striking generic characteristics observed in most real networks. To address the robustness of the relevant network properties, we compare the structural features between the investigated network and the Apollonian networks. We show that topological properties of the two networks are encoded in the way of disk packing. We argue that spatial constrains of nodes are relevant to the structure of the networks.

12 pages, 7 figures. Definitive version accepted for publication in New Journal of Physics

References in corpus (39)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Assortative mixing in networks
• The architecture of complex weighted networks
• The large-scale organization of metabolic networks
• Evolution of networks
• Classes of behavior of small-world networks
• Critical phenomena in complex networks
• Hierarchical Organization in Complex Networks
• From time series to complex networks: the visibility graph
• Dynamical and correlation properties of the Internet
• Structural Vulnerability of the North American Power Grid
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Adaptive Coevolutionary Networks: A Review
• Scale-Free Networks are Ultrasmall
• Large-scale topological and dynamical properties of Internet
• Weighted evolving networks: coupling topology and weights dynamics
• The spatial structure of networks
• Structural Properties of Planar Graphs of Urban Street Patterns
• General Dynamics of Topology and Traffic on Weighted Technological Networks
• Crossover from Scale-Free to Spatial Networks
• Scale-free Networks on Lattices
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• Self-similar disk packings as model spatial scale-free networks
• Modulated Scale-free Network in the Euclidean Space
• Geography in a Scale-Free Network Model
• Geographical threshold graphs with small-world and scale-free properties
• Structural properties of spatially embedded networks
• High Dimensional Apollonian Networks
• Evolving Apollonian Networks with Small-world Scale-free topologies
• A general geometric growth model for pseudofractal scale-free web
• Exact analytical solution of average path length for Apollonian networks
• Random walks on the Apollonian network with a single trap
• Geographical effects on cascading breakdowns of scale-free networks
• Evolving small-world scale-free networks consist of cliques
• Effects of accelerating growth on the evolution of weighted complex networks
• A geometric growth model interpolating between regular and small-world networks
• Analytical approach to directed sandpile models on the Apollonian network

Cited by in corpus (4)

• Random walks in modular scale-free networks with multiple traps
• Average distance in a hierarchical scale-free network: an exact solution
• An alternative approach to determining average distance in a class of scale-free modular networks
• Combinatorial Properties for a Class of Simplicial Complexes Extended from Pseudo-fractal Scale-free Web