Planar growth generates scale-free networks

Garvin Haslett, Seth Bullock, Marcus Brede

Research output: Contribution to journalArticle (Academic Journal)peer-review

1 Citation (Scopus)
295 Downloads (Pure)

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 languageEnglish
Pages (from-to)500-516
Number of pages17
JournalJournal of Complex Networks
Volume4
Issue number4
Early online date14 Mar 2016
DOIs
Publication statusPublished - 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.

Cite this