Network formed by movements of random walkers on a Bethe lattice

We investigate a stochastic model of network formation where short-cut edges are assumed to be created between vertices in traces of random walkers. The network initially starts from a tree-like structure (Bethe lattice) with a finite number of shells, and develops into a complex network with many circuits generated by the movement of random walkers. We show that the resulting network has a power-law in the degree distribution with an exponent smaller than 2, and demonstrate the robustness against attacks on hubs in the networks. While scale-free networks without a degree correlation are usually vulnerable to attacks on its hubs, the robustness of the network connectivity in this model comes from a self-similar structure of the network. It is interesting that a simple stochastic process like random walks can cause various structures widely seen in real networks on tree-like graphs which play an important role in the graph theory