  We present the analytical and numerical results of a random walk on the
family of small-world graphs. The average access time shows a crossover from
the regular to random behavior with increasing distance from the starting point
of the random walk. We introduce an {\em independent step approximation}, which
enables us to obtain analytic results for the average access time. We observe a
scaling relation for the average access time in the degree of the nodes. The
behavior of average access time as a function of $p$, shows striking similarity
with that of the {\em characteristic length} of the graph. This observation may
have important applications in routing and switching in networks with large
number of nodes.
