Random tree growth by vertex splitting

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

doi:10.1088/1742-5468/2009/04/P04009

Random tree growth by vertex splitting

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

Computer And Information Sciences

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Number of pages	47
Journal	Journal of Statistical Mechanics: Theory and Experiment
Volume	2009
Issue number	4
DOIs	https://doi.org/10.1088/1742-5468/2009/04/P04009
Publication status	Published - 9 Apr 2009

Keywords

random graphs
networks
growth processes
exact results

Access to Document

10.1088/1742-5468/2009/04/P04009

Cite this

@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{\c c}ois David and Mark Dukes and Thordur J{\'o}nsson and Stef{\'a}nsson, {Sigurdur {\"O}rn}",

year = "2009",

month = apr,

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",

}

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

SN - 1742-5468

VL - 2009

JO - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

IS - 4

ER -

Random tree growth by vertex splitting

Abstract

Keywords

Access to Document

Fingerprint

Cite this