Critical random graphs and the differential equations technique
Critical random graphs and the differential equations technique
复制标题
临界随机图和微分方程技术
DOI：
10.1007/s13226-017-0249-0
复制
发表时间：
2018
影响因子：
0.7
通讯作者：
Bhamidi S
中科院分区：
文献类型：
--
作者：
Bhamidi S
在过去的几年里，已经假设了大量的随机图模型来理解经验观察网络的属性。这些模型中的大多数都带有一个参数t（通常与边缘密度有关）和一个（依赖于模型的）临界值c，用于指定何时出现巨型组件。有证据表明，对于广泛的一类模型，在矩条件下，这种涌现的性质是普遍的，看起来像经典的Erdens-Rényi随机图，以及（a）在该窗口中的组件的尺寸（所有最大分量大小的比例为2/3）和（B）分量的结构（重新比例为n-1/3）收敛到与连续随机树相关的随机分形。本说明的目的是对这一领域的最新突破进行非技术性概述，强调证明此类结果的特殊工具，称为微分方程技术，该技术首先在Wormald [52，53]的工作中开发并广泛用于概率组合学，并在[10-12]中由作者及其合作者在临界随机图的背景下开发。
Over the last few years a wide array of random graph models have been postulated to understand properties of empirically observed networks. Most of these models come with a parametert(usually related to edge density) and a (model dependent) critical timetcthat specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdős-Rényi random graph, in the sense of the critical scaling window and (a) the sizes of the components in this window (all maximal component sizes scaling liken2/3) and (b) the structure of components (rescaled byn−1/3) converge to random fractals related to the continuum random tree. The aim of this note is to give a non-technical overview of recent breakthroughs in this area, emphasizing a particular tool in proving such results called the differential equations technique first developed and used extensively in probabilistic combinatorics in the work of Wormald [52, 53] and developed in the context of critical random graphs by the authors and their collaborators in [10–12].
登录
查看更多内容
DOI：
10.1007/bfb0092620
发表时间：
1997
期刊：
--
影响因子：
--
作者：
G. Grimmett
通讯作者：
G. Grimmett
DOI：
--
发表时间：
2011
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
O. Riordan
通讯作者：
O. Riordan
影响因子：
1
作者：
Tomasz Łuczak
通讯作者：
Tomasz Łuczak
Erdős-Rényi 随机图过程中的相变
影响因子：
2
作者：
B. Bollobás;O. Riordan
通讯作者：
O. Riordan
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
Adrien Joseph
通讯作者：
Adrien Joseph