  We study the simple random walk dynamics on an annealed version of a
Small-World Network (SWN) consisting of $N$ nodes. This is done by calculating
the mean number of distinct sites visited S(n) and the return probability
$P_{00}(t)$ as a function of the time $t$. $S(t)$ is a key quantity both from
the statistical physics point of view and especially for characterizing the
efficiency of the network connectedness. Our results for this quantity shows
features similar to the SWN with quenched disorder, but with a crossover time
that goes inversely proportianal to the probability $p$ of making a long range
jump instead of being proportional to $p^{-2}$ as in quenched case. We have
also carried out simulations on a modified annealed model where the crossover
time goes as $p^{-2}$ due to specific time dependent transition probabilities
and we present an approximate self-consistent solution to it.
