Optimized graph topologies for probabilistic search

This paper investigates the effect on the performance of a mobile searcher caused by altering the search environment. We model the search environment as a simple connected undirected graph. By adding non-existing edges to the graph we change the search environment´s model. Our objective is to optimize search performance, that is, to minimize the (expected) time needed to find the target, in the context of probabilistic search. We first analyze two different methods to generate random connected graphs, then evaluate a number of methods to augment a graph by means of the algebraic connectivity of the graph and its associated (Fiedler) eigenvector. The relationship between the graph topology and the performance of the search is highlighted, including a comparative evaluation of different search strategies employed by the mobile searcher. Extensive simulation studies and resulting statistical and theoretical models show that adding a few wisely chosen edges to a sparse graph is sufficient to dramatically increase search performance. Further, we propose a novel method for incorporating prior information about the target´s likely location by defining a subgraph on which the presented approach is performed, resulting in even greater improvements in search performance.