On Feb 5 2008, Ian Clarke wrote: >For a random walk of 10 hops to get from cluster A to cluster B, it >needs to find one of the 10 connections between them - yet there are >about 1,250 connections - a 1/125 probability per hop, or a 1/12.5 >probability that a random walk will find one of them. > >This means (if my math and assumptions are reasonable - and they might >not be) that there is only an (approximately) 1/12 probability that a >swap will occur between two nodes in different clusters.
I think your argument applies to short walks, but for longer walks the argument starts to cut both ways (excuse the pun): it's hard to get into clusters, but once you're in it's also hard to get out, so the probability of reaching any given node is less and less affected by the topology. So I guess the question is how many hops we need to reach that point - 10? 100? I was under the impression that short walks were adequate in small-world graphs, but maybe "short" means asymptotically small compared to the size of the graph, rather than usefully implementably short... Cheers, Michael
