Advanced

On the degree evolution of a fixed vertex in some growing networks

Lindholm, Mathias and Vallier, Thomas LU (2011) In Statistics and Probability Letters 81(6). p.673-677
Abstract
Two preferential attachment-type graph models which allow for dynamic addition/deletion of edges/vertices are considered. The focus of this paper is on the limiting expected degree of a fixed vertex. For both models a phase transition is seen to occur, i.e. if the probability with which edges are deleted is below a model-specific threshold value, the limiting expected degree is infinite, but if the probability is higher than the threshold value, the limiting expected degree is finite. In the regime above the critical threshold probability, however, the behaviour of the two models may differ. For one of the models a non-zero (as well as zero) limiting expected degree can be obtained whilst the other only has a zero limit. Furthermore, this... (More)
Two preferential attachment-type graph models which allow for dynamic addition/deletion of edges/vertices are considered. The focus of this paper is on the limiting expected degree of a fixed vertex. For both models a phase transition is seen to occur, i.e. if the probability with which edges are deleted is below a model-specific threshold value, the limiting expected degree is infinite, but if the probability is higher than the threshold value, the limiting expected degree is finite. In the regime above the critical threshold probability, however, the behaviour of the two models may differ. For one of the models a non-zero (as well as zero) limiting expected degree can be obtained whilst the other only has a zero limit. Furthermore, this phase transition is seen to occur for the same critical threshold probability of removing edges as the one which determines whether the degree sequence is of power-law type or if the tails decays exponentially fast. (C) 2011 Elsevier B.V. All rights reserved. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Preferential attachment, Preferential deletion, Expected degree
in
Statistics and Probability Letters
volume
81
issue
6
pages
673 - 677
publisher
Elsevier
external identifiers
  • wos:000292014400008
  • scopus:79952352123
ISSN
0167-7152
DOI
10.1016/j.spl.2011.02.015
language
English
LU publication?
yes
id
0cff87ce-4b4f-4125-a979-d823f53f378d (old id 2032533)
date added to LUP
2011-07-26 14:32:19
date last changed
2017-01-01 06:07:48
@article{0cff87ce-4b4f-4125-a979-d823f53f378d,
  abstract     = {Two preferential attachment-type graph models which allow for dynamic addition/deletion of edges/vertices are considered. The focus of this paper is on the limiting expected degree of a fixed vertex. For both models a phase transition is seen to occur, i.e. if the probability with which edges are deleted is below a model-specific threshold value, the limiting expected degree is infinite, but if the probability is higher than the threshold value, the limiting expected degree is finite. In the regime above the critical threshold probability, however, the behaviour of the two models may differ. For one of the models a non-zero (as well as zero) limiting expected degree can be obtained whilst the other only has a zero limit. Furthermore, this phase transition is seen to occur for the same critical threshold probability of removing edges as the one which determines whether the degree sequence is of power-law type or if the tails decays exponentially fast. (C) 2011 Elsevier B.V. All rights reserved.},
  author       = {Lindholm, Mathias and Vallier, Thomas},
  issn         = {0167-7152},
  keyword      = {Preferential attachment,Preferential deletion,Expected degree},
  language     = {eng},
  number       = {6},
  pages        = {673--677},
  publisher    = {Elsevier},
  series       = {Statistics and Probability Letters},
  title        = {On the degree evolution of a fixed vertex in some growing networks},
  url          = {http://dx.doi.org/10.1016/j.spl.2011.02.015},
  volume       = {81},
  year         = {2011},
}