修正的Newman-Watts小世界及其上随机游走的混合时  

On the Modified Newman-Watts Small World and Its Random Walk

作　　者：吴宪远[1] 祝锐 Xian Yuan WU;Rui ZHU(School of Mathematical Sciences,Capital Normal University,Beijing 100048,P.R.China)

机构地区：[1]首都师范大学数学科学学院,北京100048

出　　处：《数学学报（中文版）》2020年第2期181-192,共12页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金资助项目(11271356,11471222);北京市自然科学基金(KM201510028002);首都师范大学交叉科学研究院(19530012012)资助。

摘　　要：在一个常规构建的图中加"长边(shortcuts)"会得到一个小世界模型,这是经典的构造小世界模型的方法.最近,吴宪远在文[Internet Mathematics,DOI:10.1080/15427951,2015.101208]中指出,在加"长边"过程中加的所有边,只有与图的直径成正比才会对小世界模型的构造起决定性作用.我们依据此文的加边机制,对体积为n^d的d(d≥1)维格点图,只添加起决定性作用的长边,得到的小世界模型修正了原始的Newman-Watts小世界模型,并证明该模型的直径和混合时是log n阶的.It is well known that adding "long edges(shortcuts)" to a regularly constructed graph will make the resulted model a small world.Recently,[Internet Mathematics,DOI:10.1080/15427951,2015.101208] indicated that,among all long edges,those edges with length proportional to the diameter of the regularly constructed graph may play the key role.In this paper,we modify the original Newman-Watts small world by adding only long special edges to the d(d≥1)-dimensional lattice torus(with size nd) according to [Internet Mathematics,DOI:10.1080/15427951,2015.101208],and show that both the diameter of the modified model and the mixing time of random walk on it grow polynomially fast in log n.

关 键 词：随机网络 小世界效应 随机游走 混合时 

分 类 号：O211.9[理学—概率论与数理统计]