论文标题
种植具有优先附着结构的随机图
Growing random graphs with a preferential attachment structure
论文作者
论文摘要
本文的目的是开发一种方法，以证明Gromov-Hausodorff-Prokhorov拓扑中几乎确定收敛的方法，用于一类生长的随机图模型，这些模型概括了Rémy的二进制树算法。我们使用一些迭代胶合结构来描述获得的限制，从而概括了著名的Aldous'Brownian Tree的破线结构。 为此，我们开发了一个框架，在该框架中，沿着（可能是无限的）离散树的结构，通过粘合较小的度量空间（称为\ emph {blocks}）构建度量空间。在这个框架中，我们不断成长的随机图可以理解为沿着不断增长的离散树结构胶粘的块。然后，可以通过分别证明每个块的几乎确定的收敛并验证整个结构的某些相对紧凑性能，从而获得它们的缩放极限收敛。对于我们研究的特定模型，构造背后的离散树结构具有仿射优先附着树或加权递归树的分布。我们强烈依靠有关这两种随机树模型及其连接的结果，这些结果是在同伴论文中获得的。
The aim of this paper is to develop a method for proving almost sure convergence in Gromov-Hausodorff-Prokhorov topology for a class of models of growing random graphs that generalises Rémy's algorithm for binary trees. We describe the obtained limits using some iterative gluing construction that generalises the famous line-breaking construction of Aldous' Brownian tree. In order to do that, we develop a framework in which a metric space is constructed by gluing smaller metric spaces, called \emph{blocks}, along the structure of a (possibly infinite) discrete tree. Our growing random graphs seen as metric spaces can be understood in this framework, that is, as evolving blocks glued along a growing discrete tree structure. Their scaling limit convergence can then be obtained by separately proving the almost sure convergence of every block and verifying some relative compactness property for the whole structure. For the particular models that we study, the discrete tree structure behind the construction has the distribution of an affine preferential attachment tree or a weighted recursive tree. We strongly rely on results concerning those two models of random trees and their connection, obtained in a companion paper.
