  This research paper addresses the stability of search algorithms in complex
networks when dealing with incomplete information or uncertainty. We propose a
theoretical model to investigate whether a global search algorithm with
incomplete prior information can be outperformed by a stochastic greedy search
on average. The model incorporates random variables to perturb edge weights in
the graph, thus capturing the uncertainty of available information. Our
findings indicate that some graphs and uncertainty model parameters exist where
the global search algorithm fails under uncertainty conditions, while the
random greedy search performs better. We derive a critical curve that separates
stable from unstable graphs for global search with incomplete information.
Interestingly, the critical curve's behavior changes from monotonic to
bell-shaped depending on the uncertainty parameters. We test our proposed model
through numerical simulations on various synthetic and real-world graphs with
different structures. Our results offer insights into the design and
optimization of search algorithms for network-based applications, such as
communication networks, social networks, and biological networks. We also
discuss the study of memory and associative learning in miniature insects,
highlighting the potential of efficient search and walking strategies for small
robots or devices that operate in a limited area in space.
