- 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

Information mobility in complex networks

Ernesto Estrada*

  • Department of Physics, Department of Mathematics, and Institute of Complex Systems, University of Strathclyde, Glasgow G1 1XH, United Kingdom

  • *ernesto.estrada@strath.ac.uk
PDF

Phys. Rev. E 80, 026104 – Published 5 August, 2009

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

Abstract

The concept of information mobility in complex networks is introduced on the basis of a stochastic process taking place in the network. The transition matrix for this process represents the probability that the information arising at a given node is transferred to a target one. We use the fractional powers of this transition matrix to investigate the stochastic process at fractional time intervals. The mobility coefficient is then introduced on the basis of the trace of these fractional powers of the stochastic matrix. The fractional time at which a network diffuses 50% of the information contained in its nodes (1/k50) is also introduced. We then show that the scale-free random networks display a better spread of information than the non-scale-free ones. We study 38 real-world networks and analyze their performance in spreading information from their nodes. We find that some real-world networks perform even better than the scale-free networks with the same average degree and we point out some of the structural parameters that make this possible.

View figure in article

Article Text

References (77)

  1. S. M. Lipset and R. Bendix, Social Mobility in Industrial Society (Transaction Publications, New Jersey, 1991).
  2. B. R. Schiller, Am. Econ. Rev. 67, 926 (1977).
  3. A. F. Shorrocks, Economica 50, 3 (1983).
  4. S. S. Kuznets, Modern Economic Growth: Rate, Structure and Spread (Yale University Press, New Haven, CT, 1966).
  5. N. Ding, N. Xi, and Y. Wang, Physica A 367, 415 (2006).
  6. J. Geweke, R. C. Marshall, and G. A. Zarkin, Econometrica 54, 1407 (1986).
  7. A. F. Shorrocks, Econometrica 46, 1013 (1978).
  8. U. Cantner and J. J. Krüger, Rev. Ind. Organ. 24, 267 (2004).
  9. F. V. Waugh and M. E. Abel, J. Am. Stat. Assoc. 62, 1018 (1967).
  10. R. B. Israel, J. S. Rosenthal, and J. Z. Wei, Math. Finance 11, 245 (2001).
  11. R. A. Jarrow, D. Lando, and S. M. Turnbull, Rev. Financ. Stud. 10, 481 (1997).
  12. Q.-M. He and E. Gunn, J. Syst. Sci. Syst. Eng. 12, 210 (2003).
  13. T. Charitos, P. R. de Waal, and L. C. van der Gaag, Stat. Med. 27, 905 (2008).
  14. N. J. Higham and L. Lin, On pth roots of stochastic matrices, http://eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf
  15. B. Singer and S. Spilerman, AJS 82, 1 (1976).
  16. A. Kreinin and M. Sidelnikova, Algor. Res. Quat. 4, 23 (2001).
  17. N. L. Biggs, Algebraic Graph Theory (Cambridge University Press, Cambridge, England, 1993).
  18. N. J. Higham, Function of Matrices: Theory and Computation (SIAM, Philadelphia, 2008).
  19. E. Estrada and J. A. Rodríguez-Velázquez, Phys. Rev. E 71, 056103 (2005).
  20. E. Estrada and N. Hatano, Phys. Rev. E 77, 036111 (2008).
  21. T. Dǒslić, Chem. Phys. Lett. 412, 336 (2005).
  22. E. Estrada, Proteomics 6, 35 (2006).
  23. A. Platzer, P. Perco, A. Lukas, and B. Mayer, BMC Bioinf. 8, 224 (2007).
  24. E. Zotenko, J. Mestre, D. P. O’Leary, and T. M. Przytycka, PLOS Comput. Biol. 4, e1000140 (2008).
  25. M. Jungsbluth, B. Burghardt, and A. K. Hartmann, Physica A 381, 444 (2007).
  26. V. V. Kerrenbroeck and E. Marinari, Phys. Rev. Lett. 101, 098701 (2008).
  27. L. Da Fontoura Costa, M. A. Rodrigues Tognetti, and F. Nascimento Silva, Physica A 387, 6201 (2008).
  28. D. H. Higham and J. Croft, J. R. Soc., Interface33, 318 (2009).
  29. J. A. de la Peña, I. Gutman, and J. Rada, Linear Algebr. Appl. 427, 70 (2007).
  30. I. Gutman and A. Graovac, Chem. Phys. Lett. 436, 294 (2007).
  31. Y. Ginosar, I. Gutman, T. Mansour, and M. Schork, Chem. Phys. Lett. 454, 145 (2008).
  32. R. Carbó-Dorca, J. Math. Chem. 44, 373 (2008).
  33. M. Robbiano, R. Jimenez, and L. Medina, MATCH 61, 369 (2009).
  34. R. Norris, Markov Chains (Cambridge University Press, Cambridge, England, 1997).
  35. D. H. McLain, Comput. J. 17, 318 (1974).
  36. STATISTICA 6.0., StatSoft Inc., 2002.
  37. D. A. Bini, N. J. Higham, and B. Meini, Linear Algebr. Appl. 39, 349 (2005).
  38. P. Erdős and A. Rényi, Publ. Math. (Debrecen) 6, 290 (1959).
  39. A.-L. Barabási and R. Albert, Science 286, 509 (1999).
  40. Roget’s Thesaurus of English Words and Phrases, Project Gutenberg, 2002, http://gutenberg.net/etext/22
  41. ODLIS, Online Dictionary of Library and Information Science, 2002, http://vax.wcsu.edu/library/odlis.html
  42. B. Jones, Computational Geometry Database, 2002, http://compgeom.cs.edu/~jeffe/compgeom/biblios.html
  43. G. F. Davis, M. Yoo, and W. E. Baker, Strat. Org. 1, 301 (2003).
  44. Data for this project were provided in part by NIH Grants No. DA12831 and No. HD41877; those interested in obtaining a copy of these data should contact James Moody (moody.77@sociology.osu.edu).
  45. W. Zachary, J. Anthropol. Res. 33, 452 (1977).
  46. L. D. Zeleny, Sociometry 13, 314 (1950).
  47. http://vlado.fmf.uni-lj.si/pub/networks/data/Ucinet/UciData.htm
  48. J. J. Potterat, L. Philips-Plummer, S. Q. Muth, R. B. Rothenberg, D. E. Woodhouse, T. S. Maldonado-Long, H. P. Zimmerman, and J. B. Muth, Sex Transm. Infect. 78, i52 (2002).
  49. P. G. Lind, M. C. González, and H. J. Herrmann, Phys. Rev. E 72, 056127 (2005).
  50. V. Batagelj and A. Mrvar, Graph Drawing Contest, 2001, http://vlado.fmf.uni-lj.si/pub/GD/GD01.htm
  51. N. P. Hummon, P. Doreian, and L. C. Freeman, Knowledge 11, 459 (1990).
  52. W. de Nooy, A. Mrvar, and V. Batagelj, Exploratory Social Network Analysis with Pajek (Cambridge University Press, Cambridge, England, 2004), Chap. 11.
  53. Taken from http://vlado.fmf.uni-lj.si/pub/networks/data/default.htm as collected from the Garfield’s collection of citation network datasets (http://www.garfield.library.upenn.edu/histcomp/index.html).
  54. Taken from http://vlado.fmf.uni-lj.si/pub/networks/data/default.htm as collected from North American Transportation Atlas Data (NORTAD) (http://www.bts.gov/publications/north_american_transportation_atlas_data/).
  55. M. Faloutsos, P. Faloutsos, and C. Faloutsos, Comput. Commun. Rev. 29, 251 (1999).
  56. COSIN database, http://www.cosin.org
  57. R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Sheffer, and U. Alon, Science 303, 1538 (2004).
  58. D. Bu, Y. Zhao, L. Cai, H. Xue, X. Zhu, H. Lu, J. Zhang, S. Sun, L. Ling, N. Zhang, G. Li, and R. Chen, Nucleic Acids Res. 31, 2443 (2003).
  59. J.-C. Rain et al., Nature (London) 409, 211 (2001).
  60. M.-F. Noirot-Gros, E. Dervyn, L. J. Wu, P. Mervelet, J. Errington, S. D. Ehrlich, and P. Noirot, Proc. Natl. Acad. Sci. U.S.A. 99, 8342 (2002).
  61. M. Motz, I. Kober, C. Girardot, E. Loeser, U. Bauer, M. Albers, G. Moeckel, E. Minch, H. Voss, C. Kilger, and M. Koegl, J. Biol. Chem. 277, 16179 (2002).
  62. D. J. LaCount et al., Nature (London) 438, 103 (2005).
  63. J.-F. Rual et al., Nature (London) 437, 1173 (2005).
  64. S. Shen-Orr, R. Milo, S. Mangan, and U. Alon, Nat. Genet. 31, 64 (2002).
  65. R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Science 298, 824 (2002).
  66. J. White, E. Southgate, J. Thompson, and S. Brenner, Philos. Trans. R. Soc. London, Ser. B 314, 1 (1986).
  67. N. D. Martinez, B. A. Hawkins, H. A. Dawah, and B. P. Feifarek, Ecology 80, 1044 (1999).
  68. J. Memmott, N. D. Martinez, and J. E. Cohen, J. Anim. Ecol. 69, 1 (2000).
  69. C. Townsend, R. M. Thompson, A. R. McIntosh, C. Kilroy, E. Edwards, and M. R. Scarsbrook, Ecol. Lett. 1, 200 (1998).
  70. R. R. Christian and J. J. Luczkovich, Ecol. Modell. 117, 99 (1999).
  71. P. H. Warren, Oikos 55, 299 (1989).
  72. P. Yodzis, Ecology 81, 261 (2000).
  73. S. Opitz, ICLARM Technical Report No. 43, Manila, Philippines, 1996 (unpublished).
  74. E. Estrada, EPL 73, 649 (2006).
  75. E. Estrada, Eur. Phys. J. B 52, 563 (2006).
  76. E. Estrada, Phys. Rev. E 75, 016103 (2007).
  77. www.maths.manchester.ac.uk/~higham/mftoolbox.

Outline

Information

Phys. Rev. E 80, 026104– Published 5 August, 2009
  • Received 3 April 2009

© 2009 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation