Random Walks on Small World Networks
Random Walks on Small World Networks
复制标题
小世界网络上的随机游走
DOI：
10.1145/3382208
复制
发表时间：
2020
影响因子：
1.3
通讯作者：
Dyer M
中科院分区：
文献类型：
--
作者：
Dyer M
本文研究了小世界网络上随机游动的混合时间：从二维周期网格开始，每对距离d> 1的顶点{u，v}被添加为概率与d-r成正比的“长程”边，其中r≥ 0是模型的一个参数。Kleinberg [33]{研究了这个网络模型的一个近似变体，并证明了当r =2时（分散）路由时间为O（（logn）2），当r = 2时为nΩ（1）。在这里，我们证明了随机游动也经历了atr=2的相变，但在这种情况下，相变是不同的形式。我们建立了r< 2时混合时间为n Ω（logn），r =2时为O（（logn）4），r> 2时为n Ω（1）.
We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d> 1 is added as a “long-range” edge with probability proportional to d-r, where r≥ 0 is a parameter of the model. Kleinberg [33{ studied a close variant of this network model and proved that the (decentralised) routing time is O((logn)2) whenr=2 and nΩ (1)when r≠ 2. Here, we prove that the random walk also undergoes a phase transition atr=2, but in this case, the phase transition is of a different form. We establish that the mixing time is ϴ (log n) for r< 2, O((logn)4) forr=2, andnΩ (1)for r> 2.