A Hit-and-Run approach for generating scale invariant Small World networks

Abstract

Hit-and-Run is a well-known class of Markov chain algorithms for sampling from essentially arbitrary distributions over bounded regions of the Euclidean space. We present a class of Small World network models constructed using Hit-and-Run in a Euclidean ball. We prove that there is a unique scale invariant model in this class that admits efficient search by a decentralized algorithm. This research links two seemingly unrelated areas: Markov chain sampling techniques and scale invariant Small World networks, and may have interesting implications for stochastic search methods for continuous optimization. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009