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

项目名称： 网络的小世界结构及其上随机游动的混合时

项目编号： No.11471222

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 吴宪远

作者单位： 首都师范大学

项目金额： 65万元

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

中文关键词： 随机网络；随机游动；小世界；混合时；随机抽样

英文摘要： 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.

英文关键词： random network;random walk;small world;mixing time;random sampling