Search Results

Documents authored by Schleicher, Nick


Document
Early Typical Vertices in Subcritical Random Graphs of Preferential Attachment Type

Authors: Peter Mörters and Nick Schleicher

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)


Abstract
We study the size of the connected component of early typical vertices in a subcritical inhomogeneous random graph with a kernel of preferential attachment type. The principal tools in our analysis are, first, a coupling of the neighbourhood of a typical vertex in the graph to a killed branching random walk and, second, an asymptotic result for the number of particles absorbed at the killing barrier in this branching random walk.

Cite as

Peter Mörters and Nick Schleicher. Early Typical Vertices in Subcritical Random Graphs of Preferential Attachment Type. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 14:1-14:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{morters_et_al:LIPIcs.AofA.2024.14,
  author =	{M\"{o}rters, Peter and Schleicher, Nick},
  title =	{{Early Typical Vertices in Subcritical Random Graphs of Preferential Attachment Type}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{14:1--14:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.14},
  URN =		{urn:nbn:de:0030-drops-204493},
  doi =		{10.4230/LIPIcs.AofA.2024.14},
  annote =	{Keywords: Inhomogeneous random graphs, preferential attachment, networks, subcritical behaviour, size of components, connectivity, coupling, branching random walk, random tree}
}