  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 function of
time. We show that for STP walks site and edge exploration obey the same
scaling $\sim n^{\lambda}$ as 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, which presents a novel class of
adaptive walks, that perform faithful network discovery even on dense networks.
