License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.29
URN: urn:nbn:de:0030-drops-188542
URL: https://drops.dagstuhl.de/opus/volltexte/2023/18854/
Go to the corresponding LIPIcs Volume Portal


Becker, Ruben ; Casteigts, Arnaud ; Crescenzi, Pierluigi ; Kodric, Bojana ; Renken, Malte ; Raskin, Michael ; Zamaraev, Viktor

Giant Components in Random Temporal Graphs

pdf-format:
LIPIcs-APPROX29.pdf (0.8 MB)


Abstract

A temporal graph is a graph whose edges appear only at certain points in time. In these graphs, reachability among nodes relies on paths that traverse edges in chronological order (temporal paths). Unlike standard paths, temporal paths may not be composable, thus the reachability relation is not transitive and connected components (i.e., sets of pairwise temporally connected nodes) do not form equivalence classes, a fact with far-reaching consequences.
Recently, Casteigts et al. [FOCS 2021] proposed a natural temporal analog of the seminal Erdős-Rényi random graph model, based on the same parameters n and p. The proposed model is obtained by randomly permuting the edges of an Erdős-Rényi random graph and interpreting this permutation as an ordering of presence times. Casteigts et al. showed that the well-known single threshold for connectivity in the Erdős-Rényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting.
The second most basic phenomenon studied by Erdős and Rényi in static (i.e., non-temporal) random graphs is the emergence of a giant connected component. However, the existence of a similar phase transition in the temporal model was left open until now. In this paper, we settle this question. We identify a sharp threshold at p = log n/n, where the size of the largest temporally connected component increases from o(n) to n-o(n) nodes. This transition occurs significantly later than in the static setting, where a giant component of size n-o(n) already exists for any p ∈ ω(1/n) (i.e., as soon as p is larger than a constant fraction of n). Interestingly, the threshold that we obtain holds for both open and closed connected components, i.e., components that allow, respectively forbid, their connecting paths to use external nodes - a distinction arising from the absence of transitivity.
We achieve these results by strengthening the tools from Casteigts et al. and developing new techniques that provide means to decouple dependencies between past and future events in temporal Erdős-Rényi graphs, which could be of general interest in future investigations of these objects.

BibTeX - Entry

@InProceedings{becker_et_al:LIPIcs.APPROX/RANDOM.2023.29,
  author =	{Becker, Ruben and Casteigts, Arnaud and Crescenzi, Pierluigi and Kodric, Bojana and Renken, Malte and Raskin, Michael and Zamaraev, Viktor},
  title =	{{Giant Components in Random Temporal Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18854},
  URN =		{urn:nbn:de:0030-drops-188542},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.29},
  annote =	{Keywords: random temporal graph, Erd\H{o}s–R\'{e}nyi random graph, sharp threshold, temporal connectivity, temporal connected component, edge-ordered graph}
}

Keywords: random temporal graph, Erdős–Rényi random graph, sharp threshold, temporal connectivity, temporal connected component, edge-ordered graph
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI