From trees to graphs: collapsing continuous-time branching processes

A. Garavaglia, R. van der Hofstad

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Continuous-time branching processes (CTBPs) are powerful tools in random graph theory, but are not appropriate to describe real-world networks since they produce trees rather than (multi)graphs. In this paper we analyze collapsed branching processes (CBPs), obtained by a collapsing procedure on CTBPs, in order to define multigraphs where vertices have fixed out-degree m≥2. A key example consists of preferential attachment models (PAMs), as well as generalized PAMs where vertices are chosen according to their degree and age. We identify the degree distribution of CBPs, showing that it is closely related to the limiting distribution of the CTBP before collapsing. In particular, this is the first time that CTBPs are used to investigate the degree distribution of PAMs beyond the tree setting.

Original languageEnglish
Pages (from-to)900-919
Number of pages20
JournalJournal of Applied Probability
Volume55
Issue number3
DOIs
Publication statusPublished - 1 Sep 2018

Fingerprint

Collapsing
Branching process
Continuous Time
Preferential Attachment
Graph in graph theory
Multigraph
Degree Distribution
Limiting Distribution
Random Graphs
Graph theory
Continuous time
Graph
Model

Keywords

  • Ageing
  • Branching process
  • Preferential attachment

Cite this

@article{98bce4697db44719b66465fbf418f8b0,
title = "From trees to graphs: collapsing continuous-time branching processes",
abstract = "Continuous-time branching processes (CTBPs) are powerful tools in random graph theory, but are not appropriate to describe real-world networks since they produce trees rather than (multi)graphs. In this paper we analyze collapsed branching processes (CBPs), obtained by a collapsing procedure on CTBPs, in order to define multigraphs where vertices have fixed out-degree m≥2. A key example consists of preferential attachment models (PAMs), as well as generalized PAMs where vertices are chosen according to their degree and age. We identify the degree distribution of CBPs, showing that it is closely related to the limiting distribution of the CTBP before collapsing. In particular, this is the first time that CTBPs are used to investigate the degree distribution of PAMs beyond the tree setting.",
keywords = "Ageing, Branching process, Preferential attachment",
author = "A. Garavaglia and {van der Hofstad}, R.",
year = "2018",
month = "9",
day = "1",
doi = "10.1017/jpr.2018.57",
language = "English",
volume = "55",
pages = "900--919",
journal = "Journal of Applied Probability",
issn = "0021-9002",
publisher = "University of Sheffield",
number = "3",

}

From trees to graphs : collapsing continuous-time branching processes. / Garavaglia, A.; van der Hofstad, R.

In: Journal of Applied Probability, Vol. 55, No. 3, 01.09.2018, p. 900-919.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - From trees to graphs

T2 - collapsing continuous-time branching processes

AU - Garavaglia, A.

AU - van der Hofstad, R.

PY - 2018/9/1

Y1 - 2018/9/1

N2 - Continuous-time branching processes (CTBPs) are powerful tools in random graph theory, but are not appropriate to describe real-world networks since they produce trees rather than (multi)graphs. In this paper we analyze collapsed branching processes (CBPs), obtained by a collapsing procedure on CTBPs, in order to define multigraphs where vertices have fixed out-degree m≥2. A key example consists of preferential attachment models (PAMs), as well as generalized PAMs where vertices are chosen according to their degree and age. We identify the degree distribution of CBPs, showing that it is closely related to the limiting distribution of the CTBP before collapsing. In particular, this is the first time that CTBPs are used to investigate the degree distribution of PAMs beyond the tree setting.

AB - Continuous-time branching processes (CTBPs) are powerful tools in random graph theory, but are not appropriate to describe real-world networks since they produce trees rather than (multi)graphs. In this paper we analyze collapsed branching processes (CBPs), obtained by a collapsing procedure on CTBPs, in order to define multigraphs where vertices have fixed out-degree m≥2. A key example consists of preferential attachment models (PAMs), as well as generalized PAMs where vertices are chosen according to their degree and age. We identify the degree distribution of CBPs, showing that it is closely related to the limiting distribution of the CTBP before collapsing. In particular, this is the first time that CTBPs are used to investigate the degree distribution of PAMs beyond the tree setting.

KW - Ageing

KW - Branching process

KW - Preferential attachment

UR - http://www.scopus.com/inward/record.url?scp=85056753729&partnerID=8YFLogxK

U2 - 10.1017/jpr.2018.57

DO - 10.1017/jpr.2018.57

M3 - Article

AN - SCOPUS:85056753729

VL - 55

SP - 900

EP - 919

JO - Journal of Applied Probability

JF - Journal of Applied Probability

SN - 0021-9002

IS - 3

ER -