网络的小世界结构及其上随机游动的混合时

Small world effect is one of the most important features of real-world complex networks. In this project, we will first study the underline causes which make most of the real-world networks small world. Second, we will study the behaviors of random walks on small world networks. By studying the mixing time of random walks, we try to develop a good sampling method on complex networks. The present project focuses on the following two aspects: 1, analyze the inner causes which make the real-world complex networks always small world, then establish approprate mathematical models to describe the evolving processes of real-world netwoks. With the help of the mathematical models, we finally prove the small world property of real-world complex networks. 2, for the small worlds established in 1, we study the mixing time of random walks on them. By deriving proper lower and super bounds to the mixing times, we study the possibility that random walk mixes in short time. The answer to the second problem, for example, if it is proved that the random walks can get mixed in short time,then this just provides a good sampling methed according to the degree sequences of complex networks.

小世界效应（small world effect）是现实复杂网络（real-world complex networks）的重要特征。本项目将首先致力于研究现实复杂网络小世界性的内在形成机制。其次，我们将研究小世界网络上的随机游动（random walk）。通过研究小世界网络上的随机游动的混合时（mixing time），我们研究复杂网络上基于随机游动的快速抽样方法。 本项目具体聚焦于以下两个方面：一、分析现实复杂网络所以多为小世界的内在原因， 在此基础上，建立合理刻画网络演化过程的数学模型，并证明模型的小世界性。二、对建立 的新的小世界模型， 研究其上随机游动的混合时。通过给出过程混合时的合适的上下界估计，探讨过程短时内达到混合的可能性。对第二个问题的解答，比如，证明过程在短时内达到混合，就恰好给出了复杂网络上相对于度序列的一个好的抽样方法。

复杂网络是近二十年来走进人们日常生活的重要的新鲜事物，以互联网为代表的各类网络的蓬勃发展，正改变或已经改变了客观世界，也改变着人们的生活方式。在应用数学领域，将对复杂网络的研究纳入严格数学的范畴，解释并预测网络的各项结构特征，行为特征就成为应用数学该发展的一个新方向。本项目的主要目标是研究复杂网络的小世界机制，即网络是如何发展成小世界的。其次，我们研究小世界网络上过程：随机游走过程和尾达渗流过程。一类重要的复杂网络是几何网络，其特征是，网络的节点是欧式空间中实在的点，而建立点与点之间的连接的费用随两点之间的欧氏距离的增长而增长。互联网，电力网，道路交通网等就是这样的网络。观察认为，几何网络的小世界来源于人们因需求激发的有意识作为，即网络本来不是小世界的，因为我们需要小世界，于是人为改造网络，最后建设成为小世界。对几何网络的小世界原理的数学研究源于Watts和Newman早期的工作，Newman和Watts建立数学模型证明，在非小世界网上，人为引入“shortcuts”（即直接建立远距离节点之间的连接），可以使所得到的网络是小世界的。我们的研究基于以下观察：只有距离足够大的两点，它们之间引入shortcut，才可能导致网络的小世界化。为此在最大限度地与现实相合的前提下，我们建立Poisson几何小世界模型，证明了这个观点。该文于2017年发表在网络数学的专业杂志Internet Mathematics上。该结果是项目研究的主要成果，它深刻而精致地刻画了几何网络的小世界机制。作为以上结果的一个补充，我们还研究了所谓“修正的Newman-Watts模型”，我们证明，以上机制不仅导致小世界，而且恰好导致小世界。项目的另一个目标是研究小世界网络上的过程。对Poisson几何小世界模型和修正的Newman-Watts模型，我们分别研究其上的随机游动，我们证明它们是快速混合的，即过程以极快（相比于网络规模）的速度达到平稳分布。另一方面，对经典的小世界网络，随机图模型，我们研究其上的尾达渗流。我们得到两方面的成果：一是时间常数的存在性及偏差概率的衰减速率。二是尾达时间的方差估计问题，事实上，我们证明该时间的方差可以是有限的、对数增长以及次线性增长的。方差估计问题是首达渗流关心的主要问题，我们的方法和结论对该问题的研究有重要借鉴作用，这也是我们下一段研究的主要课题。