论文标题
随机重量的随机递归图中的最大程度
The maximal degree in random recursive graphs with random weights
论文作者
论文摘要
我们研究了随机递归树（RRT）模型及其多数对应物的概括，即均匀的定向无环图（DAG）。在这里，顶点配备了随机顶点重量，代表网络中的初始不均匀性，因此新的顶点连接到一个旧顶点，其概率与其顶点 - 权威成正比。我们首先确定均匀选择的顶点的渐近程度分布，以进行一般的顶点重量分布。对于最大程度，我们区分了导致不同行为的几个类别：对于有界的顶点权威，我们获得的最大程度的结果与RRT和DAG所观察到的结果相似。如果顶点重量获得无限的支持，那么最大程度必须满足适当的平衡，在具有较高的顶点重量和早期出生。对于Frechet最大吸引力域中的顶点重量，最大程度的一阶行为是随机的，而对于Gumbel最大吸引力域中的人来说，领先顺序是确定性的。令人惊讶的是，在后一种情况下，在考虑最佳区域的紧凑窗口中的顶点时，二阶是随机的，而在考虑所有顶点时，它变得确定性。
We study a generalisation of the random recursive tree (RRT) model and its multigraph counterpart, the uniform directed acyclic graph (DAG). Here, vertices are equipped with a random vertex-weight representing initial inhomogeneities in the network, so that a new vertex connects to one of the old vertices with a probability that is proportional to their vertex-weight. We first identify the asymptotic degree distribution of a uniformly chosen vertex for a general vertex-weight distribution. For the maximal degree, we distinguish several classes that lead to different behaviour: For bounded vertex-weights we obtain results for the maximal degree that are similar to those observed for RRTs and DAGs. If the vertex-weights have unbounded support, then the maximal degree has to satisfy the right balance between having a high vertex-weight and being born early. For vertex-weights in the Frechet maximum domain of attraction the first order behaviour of the maximal degree is random, while for those in the Gumbel maximum domain of attraction the leading order is deterministic. Surprisingly, in the latter case, the second order is random when considering vertices in a compact window in the optimal region, while it becomes deterministic when considering all vertices.
