Semi-Markov random walk on complex networks

We present a semi-Markov model of random walk on complex networks in discrete and continuous-time scenario. In the general setting of the semi-Markov chains, the duration of stay at given node – the sojourn time – is random, and the probability to transition to a neighbour depends on the sojourn time. Analytical formulae for the average sojourn time and the node occupation probability of infinite walk are presented for few cases. For the simplest case the theoretical predictions are verified with Monte Carlo simulations. We propose an application of the semi-Markovian random walk for ranking web pages determined by the fraction of time that infinite random surfer spends on a web page – time rank, as an alternative to the existing PageRank that relies on the fraction of visits – visit rank. • Semi-Markov random walk (SMRW) generalizes the classical Markov random walk. • SMRW on complex networks allows for certain theoretical calculations. • Modelling the mean residence time of surfers at web pages is an application of SMRW. • The classical PageRank estimates the expected number of visits of page – visit rank. • The mean residence time can provide alternative ranking of the nodes - time rank.