Network discovery by generalized random walks

¹ Department of Physics and Interdisciplinary Center for Network Science and Applications (iCeNSA), University of Notre Dame - Notre Dame, IN 46556, USA
² Department of Computer Science and Department of Physics, Rensselaer Polytechnic Polytechnic Institute 110 8 th Street, Troy, NY 12180-3590, USA

^a toro@nd.edu

Received: 23 August 2010
Accepted: 17 November 2010

Abstract

We investigate network exploration by random walks defined via stationary and adaptive transition probabilities on large graphs. We derive an exact formula valid for arbitrary graphs and arbitrary walks with stationary transition probabilities (STP), for the average number of discovered edges as a function of time. We show that for STP walks site and edge exploration obey the same scaling ∼n^λ as a function of time n. Therefore, edge exploration on graphs with many loops is always lagging compared to site exploration, the revealed graph being sparse until almost all nodes have been discovered. We then introduce the edge explorer model (EEM), which presents a novel class of adaptive walks, that perform faithful network discovery even on dense networks.