Exposure predicts learning of complex networks by random walks

Random walks are a common model for exploration and discovery of complex networks. While numerous algorithms have been proposed to map out an unknown network, a complementary question arises: in a known network, which nodes and edges are most likely to be discovered by a random walk in finite time? Here we introduce a new metric of exposure that predicts learning of nodes and edges across several types of networks, including weighted and temporal, and show that edge learning follows a universal trajectory across many orders of magnitude of exposure. While learning of individual nodes and edges is noisy, exposure theory is highly accurate in prediction of aggregate statistics of exploration.