论文标题
随机时间图中的巨型组件
Giant Components in Random Temporal Graphs
论文作者
论文摘要
时间图是一个图形，其边缘仅在某些时间点出现。最近，第二名和最后三位作者提出了Erdős-rényi随机图模型的自然时间类似物。提出的模型是通过随机置换Erdős-rényi随机图的边缘而获得的，并将此置换解释为存在时间的顺序。结果表明，在时间环境中，ERDőS-Rényi模型风扇中的连接性阈值分为多个相位转换。 在本文中，我们确定了巨大的临时连接组件出现的尖锐阈值。我们表明，在$ p = \ log n/n $时，最大的时间连接组件的大小从$ o（n）$增加到〜$ n-o（n）$。此阈值适用于开放和封闭的连接组件，即分别允许其连接路径使用外部节点的组件。
A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős-Rényi random graph model. 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. It was shown that the connectivity threshold in the Erdős-Rényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting. In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at $p = \log n/n$ the size of the largest temporally connected component increases from $o(n)$ to~$n-o(n)$. This threshold holds for both open and closed connected components, i.e. components that allow, respectively forbid, their connecting paths to use external nodes.
