Resource Location Mechanisms for Complex Networks Based on Random Walks

Abstract

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.