random walk

the stationary distribution on V is a uniform distribution if the graph is regular, and the stationary distribution is unique(connected graph)

the most important property about stationary distribution is that if the graph is non-bipartite, the distribution V(t) tends to a stationary distribution, with t --> infinity

The surprising fact, is that the mixting time may be much less than the number of the nodes; for an expander graphy, it takes log(n), where an expander is a graph in which the neighborhood of any set of vertices S is large relative to the size of S

The problem of deciding whether a graph is an expander is known to be co-NP-complete