Random tree growth by vertex splitting

François David, Mark Dukes, Thordur Jónsson, Sigurdur Örn Stefánsson

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

We study a model of growing planar tree graphs where in each time step we separate the tree into two components by splitting a vertex and then connect the two pieces by inserting a new link between the daughter vertices. This model generalizes the preferential attachment model and Ford's α-model for phylogenetic trees. We develop a mean field theory for the vertex degree distribution, prove that the mean field theory is exact in some special cases and check that it agrees with numerical simulations in general. We calculate various correlation functions and show that the intrinsic Hausdorff dimension can vary from 1 to ∞, depending on the parameters of the model.
LanguageEnglish
Number of pages47
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2009
Issue number4
DOIs
Publication statusPublished - 9 Apr 2009

Fingerprint

Random Trees
apexes
Vertex of a graph
Mean-field Theory
Preferential Attachment
Model
Vertex Degree
Phylogenetic Tree
Degree Distribution
Hausdorff Dimension
attachment
Correlation Function
Vary
Calculate
Numerical Simulation
Generalise
Graph in graph theory
simulation

Keywords

  • random graphs
  • networks
  • growth processes
  • exact results

Cite this

David, François ; Dukes, Mark ; Jónsson, Thordur ; Stefánsson, Sigurdur Örn. / Random tree growth by vertex splitting. In: Journal of Statistical Mechanics: Theory and Experiment. 2009 ; Vol. 2009, No. 4.
@article{bb382cd05e174dcb847ab53da141dadb,
title = "Random tree growth by vertex splitting",
abstract = "We study a model of growing planar tree graphs where in each time step we separate the tree into two components by splitting a vertex and then connect the two pieces by inserting a new link between the daughter vertices. This model generalizes the preferential attachment model and Ford's α-model for phylogenetic trees. We develop a mean field theory for the vertex degree distribution, prove that the mean field theory is exact in some special cases and check that it agrees with numerical simulations in general. We calculate various correlation functions and show that the intrinsic Hausdorff dimension can vary from 1 to ∞, depending on the parameters of the model.",
keywords = "random graphs, networks, growth processes, exact results",
author = "Fran{\cc}ois David and Mark Dukes and Thordur J{\'o}nsson and Stef{\'a}nsson, {Sigurdur {\"O}rn}",
year = "2009",
month = "4",
day = "9",
doi = "10.1088/1742-5468/2009/04/P04009",
language = "English",
volume = "2009",
journal = "Journal of Statistical Mechanics: Theory and Experiment",
issn = "1742-5468",
number = "4",

}

Random tree growth by vertex splitting. / David, François; Dukes, Mark; Jónsson, Thordur; Stefánsson, Sigurdur Örn.

In: Journal of Statistical Mechanics: Theory and Experiment, Vol. 2009, No. 4, 09.04.2009.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Random tree growth by vertex splitting

AU - David, François

AU - Dukes, Mark

AU - Jónsson, Thordur

AU - Stefánsson, Sigurdur Örn

PY - 2009/4/9

Y1 - 2009/4/9

N2 - We study a model of growing planar tree graphs where in each time step we separate the tree into two components by splitting a vertex and then connect the two pieces by inserting a new link between the daughter vertices. This model generalizes the preferential attachment model and Ford's α-model for phylogenetic trees. We develop a mean field theory for the vertex degree distribution, prove that the mean field theory is exact in some special cases and check that it agrees with numerical simulations in general. We calculate various correlation functions and show that the intrinsic Hausdorff dimension can vary from 1 to ∞, depending on the parameters of the model.

AB - We study a model of growing planar tree graphs where in each time step we separate the tree into two components by splitting a vertex and then connect the two pieces by inserting a new link between the daughter vertices. This model generalizes the preferential attachment model and Ford's α-model for phylogenetic trees. We develop a mean field theory for the vertex degree distribution, prove that the mean field theory is exact in some special cases and check that it agrees with numerical simulations in general. We calculate various correlation functions and show that the intrinsic Hausdorff dimension can vary from 1 to ∞, depending on the parameters of the model.

KW - random graphs

KW - networks

KW - growth processes

KW - exact results

U2 - 10.1088/1742-5468/2009/04/P04009

DO - 10.1088/1742-5468/2009/04/P04009

M3 - Article

VL - 2009

JO - Journal of Statistical Mechanics: Theory and Experiment

T2 - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

SN - 1742-5468

IS - 4

ER -