论文标题
等级K随机图和有限类型的分支过程
Rank-k random graphs and finite type branching processes
论文作者
论文摘要
在本说明中，我们研究了随机图中的探索过程与分支过程之间的基本关系。我们制定了一类模型，我们称为{\ em rank- $ k $随机图}，这很特别，因为它们的邻居探索可以通过多类型分支过程的{\ em稀疏}获得。我们表明，可以用2型分支过程的稀疏来描述任何级别2随机图，而对于较高的等级，尚不清楚需要多少类型。
In this note, we investigate fundamental relations between exploration processes in random graphs, and branching processes. We formulate a class of models that we call {\em rank-$k$ random graphs}, and that are special in that their neighborhood explorations can be obtained by a {\em thinning} of multi-type branching processes. We show that any rank-2 random graph can be described in terms of thinning of a 2-type branching process, while for higher rank, it is not clear how many types are needed.
