Abstract
In this paper, we introduce a model of spatial network growth in which nodes are placed at randomly selected locations on a unit square in R2, forming new connections to old nodes subject to the constraint that edges do not cross. The resulting network has a power law degree distribution, high clustering and the small world property. We argue that these characteristics are a consequence of the two defining features of the network formation procedure; growth and planarity conservation. We demonstrate that the model can be understood as a variant of random Apollonian growth and further propose a one parameter family of models with the Random Apollonian Network and the Deterministic Apollonian Network as extreme cases and our model as a midpoint between them. We then relax the planarity constraint by allowing edge crossings with some probability and find a smooth crossover from power law to exponential degree distributions when this probability is increased.
Original language | English |
---|---|
Pages (from-to) | 500-516 |
Number of pages | 17 |
Journal | Journal of Complex Networks |
Volume | 4 |
Issue number | 4 |
Early online date | 14 Mar 2016 |
DOIs | |
Publication status | Published - Dec 2016 |
Keywords
- Planarity
- Apollonian Networks
- Spatial Networks
Fingerprint
Dive into the research topics of 'Planar growth generates scale-free networks'. Together they form a unique fingerprint.Profiles
-
Professor Seth Bullock
- School of Computer Science - Toshiba Chair in Data Science and Simulation
Person: Academic