Methods for creating scale-free networks without resorting to global knowledge

Abstract

This paper is a progress report on investigations into methods for evolving scalefree networks using less-than-global knowledge of network characteristics. The motivation for this work is the reliance on global knowledge by the now wellknown Albert-Barabási algorithm for evolving fat-tailed networks exhibiting powerlaw node degree distributions. This paper examines three approaches, namely tournament selection, a deterministic walk, and a stochastic walk. These methods yield fat-tailed node degree distributions to a greater or lesser extent, but not "classic" power-law distributions. The investigation is on-going.