Detecting unknown paths on complex networks through random walks

Shao-Ping Wang and Wen-Jiang Pei

Physica A: Statistical Mechanics and its Applications, 2009, vol. 388, issue 4, 514-522

Abstract: 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.

Keywords: Random walk; Complex networks; Path; Search; Hitting times (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437108008649
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:388:y:2009:i:4:p:514-522

DOI: 10.1016/j.physa.2008.10.021

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().