Uniform random walks in very large models
Johan Oudinet · 2007
This paper presents first experimental results on uniform random generation of paths in very large graphs that model concurrent systems, as it was presented in [3]. The approach is based on techniques and tools for counting and drawing uniformly at random in combinatorial structures. It exploits the fact that in a system made of several concurrent components, local uniform drawings of component paths can be combined into a very good approximation of uniform drawing of paths in the global system, without constructing the global model. The paper describes some implementation of the methods presented in [3], reports results on a first suite of benchmarks, exploring the limits and the possibility of this new approach to uniform random walks.