Distinct Nodes Visited by Random Walkers on Scale-Free Networks

How fast can a group of randomly walking drunkards starting from one node of a scale-free network explore the rest of the network? We look to answer this question in our work and find that, unlike regular lattices, the number of sites of a scale-free network not visited by any of the random walkers decays as a stretched exponential. Furthermore, we obtain scaling relations that allow us to map the problem with multiple random walkers to that of the analytically tractable single walker problem. A simple presentation of our key findings is provided in this poster which was presented in the WE-Heraeus Seminar “Search and Problem Solving by Random Walks: Drunkards Vs. Quantum Computers” which took place in the Physikzentrum at Bad Honnef near Bonn (Germany) from May 28 to June 1, 2018.

This project was carried out under the guidance of Prof. M. S. Santhanam. The official link to the paper can be found here. You can also obtain a preprint here and here.