First passage percolation on random graphs with finite mean degrees
First passage percolation on random graphs with finite mean degrees
复制标题
DOI：
10.1214/09-aap666
复制
发表时间：
2009-03
影响因子：
1.8
通讯作者：
S. Bhamidi;R. Hofstad;G. Hooghiemstra
中科院分区：
文献类型：
--
作者：
S. Bhamidi;R. Hofstad;G. Hooghiemstra
我们在构型模型上研究了第一通道渗流。假设每条边都有一个独立的指数分布的边权重，我们推导出了网络中两个随机选择的连通顶点之间的最小权值以及最轻路径上的边数的显式分布渐近，即所谓的跳数。我们分析了阶次幂指数为τ>；2的构型模型，其中阶数设为I.I.D.具有指数为τ−1>；1的幂函数形式的尾部分布，或者具有更细的尾部(τ=∞)。在这个模型中，阶数的一阶矩是有限的，而τ>；3的方差是有限的，而τ∈(2，3)的方差是无穷的。我们证明了Hopcount的一个中心极限定理，其中均值和方差渐近相等等于αlogn，其中α∈(0，1)表示τ∈(2，3)，而α>；1表示τ>；3。这里n表示图的大小。对于τ∈(2，3)，已知两个随机选择的连通顶点之间的图距离与loglogn[25]成正比，即距离超小。因此，边权重的增加会导致网络几何结构的显著变化。我们进一步研究了最小权路径的权重，并证明了适当中心形式的分布收敛。这项研究继续了在[5]中启动的程序，证明了在I.I.D.下，logn是跳数的正确标度。边无序，即使两个随机选择的顶点之间的图形距离的阶数要小得多。文献[6]研究了无穷平均次数(τ∈[1，2))的情形，证明了Hopcount保持一致有界且按分布收敛。
We study first passage percolation on the configuration model. Assuming that each edge has an independent exponentially distributed edge weight, we derive explicit distributional asymptotics for the minimum weight between two randomly chosen connected vertices in the network, as well as for the number of edges on the least weight path, the so-called hopcount. We analyze the configuration model with degree power-law exponent τ > 2, in which the degrees are assumed to be i.i.d. with a tail distribution which is either of power-law form with exponent τ − 1 > 1, or has even thinner tails (τ = ∞). In this model, the degrees have a finite first moment, while the variance is finite for τ > 3, but infinite for τ ∈ (2, 3). We prove a central limit theorem for the hopcount, with asymptotically equal means and variances equal to α log n, where α ∈ (0, 1) for τ ∈ (2, 3), while α > 1 for τ > 3. Here n denotes the size of the graph. For τ ∈ (2, 3), it is known that the graph distance between two randomly chosen connected vertices is proportional to log log n [25], i.e., distances are ultra small. Thus, the addition of edge weights causes a marked change in the geometry of the network. We further study the weight of the least weight path, and prove convergence in distribution of an appropriately centered version. This study continues the program initiated in [5] of showing that log n is the correct scaling for the hopcount under i.i.d. edge disorder, even if the graph distance between two randomly chosen vertices is of much smaller order. The case of infinite mean degrees (τ ∈ [1, 2)) is studied in [6], where it is proved that the hopcount remains uniformly bounded and converges in distribution.