Detecting unknown paths on complex networks through random walks

In this article, we investigate the problem of detecting unknown paths on complex networks through random walks. To detect a given path on a network a random walker should pass through the path from its initial node to its terminal node in turn. We calculate probability ϕ(t) that a random walker detects a given path on a connected network in t steps when it starts out from source node s. We propose an iteration formula for calculating ϕ(t). Generating function of ϕ(t) is also derived. Major factors affecting ϕ(t), such as walking time t, path length l, starting point of the walker, structure of the path, and topological structure of the underlying network are further discussed. Among these factors, two most outstanding ones are walking time t and path length l. On the one hand, ϕ(t) increases as t increases, and ϕ(∞)=1, which shows that the longer the walking time, the higher the chance of detecting a given path, and the walker will discover the path sooner or later so long as it keeps wandering on the network. On the other hand, ϕ(t) drops substantially as path length l increases, which shows that the longer the path, the lower the chance for the walker to find it in a given time. Apart from path length, path structure also has obvious effect on ϕ(t). Starting point of the walker has only minor influence on ϕ(t), but topological structure of the underlying network has strong influence on ϕ(t). Simulations confirm our analytic results.