  A Markov chain (MC) formalism is used to investigate the mean-square
displacement (MSD) of a random walker on Newman-Watts (NW) networks. It leads
to a precise analysis of the conditions for the emergence of anomalous sub- or
super-diffusive regimes in such random media. Whereas results provided by most
numerical approaches used so far base their results on the computation of a
large number of independent runs over many equivalent substrates, the MC
framework is applied only once to each equivalent sample. Starting from the
simple cycle graph with $2k$ nearest neighbor connections, for which exact MSD
expressions within the MC formalism can be derived, the randomness and
complexity of the substrate is easily controlled by the number $x$ of added
links. Results for different values of $k$, $x$, and the number $N$ of nodes
make it possible to distinguish actual anomalous regimes from transient
behavior and finite size effects. Albeit the high computing cost restricts the
size of our networks to $N\leq1500$ nodes, our very precise results justify a
new and more comprehensive scaling ansatz for walker dynamics, from which the
behavior for very large networks can be derived.
