From trees to graphs: collapsing continuous-time branching processes

A. Garavaglia, R. van der Hofstad

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
3 Downloads (Pure)


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
Issue number3
Publication statusPublished - 1 Sept 2018


  • Ageing
  • Branching process
  • Preferential attachment


Dive into the research topics of 'From trees to graphs: collapsing continuous-time branching processes'. Together they form a unique fingerprint.

Cite this