随机图中的两种相变

摘要

本文研究随机图中的两种相变：巨分支的相变与度分布的相变．在第二章，我们研究随机正则图上的非齐次渗流，证明了此渗流的巨分支存在相变，在第三章，我们引入一类随机图模型并证明此类随机图过程的度分布的期望存在相变．为系统介绍自己博士学习期间在随机图方面的研究，我们增加了研究一类顶点有限制的随机图过程的无标度性的第四章与研究Erd(o)s-R(e)nyi随机图的k重支配数的第五章．
　　 渗流是—个重要且热门的概率领域．最近，有限图上的渗流受到了广泛的关注；相关的核心问题是巨分支的相变及其临界概率．在现有数学文献中，所有有限图上的边渗流都是齐次的，即每条边（被独立地删去且）删去的概率是相等的．而在非齐次渗流中，每条边被删去（或者保留）的概率是不相同的．随机图上的一些渗流现象（随机电阻网络，无线通讯网络中带噪声边的信息传输）无法用齐次渗流描述；但却可以用非齐次边渗流来刻画([41]、[31])．这是非齐次渗流的物理意义与数学意义之所在，渗流专家I．Benjamini(ICM2010邀请报告者)认为这种渗流很有意义．关于随机图上非齐次边渗流的相变，物理学者有—个基本猜想（用不严格的方法推导出的基本结论）([31])．对随机正则图上的非齐次边渗流，我们在第二章证明了物理学者的猜想是对的．这是关于随机图上非齐次边渗流的第—个严格的数学结果．具体地，令d(≥3)为一固定的自然数，Gn=G(n，d)是顶点集为Vn={1，…，n)的随机d正则图，考虑Cn上如下的非齐次渗流：（顶点i和j之间的）边eij被保留下来的概率为Xij∈[0，1]；其中诸xij独立同分布．记渗透之后所产生的图为Gn(X），其中X与Xij同分布．令Gn(X)的巨分支（最大连通分支）为C1．则C1在E(x)=3/D-1附近发生相变：(i)当E(x)>3/D-1时，w.h.p.+C1与n同阶；(ii)当E(x)<1/d-1时，w.h.p.Cl至多与logn同阶；(iii)当E(x)=1/d-1时，w．h.p.C1的阶数逼近n2/3．进一步，此相变的临界窗口的宽度是n-1/3．
　　 为研究现实网络，众多专家引入了许多有删点行为的随机图模型；见[26]，[29]以及[30]等，在这些模型中，删点几乎都是一致的，然而，在现实网络中那些很重要的点(Hub)崩溃的可能性显然比那些度很小的点崩溃的可能性要小得多．[30]认为如下的问题很有意义；研究有偏向删点(度越小的顶点删去的可能性越大）的随机图模型；Bonato[20]认为这是一个重要的挑战，注意在经典的Barab(a)si-Albert模型或其他诸如[26]、[29]、[30]等引入的模型中，那些还在此网络中的顶点在任何时刻总是能够与更多的顶点相连．但是在现实网络中由于各种原因有些顶点在某些时刻是不能与更多的顶点相连的（我们用inactiveness来刻画此现象）．第三章和第四章研究上述两种网络现象．在第三章，我们引入了一类有偏向删点且顶点有限制的随机图过程并证明了度分布的期望存在相变：当2β/1-α0>1时，其服从指数分布；当2β/1-α0<1时，其具有无标度性（β，α0的意义见第三章）．在第四章，我们引入了一类顶点有限制的随机图过程且利用统计物理中的主方程方法启发式地证明了此类随机图的度分布是无标度的．注意第四章的模型并不是第三章模型的特殊情形，在第三章中，每个点在任意时刻inactive的概率α0是—个常数；而在第四章inactive的概率α可以是顶点的度的函数，亦可以是—个随机变量，对图G=(V，E)，称顶点集D(∈)V为支配集，若任意的顶点μ∈V\D至少与D中的—个顶点相连，更一般地，任给固定的自然数K，称集合D为一个K重支配集，若任意的顶点u∈V\D至少与D中的K个顶点相连．K重支配数指的是V中的子集V1构成K重支配集所需要的最少顶点数．注意任给K≥1，确定K重支配数是—个NP-hard问题，因此，—个有意义的问题是当一个图的顶点数非常大时如何确定其K重支配数．在第五章，我们证明了对固定的p∈(0，1)，Erdos-Renyi随机图G(n，p)的2重支配数w.h.p.只取两个确定性值，其k重支配数w.h.p.取有限个确定性值．