论文标题
动态随机图带有顶点去除
Dynamic random graphs with vertex removal
论文作者
论文摘要
我们介绍并分析了一个动态随机图，其定义为如下的顶点删除（DRGVR）。在每个步骤中，使用概率$ p> 1/2 $引入了新的顶点，并且概率$ 1-p $ a顶点，在当前的顶点（如果有的话）在图中随机选择，将其从图中删除，将其与与之相邻的所有边缘一起从图中删除。在前一种情况下，新的顶点通过边缘连接到其他每个顶点，概率与已经存在的顶点成反比。 我们证明DRGVR收敛到局部限制并确定此限制。此外，我们分析了其组成结构，并就巨大组成部分的存在区分了亚临界和超临界状态。作为该分析的副产品，我们获得了关键参数的上限和下限。此外，我们提供了最大程度的精确表达（以及DRGVR自然取向的内度和外观）。几个浓度和稳定性结果完成了研究。
We introduce and analyse a Dynamic Random Graph with Vertex Removal (DRGVR) defined as follows. At every step, with probability $p > 1/2$ a new vertex is introduced, and with probability $1-p$ a vertex, chosen uniformly at random among the present ones (if any), is removed from the graph together with all edges adjacent to it. In the former case, the new vertex connects by an edge to every other vertex with probability inversely proportional to the number of vertices already present. We prove that the DRGVR converges to a local limit and determine this limit. Moreover, we analyse its component structure and distinguish a subcritical and a supercritical regime with respect to the existence of a giant component. As a byproduct of this analysis, we obtain upper and lower bounds for the critical parameter. Furthermore, we provide precise expression of the maximum degree (as well as in- and out-degree for a natural orientation of the DRGVR). Several concentration and stability results complete the study.
