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

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

在一个常规构建的图中加"长边(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.