论文标题
相关的随机生长图
Correlated randomly growing graphs
论文作者
论文摘要
我们介绍了一个新的相关随机增长图的模型，并研究了检测相关结构相关和估计方面的基本问题。该模型很简单，从任何随机生长的图形模型开始，例如统一附件（UA）或优先附件（PA）。给定这样的型号，一对图$（g_1，g_2）$在两个阶段生长：直到时间$ t _ {\ star} $它们一起生长在一起（即$ g_1 = g_2 $），之后它们根据潜在的增长模型独立地生长。 我们表明，每当种子图在基础图生长模型中产生影响时，这已显示为PA和UA树，并且可以猜想在该模型中可以检测到相关性，即使该图仅在单个时间步中一起生长。我们还提供了一个一般的条件（适用于PA和UA树），在该条件下可能可以检测到$ 1 $ as $ t _ {\ star} \ to \ infty $，概率为$ 1 $。最后，我们向PA和UA树展示，可以通过$ t _ {\ star} $测量的相关量以消失的相对误差为$ t _ {\ star} \ to \ infty $。
We introduce a new model of correlated randomly growing graphs and study the fundamental questions of detecting correlation and estimating aspects of the correlated structure. The model is simple and starts with any model of randomly growing graphs, such as uniform attachment (UA) or preferential attachment (PA). Given such a model, a pair of graphs $(G_1, G_2)$ is grown in two stages: until time $t_{\star}$ they are grown together (i.e., $G_1 = G_2$), after which they grow independently according to the underlying growth model. We show that whenever the seed graph has an influence in the underlying graph growth model---this has been shown for PA and UA trees and is conjectured to hold broadly---then correlation can be detected in this model, even if the graphs are grown together for just a single time step. We also give a general sufficient condition (which holds for PA and UA trees) under which detection is possible with probability going to $1$ as $t_{\star} \to \infty$. Finally, we show for PA and UA trees that the amount of correlation, measured by $t_{\star}$, can be estimated with vanishing relative error as $t_{\star} \to \infty$.
