Edge-attractor Random Walks on Dynamic Networks

We study the behaviour of continuous time random walks moving over dynamic networks in the presence of mutual dependencies: the walker influences the network dynamics and the network influences the walker steps. We introduce the edge-attractor random walk model in which the network dynamics is biased towards graph configurations displaying higher degree for the vertex currently occupied by the walker. In particular, assuming the walker is in vertex i, the network transition rate to a possible configuration g is linearly proportional to the degree of vertex i in g. The network dynamics, on the other hand, by changing the edge set of the underlying graph configuration, naturally affects the walker behaviour preventing/allowing different walker steps over time. The joint process describing the edge-attractor random walk moving over a dynamic network is a continuous time Markov chain which is shown to be time reversible. By exploiting the time reversibility of the joint chain, we provide a simple expression for the stationary distribution of the edge-attractor random walk in terms of the vertex degrees in the possible network configurations. Interestingly, the stationary distribution of the walker does not depend on the particular transitions of the network dynamics, but only on the set of possible network configurations. We also provide an example of a dynamic network induced by an On-Off edge Markovian process, for which the stationary distribution of the edge-attractor walker is given in a closed-form expression.