Mixing search on complex networks

Cun-Lai Pu and Wen-Jiang Pei

Physica A: Statistical Mechanics and its Applications, 2010, vol. 389, issue 3, 587-594

Abstract: In this article, we derive the first passage time (FPT) distribution and the mean first passage time (MFPT) of random walks from multiple sources on networks. On the basis of analysis and simulation, we find that the MFPT drops substantially when particle number increases at the first stage, and converges to the shortest distance between the sources and the destination when particle number tends to infinite. Given the fact that a Brownian particle from a high-degree node often needs a large number of steps to reach an expected low-degree node, which is the bottleneck for a single random walk, we propose a mixing search model to improve the efficiency of search processes by using random walks from multiple sources to continue the searches from high-degree nodes to destinations. We compare our model with the mixing navigation model proposed by Zhou on complex networks and find that our model converges much faster with lower hardware cost than Zhou’s model. Moreover, simulations on scale-free networks show that the search efficiency of our model is much higher than that of a single random walk, and comparable to that of multiple random walks which have much higher hardware cost than our model. Finally, we discuss the traffic cost of our model, and propose an absorption strategy for our model to recover the additional walkers in networks. Simulations indicate that this strategy reduces the traffic cost of our model effectively.

Keywords: Random walk; Complex networks; First passage time; Search (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437109008565
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:389:y:2010:i:3:p:587-594

DOI: 10.1016/j.physa.2009.10.007

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