Tesis Doctoral leída en la Universidad Rey Juan Carlos en 2013. Directores de la Tesis: Antonio Fernández Anta y Luis López Fernández

Random walks have been proven useful in several applications in networks.
For instance, they can be used to locate resources in complex networks.
The networks considered in this dissertation are built randomly, and
their topology is unknown, making the use of random walks very suitable.
However, search lengths (i.e., the length of the random walks) can be large,
and therefore some variants have been devised pursuing a trade-off between
better performance and limited cost. A self-avoiding random walk, for instance,
is one that tries not to revisit nodes, therefore covering the network faster.
Its performance when locating resources has been analyzed using essentially
empirical studies, since a strict analytical approach is hard, because it is not
a Markovian stochastic process. In this dissertation, we propose an analytical
model that allows to estimate the expected search length of self-avoiding
random walks in networks with resource multiplicity. The model includes the
possible availability of one-hop resource replication (i.e., nodes know about
their neighbors¿ resources).
To further reduce search lengths, we propose a resource location mechanism
based on building random walks by connecting together partial random
walks previously computed at each network node. Resources found in each
partial walk are registered, so that searches can jump over partial walks where
the resource is not located. We assume that perfect recording of resources
may be costly, and hence compact probabilistic data structures, like Bloom
filters, are used at the cost of introducing false positives. This mechanism
can be applied to networks with static or dynamic resources. In the latter
case, resource information deteriorates as resources appear and disappear
over time. Different procedures to select a partial walk from a node result in
variations of this mechanism. In addition, partial walks can be either simple
random walks or self-avoiding random walks.
Analytical models are provided to predict expected search lengths and
other magnitudes of the resulting mechanisms. Simulation experiments performed
on several types of networks characterized by their size and degree
distribution are used to validate these predictions and to compare these techniques with simple random walk searches. The experiments show very large
reductions of expected search lengths, even in the face of high resource volatility.

Sistemas Telemáticos y Computación