Michael Rogers wrote: > On Oct 17 2007, Matthew Toseland wrote: >> What is mixing? > > If you take a large number of random walks from randomly chosen nodes, the > probability of ending up at each node converges towards what's called the > stationary distribution as the walks get longer. If the convergence > happens quickly, ie a short random walk is nearly equivalent to an > infinitely long random walk, the graph is said to have a fast mixing time. > In other words if a graph is fast mixing, the local structure is in some > sense a good representation of the global structure.
Just saw this paper in the last TOC. I have only read the abstract and not perusing it, but perhaps my be interesting: The Convergence-Guaranteed Random Walk and Its Applications in Peer-to-Peer Networks http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tc/&toc=comp/trans/tc/5555/01/t1toc.xml&DOI=10.1109/TC.2007.70837
