有限图上的博弈渗流与非齐次渗流模型

This project is going to investigate the following two kinds of percolation on finite graphs. One is game percolation, i.e. Maker and Breaker take turns to choose edges and retain them independently with p1 and p2 respectively on finite graph G in which every edge can only be chosen once. Maker tries to obtain a subgraph with some graph property while Breaker tries his best to stop it. Especially for game percolation on complete graph we try to find out the sufficient and necessary conditions to make sure Maker can get a subgraph which is of some graph property. The other is inhomogeneous percolation (i.e. the probabilities of retaining edges are not consistent), especially on complete graph, random d-regular graph and random graph with given degree sequence. We look for the criteria for the existence of giant component which is a connected subgraph with a constant fraction of G's vertices. These two models can characterize the robustness of real-world networks better than homogeneous percolation does.

本课题将研究如下两类渗流模型：1. 有限图上的博弈渗流，即选手Maker及Breaker轮流在有限图G上选边(每条边只能被选一次)，Maker所选的每条边独立地以概率p1保留，Breaker所选的每条边独立地以概率p2保留。Maker的目标是建立一个具有某种图性质的子图而Breaker试图阻止其出现。特别地，当G为完全图时我们将寻找Maker能构造出一个具有某种图性质的子图的充要条件。2. 有限图上的非齐次渗流(即每条边保留的概率不一致)，特别是完全图、随机d-正则图以及给定度序列随机图上的非齐次渗流，寻找此类渗流存在巨分支的判断法则。上述两类渗流比齐次渗流能更好地刻画现实网络的鲁棒性。

(1) 研究了完全图上的一种非齐次边渗流(随机相交图)，利用耦合方法、鞅方法、停时定理等研究了临界随机相交图的最大分支，证明了其存在相变，其中一类临界随机相交图的最大分支大小依赖于随机相交图定义中的参数，而另一类临界随机相交图的最大分支大小与参数无关。.(2) 研究了一类随机图上的非齐次点渗流（有偏向删顶点情形，已有随机图过程基本都是一致删点的），利用耦合方法、鞅停时定理证明了此类渗流后其度序列分布的期望存在相变，当其参数满足一定条件的时候，其度分布的期望是呈指数衰减；当其参数不满足这个条件时，其度分布的期望呈幂率衰减。此随机图推广了经典Barabasi-Albert模型，更好解释了一些经济网络现象；同时进一步确认了物理学者提出的一个问题：是否存在一个随机图模型使得当其参数变化时，度分布类型不一样。.(3) 首次提出了随机违约顺序并引入条件自上而下方法；该方法通过提前确定违约顺序把无序的个体违约时间转换成次序违约时间；其优势在于结合了组合信用风险建模的两类传统方法（自上而下法、自下而上法）的优点，使得定价和对冲的相关计算变得简单。.(4) 研究了圈上的多重懒惰随机游走，利用耦合方法证明了其最大相遇时的期望的阶数为hmax*log n, 其中hmax 为圈上的一简单随机游走的最大击中时。.(5) 研究了随机变量序列和的收敛性以及生物网络上的疾病基因等。