| الملخص: | 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 {𝑢, 𝑣 } with distance 𝑑 > 1 is added as a “long-range" edge with probability proportional to 𝑑−𝑟, where 𝑟 ≥ 0 is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the (decentralised) routing time is 𝑂( (log𝑛)2) when 𝑟 = 2 and 𝑛Ω(1) when 𝑟 ≠ 2. Here, we prove that the random walk also undergoes a phase transition at 𝑟 = 2, but in this case the phase transition is of a different form. We establish that the mixing time is Θ(log𝑛) for 𝑟 < 2, 𝑂( (log𝑛)4) for 𝑟 = 2 and 𝑛 Ω(1) for 𝑟 > 2.
|
|---|