{'fraction_non_alphanumeric': 0.06500691562932227, 'fraction_numerical': 0.02074688796680498, 'mean_word_length': 4.134751773049645, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Random Walks on Small World Networks

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((log n)2) when r=2 and nΩ (1) when r≠ 2. Here, we prove that the random walk also undergoes a phase transition at r=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((log n)4) for r=2, and nΩ (1) for r> 2.