小世界模型的伪随机性质

近年来，复杂网络作为描述复杂系统的工具已经得到了广泛而深入的研究。但大多数工作只孤立地研究模型的一个或一些典型性质；对于模型上典型性质间关系的现有研究，还只限于数值分析而非理论阐释。本项目旨在从整体角度研究网络模型上典型性质间的关系，找出理论上最重要的典型性质，即模型的伪随机性质。本项目将着重研究小世界模型。对该模型，我们将改造并发展Erd?s-Rényi模型上伪随机性质研究的相关工具。此外，由于目前基于概率观点的算法复杂性理论还存在着明显的不足，而且也不符合网络模型上算法有效性评估的一般标准。本项目将依据当前广为认可的评估标准，建立新的概率观点下的算法复杂性理论。本项目的研究对随机图、复杂网络理论、以及网络模型上的算法设计与复杂性分析具有很好的理论意义，也必然会有一定的潜在应用。

本项目主要包含两个方面的内容: 1)从整体角度研究小世界模型, 力图能在理论上刻画该模型中最重要的典型性质或不变量; 2)依据当前概率观点下, 算法设计领域中广为认可的标准, 建立新的概率观点下的算法复杂性理论.. 关于第一个方面, 我们发现可以通过建立小世界模型的全系不变量, 得到系统的解决. 而且我们已经基本上确认了, 图的邻接谱就是该模型的一个全系不变量. 此外, 我们还对随机图的邻接谱, 以及图的邻接谱与图结构之间的关系进行了研究, 给出了Erdos-Renyi随机图模型中Estrada指数的准确估计, 得到了图的邻接谱中零特征值的重数与图结构之间的确切关系.. 对于第二个方面, 我们针对现有理论中存在的问题, 提出了解决方案. 事实上, 我们依据基于概率观点设计算法时, 大家普遍采用的标准作为问题易解的标准. 而且, 依据这一标准, 设计出了比Levin理论中问题间的归约更强的新归约. 并建立了该理论框架下的三个完全问题.