  Several kinds of walks on complex networks are currently used to analyze
search and navigation in different systems. Many analytical and computational
results are known for random walks on such networks. Self-avoiding walks (SAWs)
are expected to be more suitable than unrestricted random walks to explore
various kinds of real-life networks. Here we study long-range properties of
random SAWs on scale-free networks, characterized by a degree distribution
$P(k) \sim k^{-\gamma}$. In the limit of large networks (system size $N \to
\infty$), the average number $s_n$ of SAWs starting from a generic site
increases as $\mu^n$, with $\mu = < k^2 > / < k > - 1$. For finite $N$, $s_n$
is reduced due to the presence of loops in the network, which causes the
emergence of attrition of the paths. For kinetic growth walks, the average
maximum length, $< L >$, increases as a power of the system size: $< L > \sim
N^{\alpha}$, with an exponent $\alpha$ increasing as the parameter $\gamma$ is
raised. We discuss the dependence of $\alpha$ on the minimum allowed degree in
the network. A similar power-law dependence is found for the mean
self-intersection length of non-reversal random walks. Simulation results
support our approximate analytical calculations.
