From trees to graphs: collapsing continuous-time branching processes

A. Garavaglia, R. van der Hofstad

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

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

Keywords

  • Ageing
  • Branching process
  • Preferential attachment

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

Cite this