Impact of initial lattice structures on networks generated by traces of random walks

We show that the platform stage of network evolution plays a principal role in the topology of resulting networks generated by short-cuts stimulated by the movements of a random walker, the mechanism of which tends to produce power-law degree distributions. To examine the numerical results, we have developed a statistical method which relates the power-law exponent gamma to random properties of the subgraph developed in the platform stage. As a result, we find that an important exponent in the network evolution is alpha, which characterizes the size of the subgraph in the form V similar to t(alpha), where V and t denote the number of vertices in the subgraph and the time variable, respectively. 2D lattices can impose specific limitations on the walker's diffusion, which keeps the value of alpha within a moderate range and provides typical properties of complex networks. ID and 3D cases correspond to different ends of the spectrum for alpha, with 2D cases in between. Especially for 2D square lattices, a discontinuous change of the network structure is observed, which varies according to whether gamma is greater or less than 2. For 1D cases, we show that emergence of nearly complete subgraphs is guaranteed by alpha < 1/2, although the transient power-law is permitted at low increase rates of edges. Additionally, the model exhibits a spontaneous emergence of highly clustered structures regardless of its initial structure. (C) 2010 Elsevier B.V. All rights reserved.