  We analyze time-discrete and continuous `fractional' random walks on
undirected regular networks with special focus on cubic periodic lattices in
$n=1,2,3,..$ dimensions. The fractional random walk dynamics is governed by a
master equation involving {\it fractional} powers of Laplacian matrices
$L^{\frac{\alpha}{2}}$}where $\alpha=2$ recovers the normal walk. First we
demonstrate that the interval $0<\alpha\leq 2$ is admissible for the fractional
random walk. We derive analytical expressions for fractional transition matrix
and closely related the average return probabilities. We further obtain the
fundamental matrix $Z^{(\alpha)}$, and the mean relaxation time (Kemeny
constant) for the fractional random walk. The representation for the
fundamental matrix $Z^{(\alpha)}$ relates fractional random walks with normal
random walks. We show that the fractional transition matrix elements exhibit
for large cubic $n$-dimensional lattices a power law decay of an
$n$-dimensional infinite space Riesz fractional derivative type indicating
emergence of L\'evy flights. As a further footprint of L\'evy flights in the
$n$-dimensional space, the fractional transition matrix and fractional return
probabilities are dominated for large times $t$ by slowly relaxing long-wave
modes leading to a characteristic $t^{-\frac{n}{\alpha}}$-decay. It can be
concluded that, due to long range moves of fractional random walk, a small
world property is emerging increasing the efficiency to explore the lattice
when instead of a normal random walk a fractional random walk is chosen.
