Exposure theory for learning complex networks with random walks
Abstract
Random walks are a common model for the 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 walker in finite time? Here, we introduce exposure theory, a statistical mechanics framework that predicts the learning of nodes and edges across several types of networks, including weighted and temporal, and show that edge learning follows a universal trajectory. While the learning of individual nodes and edges is noisy, exposure theory produces a highly accurate prediction of aggregate exploration statistics.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 23, 2022
- Source ID
- 10.1093/comnet/cnac029
Entities
People
- Andrei A Klishin
- Danielle Bassett
Organizations
- Army Research Office
- National Institute of Mental Health
- University of Pennsylvania