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

作者：吴宪远; 祝锐^*

来源：数学学报(中文版), 2020, 63(02): 181-192.

• 随机网络
• 小世界效应
• 随机游走
• 混合时

在一个常规构建的图中加"长边(shortcuts)"会得到一个小世界模型,这是经典的构造小世界模型的方法.最近,吴宪远在文[Internet Mathematics,DOI:10.1080/15427951,2015.101208]中指出,在加"长边"过程中加的所有边,只有与图的直径成正比才会对小世界模型的构造起决定性作用.我们依据此文的加边机制,对体积为nd的d(d≥1)维格点图,只添加起决定性作用的长边,得到的小世界模型修正了原始的Newman-Watts小世界模型,并证明该模型的直径和混合时是log n阶的.

• 单位
  首都师范大学