Potential induced random teleportation on finite graphs.

Chow, Shui-Nee; Ye, Xiaojing; Zhou, Haomin

We propose and analyze a potential induced random walk and its modification called random teleportation on finite graphs. The transition probability is determined by the gaps between potential values of adjacent and teleportation nodes. We show that the steady state of this process has a number of desirable properties. We present a continuous time analogue of the random walk and teleportation, and derive the lower bound on the order of its exponential convergence rate to stationary distribution. The efficiency of proposed random teleportation in search of global potential minimum on graphs and node ranking are demonstrated by numerical tests. Moreover, we discuss the condition of graphs and potential distributions for which the proposed approach may work inefficiently, and introduce the intermittent diffusion strategy to overcome the problem and improve the practical performance.

FINITE element method; TELEPORTATION; MATHEMATICAL models of diffusion; GRAPHIC methods; STOCHASTIC convergence

Computational Optimization & Applications, 2015, Vol 61, Issue 3, p689

0926-6003

Academic Journal

10.1007/s10589-015-9727-7