- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Long-range navigation on complex networks using Lévy random walks

A. P. Riascos and José L. Mateos

  • Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 México, D.F., México

PDF

Phys. Rev. E 86, 056110 – Published 19 November, 2012

DOI: https://doi.org/10.1103/PhysRevE.86.056110

Abstract

We introduce a strategy of navigation in undirected networks, including regular, random, and complex networks, that is inspired by Lévy random walks, generalizing previous navigation rules. We obtained exact expressions for the stationary probability distribution, the occupation probability, the mean first passage time, and the average time to reach a node on the network. We found that the long-range navigation using the Lévy random walk strategy, compared with the normal random walk strategy, is more efficient at reducing the time to cover the network. The dynamical effect of using the Lévy walk strategy is to transform a large-world network into a small world. Our exact results provide a general framework that connects two important fields: Lévy navigation strategies and dynamics on complex networks.

View figure in article

Article Text

References (40)

  1. M. E. J. Newman, Networks: An Introduction (Oxford University Press, Oxford, 2010).
  2. A.-L. Barabási, Nat. Phys. 8, 14 (2012).
  3. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, Phys. Rep. 424, 175 (2006).
  4. A. Arenas, A. Dí-az-Guilera, J. Kurths, Y. Moreno, and C. Zhou, Phys. Rep. 469, 93 (2008).
  5. A. Barrat, M. Barthélemy, and A. Vespignani, Dynamical Processes on Complex Networks (Cambridge University Press, Cambridge, 2008).
  6. A. Vespignani, Nat. Phys. 8, 32 (2012).
  7. G. Ramos-Fernández, J. L. Mateos, O. Miramontes, G. Cocho, H. Larralde, and B. Ayala-Orozco, Behav. Ecol. Sociobiol. 55, 223 (2004).
  8. D. Boyer, G. Ramos-Fernández, O. Miramontes, J. L. Mateos, G. Cocho, H. Larralde, H. Ramos, and F. Rojas, Proc. R. Soc. B 273, 1743 (2006).
  9. D. Boyer, M. C. Crofoot, and P. D. Walsh, J. R. Soc. Interface 9, 842 (2012).
  10. D. Brockmann, L. Hufnagel, and T. Geisel, Nature (London) 439, 462 (2006).
  11. M. C. González, C. A. Hidalgo, and A.-L. Barabási, Nature (London) 453, 779 (2008).
  12. M. Boguñá, D. Krioukov, and K. C. Claffy, Nat. Phys. 5, 74 (2009).
  13. C. Song, T. Koren, P. Wang, and A.-L. Barabási, Nat. Phys. 6, 818 (2010).
  14. V. Belik, T. Geisel, and D. Brockmann, Phys. Rev. X 1, 011001 (2011).
  15. F. Simini, M. C. González, A. Maritan, and A.-L. Barabási, Nature (London) 484, 96 (2012).
  16. D. Lazer, A. Pentland, L. Adamic, S. Aral, et al. Science 323, 721 (2009).
  17. J. L. Iribarren and E. Moro, Phys. Rev. Lett. 103, 038702 (2009).
  18. M. Szell, R. Sinatra, G. Petri, S. Thurner, and V. Latora, Sci. Rep. 2, 457 (2012).
  19. S. Aral and D. Walker, Science 337, 337 (2012).
  20. P. Holme and J. Saramäki, Phys. Rep. 519, 97 (2012).
  21. J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).
  22. R. Metzler and J. Klafter, J. Phys. A 37, R161 (2004).
  23. M. F. Shlesinger, J. Phys. A 42, 434001 (2009); E. P. Raposo, S. V. Buldyrev, M. G. E. da Luz, G. M. Viswanathan, and H. E. Stanley, ibid. 42, 434003 (2009); R. Metzler, T. Koren, B. van den Broek, G. J. L. Wuite, and M. A. Lomholt, ibid. 42, 434005 (2009); G. Oshanin, K. Lindenberg, H. S. Wio, and S. Burlatsky, ibid. 42, 434008 (2009).
  24. G. M. Viswanathan, M. G. E. da Luz, E. P. Raposo, and H. E. Stanley, The Physics of Foraging (Cambridge University Press, New York, 2011).
  25. O. Bénichou, C. Loverdo, M. Moreau, and R. Voituriez, Rev. Mod. Phys. 83, 81 (2011).
  26. M. A. Lomholt, K. Tal, R. Metzler, and K. Joseph, Proc. Natl. Acad. Sci. USA 105, 11055 (2008).
  27. D. W. Sims et al., Nature (London) 451, 1098 (2008).
  28. M. de Jager, F. J. Weissing, P. M. J. Herman, B. A. Nolet, and J. van de Koppel, Science 332, 1551 (2011).
  29. C. Brown, L. Liebovitch, and R. Glendon, Hum. Ecol. 35, 129 (2007).
  30. I. Rhee, M. Shin, S. Hong, K. Lee, S. J. Kim, and S. Chong, IEEE/ACM Trans. Networking 19, 630 (2011).
  31. N. Scafetta, Chaos 21, 043106 (2011).
  32. F. Radicchi, A. Baronchelli, and L. A. N. Amaral, PLoS ONE 7, e29910 (2012).
  33. F. Radicchi and A. Baronchelli, Phys. Rev. E 85, 061121 (2012).
  34. S. Redner, A Guide to First-Passage Processes (Cambridge University Press, New York, 2001).
  35. B. D. Hughes, Random Walks and Random Environments, Vol. 1, Random Walks (Oxford University Press, New York, 1996).
  36. J. M. Kleinberg, Nature (London) 406, 845 (2000); S. Carmi, S. Carter, J. Sun, and D. ben-Avraham, Phys. Rev. Lett. 102, 238702 (2009); G. Li, S. D. S. Reis, A. A. Moreira, S. Havlin, H. E. Stanley, and J. S. Andrade, ibid. 104, 018701 (2010); Y. Hu, Y. Wang, D. Li, S. Havlin, and Z. Di, ibid. 106, 108701 (2011).
  37. If λN≠−1, Pi∞=limt→∞Pij(t); if λN=−1, the Markovian process is cyclic, and Pi∞ is interpreted as a temporal average of Pij(t) when t→∞.
  38. J. G. Kemeny and J. L. Snell, Finite Markov Chains (Van Nostrand, Princeton, NJ, 1960); Z. Zhang, A. Julaiti, B. Hou, H. Zhang, and G. Chen, Eur. Phys. J. B 84, 691 (2011); V. Tejedor, O. Bénichou, and R. Voituriez, Phys. Rev. E 80, 065104 (2009).
  39. N. G. van Kampen, Stochastic Processes in Physics and Chemistry (North Holland, Amsterdam, 1992).
  40. A.-L. Barabási and R. Albert, Science 286, 509 (1999).

Outline

Information

Phys. Rev. E 86, 056110– Published 19 November, 2012
  • Received 13 June 2012

©2012 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation