Network formed by traces of random walks

We propose a model of time evolving networks in which a kind of transport between vertices generates new edges in the graph. We call the model "Network formed by traces of random walks", because the transports are represented abstractly by random walks. Our numerical calculations yield several important properties observed commonly in complex networks, although the graph at initial time is only a one-dimensional lattice. For example, the distribution of vertex degree exhibits various behaviors such as exponential, power law like, and bi-modal distribution according to change of probability of extinction of edges. Another property such as strong clustering structure and small mean vertex-vertex distance can also be found. The transports represented by random walks in a framework of strong links between regular lattice is a new mechanisms which yields biased acquisition of links for vertices. (C) 2007 Elsevier B.V. All rights reserved.