Exploring Low-degree nodes first accelerates Network Exploration

What is it about?

We consider information diffusion on Web-like networks and how random walks can simulate it. A well-studied problem in this domain is Partial Cover Time, i.e., the calculation of the expected number of steps a random walker needs to visit a given fraction of the nodes of the network.

Featured Image

Photo by Alina Grubnyak on Unsplash

Photo by Alina Grubnyak on Unsplash

Why is it important?

Existing solutions for the Cover time problem might be extended to the Partial Cover Time but they make assumptionswhich we believe are unrealistic in Web applications We introduce a version of the Cover problem called "Partial Cover Time with Budget." The budget is a limit on the number of neighbors that can be inspected for their degree; Our algorithm is called Min-degree (MD) and, essentially, it biases random walkers towards visiting peripheral areas of the network first. Extensive benchmarking on six real datasets proves that the---perhaps counter-intuitive strategy---MD strategy is in fact highly competitive wrt. state-of-the-art algorithms for cover.