Scale-Free Networks Generated By Random Walkers

Jari Saramaki, Kimmo Kaski

Published 2004-04-05Version 1

We present a simple mechanism for generating undirected scale-free networks using random walkers, where the network growth is determined by choosing parent vertices by sequential random walks. We show that this mechanism produces scale-free networks with degree exponent gamma=3 and clustering coefficients depending on random walk length. The mechanism can be interpreted in terms of preferential attachment without explicit knowledge of node degrees.