Exposure theory for learning complex networks with random walks

2022/02/23 by Klishin, Andrei A., Bassett, Dani S. · 1 citation
#FOS: Computer and information sciences #FOS: Physical sciences #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #Statistical Mechanics (cond-mat.stat-mech)

paper · doi:10.48550/arxiv.2202.11262

Abstract

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 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.

Cited by

• Origins and mitigation of double descent in reduced order modeling

Related

• Identifying Complex Networks by Random Walks
• Random Walks on Complex Networks
• Distinct nodes visited by random walkers on scale-free networks
• Embedding networks with the random walk first return time distribution
• Random walks with long-range memory on networks