On 06 Feb 2008 09:44:30 +0000, Michael Rogers <m.rogers at cs.ucl.ac.uk> wrote: > 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.
Yes, but only if there enough hops to virtually assure that the random walk will stumble from one cluster to the other. > 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... The scenario I outlined above may be too contrived, but I do think we should simulate short walks to find nodes for random swapping, rather than just assuming that a short walk will select a random node with even probability. Ian. -- Email: ian at uprizer.com Cell: +1 512 422 3588 Skype: sanity
