Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Growing networks with preferential addition and deletion of edges
Stockholm University, Faculty of Science, Department of Mathematics.
Stockholm University, Faculty of Science, Department of Mathematics.
2009 (English)In: Physica A: Statistical Mechanics and its Applications, ISSN 0378-4371, E-ISSN 1873-2119, Vol. 388, no 19, 4297-4303 p.Article in journal (Refereed) Published
Abstract [en]

A preferential attachment model for a growing network incorporating the deletion of edges is studied and the expected asymptotic degree distribution is analyzed. At each time step t=1,2,…, with probability π1>0 a new vertex with one edge attached to it is added to the network and the edge is connected to an existing vertex chosen proportionally to its degree, with probability π2 a vertex is chosen proportionally to its degree and an edge is added between this vertex and a randomly chosen other vertex, and with probability π3=1−π1π2<1/2 a vertex is chosen proportionally to its degree and a random edge of this vertex is deleted. The model is intended to capture a situation where high-degree vertices are more dynamic than low-degree vertices in the sense that their connections tend to be changing. A recursion formula is derived for the expected asymptotic fraction pk of vertices with degree k, and solving this recursion reveals that, for π3<1/3, we have pkk−(3−7π3)/(1−3π3), while, for π3>1/3, the fraction pk decays exponentially at rate (π1+π2)/2π3. There is hence a non-trivial upper bound for how much deletion the network can incorporate without losing the power-law behavior of the degree distribution. The analytical results are supported by simulations.

Place, publisher, year, edition, pages
2009. Vol. 388, no 19, 4297-4303 p.
Keyword [en]
Preferential attachment; Preferential deletion; Complex networks; Random graphs; Degree distribution
National Category
Mathematics
Identifiers
URN: urn:nbn:se:su:diva-36100DOI: 10.1016/j.physa.2009.06.032ISI: 000268653900034OAI: oai:DiVA.org:su-36100DiVA: diva2:288753
Available from: 2010-01-21 Created: 2010-01-21 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Deijfen, Maria
By organisation
Department of Mathematics
In the same journal
Physica A: Statistical Mechanics and its Applications
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 16 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf