Distinct nodes visited by random walkers on scale-free networks

Aanjaneya Kumar, Yagyik Goswami and M.S. Santhanam

Physica A: Statistical Mechanics and its Applications, 2019, vol. 532, issue C

Abstract: Random walks on discrete lattices are fundamental models that form the basis for our understanding of transport and diffusion processes. For a single random walker on complex networks, many properties such as the mean first passage time and cover time are known. However, many recent applications involving search engines and recommender systems involve multiple random walkers on complex networks. In this work, based on numerical simulations, we show that the fraction of nodes of scale-free network not visited by W random walkers in time t has a stretched exponential form independent of the number of walkers and the size of the network. This leads to a power-law relation between nodes not visited by W walkers and by 1 walker within time t. Thus the problem of finding the distinct nodes visited by W walkers, effectively, can be reduced to that of a single walker. The robustness of the results is demonstrated by verifying them on four different real-world networks that approximately display scale-free structure.

Keywords: Random walk; Complex Networks (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437119311045
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:532:y:2019:i:c:s0378437119311045

DOI: 10.1016/j.physa.2019.121875

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 ().