Source-linked AI summary
Random walks and search in time-varying networks
Nicola Perra, Andrea Baronchelli, Delia Mocanu, Bruno Gonçalves, Romualdo Pastor-Satorras, Alessandro Vespignani
TL;DR
The paper studies random walks and mean first passage times in time-varying activity-driven networks, where network and walker dynamics evolve on the same timescale. Analytical results and simulations show behavior unlike quenched and annealed networks, with implications for network search, retrieval, and diffusion.
Problem
Random-walk behavior and network discovery in time-varying networks with dynamically changing connectivity require analysis beyond quenched and annealed topologies.
Method
The paper derives stationary random-walk states and mean first passage times for directed and undirected activity-driven networks.
Results
Time-varying connectivity produces random-walk and discovery behavior strikingly different from quenched and annealed topologies.
Takeaways & Limitations
Dynamical connectivity patterns should be considered when defining strategies for exploring and retrieving information and characterizing spreading and diffusion.
Takeaways & Limitations
The model is Markovian and lacks dynamical correlations found in real networks, whose effects on diffusion require further study.
Abstract
from arXiv · showhide
The random walk process underlies the description of a large number of real world phenomena. Here we provide the study of random walk processes in time varying networks in the regime of time-scale mixing; i.e. when the network connectivity pattern and the random walk process dynamics are unfolding on the same time scale. We consider a model for time varying networks created from the activity potential of the nodes, and derive solutions of the asymptotic behavior of random walks and the mean first passage time in undirected and directed networks. Our findings show striking differences with respect to the well known results obtained in quenched and annealed networks, emphasizing the effects of dynamical connectivity patterns in the definition of proper strategies for search, retrieval and diffusion processes in time-varying networks