- 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

Random walks on temporal networks

Michele Starnini1, Andrea Baronchelli2, Alain Barrat3,4, and Romualdo Pastor-Satorras1

  • 1Departament de Física i Enginyeria Nuclear, Universitat Politècnica de Catalunya, Campus Nord B4, E-08034 Barcelona, Spain
  • 2Department of Physics, College of Computer and Information Sciences, Bouvé College of Health Sciences, Northeastern University, Boston, Massachusetts 02120, USA
  • 3Centre de Physique Théorique, Aix-Marseille Univ, CNRS UMR 7332, Univ Sud Toulon Var, F-13288 Marseille cedex 9, France
  • 4Data Science Laboratory, ISI Foundation, I-Torino, Italy

PDF

Phys. Rev. E 85, 056115 – Published 18 May, 2012

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

Abstract

Many natural and artificial networks evolve in time. Nodes and connections appear and disappear at various time scales, and their dynamics has profound consequences for any processes in which they are involved. The first empirical analysis of the temporal patterns characterizing dynamic networks are still recent, so that many questions remain open. Here, we study how random walks, as a paradigm of dynamical processes, unfold on temporally evolving networks. To this aim, we use empirical dynamical networks of contacts between individuals, and characterize the fundamental quantities that impact any general process taking place upon them. Furthermore, we introduce different randomizing strategies that allow us to single out the role of the different properties of the empirical networks. We show that the random walk exploration is slower on temporal networks than it is on the aggregate projected network, even when the time is properly rescaled. In particular, we point out that a fundamental role is played by the temporal correlations between consecutive contacts present in the data. Finally, we address the consequences of the intrinsically limited duration of many real world dynamical networks. Considering the fundamental prototypical role of the random walk process, we believe that these results could help to shed light on the behavior of more complex dynamics on temporally evolving networks.

View figure in article

Article Text

References (52)

  1. P. Holme and J. Saramäki, e-print arXiv:1108.1780.
  2. S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications (Cambridge University Press, Cambridge, 1994).
  3. M. E. J. Newman, Proc. Natl. Acad. Sci. USA 98, 404 (2001).
  4. A.-L. Barabási and R. Albert, Science 286, 509 (1999).
  5. A. Barrat, M. Barthélemy, and A. Vespignani, Dynamical Processes on Complex Networks (Cambridge University Press, Cambridge, 2008).
  6. P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot, in WDTN’05: Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking (ACM, New York, 2005), pp. 244–251.
  7. P. Holme, Phys. Rev. E 71, 046119 (2005).
  8. J.-P. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, and A.-L. Barabási, Proc. Natl. Acad. Sci. 104, 7332 (2007).
  9. A. Gautreau, A. Barrat, and M. Barthélemy, Proc. Natl. Acad. Sci. 106, 8847 (2009).
  10. C. Cattuto, W. Van den Broeck, A. Barrat, V. Colizza, J.-F. Pinton, and A. Vespignani, PLoS ONE 5, e11596 (2010).
  11. J. Tang, S. Scellato, M. Musolesi, C. Mascolo, and V. Latora, Phys. Rev. E 81, 055101 (2010).
  12. P. Bajardi, A. Barrat, F. Natale, L. Savini, and V. Colizza, PLoS ONE 6, e19869 (2011).
  13. J. Stehlé, N. Voirin, A. Barrat, C. Cattuto, V. Colizza, L. Isella, C. Régis, J.-F. Pinton, N. Khanafer, W. Van den Broeck, and P. Vanhems, BMC Medicine 9 (2011).
  14. G. Miritello, E. Moro, and R. Lara, Phys. Rev. E 83, 045102 (2011).
  15. M. Karsai, M. Kivelä, R. K. Pan, K. Kaski, J. Kertész, A.-L. Barabási, and J. Saramäki, Phys. Rev. E 83, 025102 (2011).
  16. A. Scherrer, P. Borgnat, E. Fleury, J.-L. Guillaume, and C. Robardet, Comp. Net. 52, 2842 (2008).
  17. S. A. Hill and D. Braha, Phys. Rev. E 82, 046105 (2010).
  18. J. Stehlé, A. Barrat, and G. Bianconi, Phys. Rev. E 81, 035101 (2010).
  19. K. Zhao, J. Stehlé, G. Bianconi, and A. Barrat, Phys. Rev. E 83, 056109 (2011).
  20. L. E. C. Rocha, F. Liljeros, and P. Holme, PLoS Comput. Biol. 7, e1001109 (2011).
  21. L. Isella, J. Stehlé, A. Barrat, C. Cattuto, J.-F. Pinton, and W. V. den Broeck, J. Theor. Biol. 271, 166 (2011).
  22. M. Kivela, R. Kumar Pan, K. Kaski, J. Kertesz, J. Saramaki, and M. Karsai, e-print arXiv:1112.4312v1.
  23. N. Fujiwara, J. Kurths, and A. Díaz-Guilera, Phys. Rev. E 83, 025101 (2011).
  24. R. Parshani, M. Dickison, R. Cohen, H. E. Stanley, and S. Havlin, Europhys. Lett. 90, 38004 (2010).
  25. A. Baronchelli and A. Díaz-Guilera, Phys. Rev. E 85, 016113 (2012).
  26. G. H. Weiss, Aspects and Applications of the Random Walk (North-Holland Publishing, Amsterdam, 1994).
  27. B. Hughes, Random Walks and Random Environments (Clarendon Press, Oxford, 1995).
  28. L. Lovász, in Combinatorics, Paul Erdös is Eighty (János Bolyai Mathematical Society, Budapest, 1996), p. 353.
  29. L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman, Phys. Rev. E 64, 046135 (2001).
  30. Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, in Proceedings of the 16th International Conference on Supercomputing (ACM Press, New York, 2002), pp. 84–95.
  31. [http://www.sociopatterns.org/].
  32. A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani, Proc. Natl. Acad. Sci. USA 101, 3747 (2004).
  33. J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).
  34. A.-C. Wu, X.-J. Xu, Z.-X. Wu, and Y.-H. Wang, Chin. Phys. Lett. 24, 577 (2007).
  35. D. Stauffer and M. Sahimi, Phys. Rev. E 72, 046128 (2005).
  36. E. Almaas, R. V. Kulkarni, and D. Stroud, Phys. Rev. E 68, 056105 (2003).
  37. M. E. J. Newman, Networks: An introduction (Oxford University Press, Oxford, 2010).
  38. J. Stehlé, N. Voirin, A. Barrat, C. Cattuto, L. Isella, J.-F. Pinton, M. Quaggiotto, W. Van den Broeck, C. Régis, B. Lina, and P. Vanhems, PLoS ONE 6, e23176 (2011).
  39. V. Kostakos, Physica A: Statistical Mechanics and its Applications 388, 1007 (2009).
  40. V. Nicosia, J. Tang, M. Musolesi, G. Russo, C. Mascolo, and V. Latora, Chaos 22, 023101 (2012).
  41. A. Barabási, Nature (London) 435, 207 (2005).
  42. W. V. den Broeck, C. Cattuto, A. Barrat, M. Szomsor, G. Correndo, and H. Alani, in Proceedings of the 8th Annual IEEE International Conference on Pervasive Computing and Communications (IEEE, Washington, DC, 2010), p. 226.
  43. G. Kossinets, J. Kleinberg, and D. Watts, in Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM, New York, 2008).
  44. R. K. Pan and J. Saramäki, Phys. Rev. E 84, 016105 (2011).
  45. A. Baronchelli and R. Pastor-Satorras, Phys. Rev. E 82, 011111 (2010).
  46. A. Baronchelli, M. Catanzaro, and R. Pastor-Satorras, Phys. Rev. E 78, 011114 (2008).
  47. A. Baronchelli and V. Loreto, Phys. Rev. E 73, 026103 (2006).
  48. P. Pons and M. Latapy, in Proceedings of the 20th International Symposium on Computer and Information Sciences (ISCIS’05), Lecture Notes in Computer Science, Vol. 3733 (Springer, Istanbul, 2005), pp. 284–293.
  49. D. Braha and Y. Bar-Yam, in Adaptive Networks, Understanding Complex Systems, Vol. 51, edited by T. Gross and H. Sayama (Springer, Berlin/Heidelberg, 2009), pp. 39–50.
  50. J. Tang, M. Musolesi, C. Mascolo, V. Latora, and V. Nicosia, in Proceedings of the 3rd Workshop on Social Network Systems, SNS’10 (ACM, New York, 2010), pp. 3:1–3:6.
  51. K. Lerman, R. Ghosh, and J. H. Kang, in Proceedings of the Eighth Workshop on Mining and Learning with Graphs, MLG’10 (ACM, New York, 2010), pp. 70–77.
  52. M. J. Newman, Social Networks 27, 39 (2005).

Outline

Information

Phys. Rev. E 85, 056115– Published 18 May, 2012
  • Received 12 March 2012

©2012 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation