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.
Expander graphs are fast mixing; I'm not sure about the various small world and scale-free models. The Sybilguard paper says that social networks are also fast mixing but I'm not sure whether it cites a source for that claim. Cheers, Michael
