On Sat, 2007-10-20 at 00:49 +0100, Michael Rogers wrote: > 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.
Small-world networks can indeed be fast-mixing, but not all of them. Small-world is a broad term, yet most people just seem to refer to the Kleinberg or Watts-Strogatz model as if it refers to a class of graphs with similar properties. I think it would be most interesting if someone took some time and tried to come up with a reasonable taxonomy of the small-world phenomenon. Thanks for the sim reference Michael. I've given up looking at Freenet topologies in my work for now, but maybe I'll come back to it when the paper deadline isn't so near. Cheers, Cyrus
