Exploring multi-layered networks through random walks: bridging offline optimization and online learning

The multi-layered network exploration problem MuLaNE is a significant challenge derived from various practical applications. In MuLaNE, there are multiple layers of the network, where each node is assigned an importance weight, and each layer is explored through random walks. The objective is to allocate a total random walk budget B across the network layers to maximize the cumulative weights of the unique nodes visited. We systematically approach this problem by addressing both offline optimization and online learning scenarios. For the offline optimization case, where the network structure and node weights are known, we propose constant-ratio approximation algorithms based on greedy strategies for overlapping networks, and exact optimal solutions using greedy or dynamic programming for non-overlapping networks. In the online learning scenario, where neither the network structure nor the node weights are initially known, we adapt the combinatorial multi-armed bandit framework. We develop algorithms with two distinct confidence radius designs to simultaneously learn random walk parameters and node weights, while optimizing budget allocation across multiple rounds, achieving logarithmic regret bounds. Finally, experimental results on real-world social and computer networks validate the practical applicability of MuLaNE and our theoretical findings. © 2026 Published by Elsevier B.V.