Network formed by movements of random walkers on a Bethe lattice

2nd International Conference on Mathematical Modeling in Physical Sciences 2013

物理学;数学

Ikeda, Nobutoshi^1

Tohoku Seikatsu Bunka Junior College, 1-18-2 Niji-no-Oka, Izumi-ku, Sendai 981-8585, Japan^1

关键词: Bethe lattice;    Degree correlation;    Degree distributions;    Network connectivity;    Network formation;    Random walkers;    Real networks;    Tree-like structures;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/490/1/012189/pdf
DOI  :  10.1088/1742-6596/490/1/012189

来源: IOP

【 摘 要 】

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.