Exploring complex networks by means of adaptive walkers

Abstract

Finding efficient algorithms to explore large networks with the aim of recovering information about their structure is an open problem. Here, we investigate this challenge by proposing a model in which random walkers with previously assigned home nodes navigate through the network during a fixed amount of time. We consider that the exploration is successful if the walker gets the information gathered back home, otherwise, no data is retrieved. Consequently, at each time step, the walkers, with some probability, have the choice to either go backward approaching their home or go farther away. We show that there is an optimal solution to this problem in terms of the average information retrieved and the degree of the home nodes and design an adaptive strategy based on the behavior of the random walker. Finally, we compare different strategies that emerge from the model in the context of network reconstruction. Our results could be useful for the discovery of unknown connections in large scale networks.

10 pages, 10 figures

References in corpus (7)

• Critical phenomena in complex networks
• Efficient Immunization Strategies for Computer Networks and Populations
• Dynamics of jamming transitions in complex networks
• On the universality of the scaling of fluctuations in traffic on complex networks
• Scaling breakdown in flow fluctuations on complex networks
• Exploring Complex Networks through Random Walks
• Smart random walkers: the cost of knowing the path

Cited by in corpus (10)

• Random walks on networks with stochastic resetting
• Characteristic times of biased random walks on complex networks
• Random walks on complex networks with first-passage resetting
• Random walks on complex networks under node-dependent stochastic resetting
• Random walks on complex networks under time-dependent stochastic resetting
• Random walks on complex networks with multiple resetting nodes: a renewal approach
• Derivative-variable correlation reveals the structure of dynamical networks
• Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Network
• Network heterogeneity and node capacity lead to heterogeneous scaling of fluctuations in random walks on graphs
• Non-equilibrium random walks on multiplex networks