- 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

Exact analytical solution of irreversible binary dynamics on networks

Edward Laurence1,*, Jean-Gabriel Young1, Sergey Melnik2, and Louis J. Dubé1,†

  • 1Département de Physique, de Génie Physique, et d'Optique, Université Laval, Québec (Québec), Canada G1V 0A6
  • 2MACSI, Department of Mathematics & Statistics, University of Limerick, Limerick, V94 T9PX, Ireland

  • *edward.laurence.1@ulaval.ca
  • †ljd@phy.ulaval.ca
PDF

Phys. Rev. E 97, 032302 – Published 2 March, 2018

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

Abstract

In binary cascade dynamics, the nodes of a graph are in one of two possible states (inactive, active), and nodes in the inactive state make an irreversible transition to the active state, as soon as their precursors satisfy a predetermined condition. We introduce a set of recursive equations to compute the probability of reaching any final state, given an initial state, and a specification of the transition probability function of each node. Because the naive recursive approach for solving these equations takes factorial time in the number of nodes, we also introduce an accelerated algorithm, built around a breath-first search procedure. This algorithm solves the equations as efficiently as possible in exponential time.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (30)

  1. J. P. Gleeson, Phys. Rev. E 77, 046117 (2008).
  2. S. R. Broadbent and J. M. Hammersley, in Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 53 (Cambridge University Press, Cambridge, UK, 1957), pp. 629–641.
  3. D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. Lett. 85, 5468 (2000).
  4. D. J. Watts, Proc. Natl. Acad. Sci. USA 99, 5766 (2002).
  5. M. E. J. Newman, Phys. Rev. E 66, 016128 (2002).
  6. L. Meyers, Bull. Amer. Math. Soc. 44, 63 (2007).
  7. A. G. Haldane and R. M. May, Nature 469, 351 (2011).
  8. D. W. Zhou, D. D. Mowrey, P. Tang, and Y. Xu, Phys. Rev. Lett. 115, 108103 (2015).
  9. M. Kaiser, M. Görner, and C. C. Hilgetag, New J. Phys. 9, 110 (2007).
  10. M. Kaiser and C. C. Hilgetag, Front. Neuroinform. 4, 1662 (2010).
  11. M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. E. 64, 026118 (2001).
  12. M. Molloy and B. Reed, Random Struc. Algor. 6, 161 (1995).
  13. M. Molloy and B. Reed, Comb. Probab. Comput. 7, 295 (1998).
  14. H. Wilf, Generatingfunctionology (Academic Press, New York, 1990).
  15. J. P. Gleeson, Phys. Rev. X 3, 021004 (2013).
  16. S. Melnik, M. A. Porter, P. J. Mucha, and J. P. Gleeson, Chaos 24, 023106 (2014).
  17. M. Shrestha and C. Moore, Phys. Rev. E 89, 022805 (2014).
  18. B. Karrer, M. E. J. Newman, and L. Zdeborová, Phys. Rev. Lett. 113, 208702 (2014).
  19. S. Melnik, A. Hackett, M. A. Porter, P. J. Mucha, and J. P. Gleeson, Phys. Rev. E 83, 036112 (2011).
  20. A. Y. Lokhov, M. Mézard, and L. Zdeborová, Phys. Rev. E 91, 012811 (2015).
  21. A. Hackett, S. Melnik, and J. P. Gleeson, Phys. Rev. E 83, 056107 (2011).
  22. A. Hackett and J. P. Gleeson, Phys. Rev. E 87, 062801 (2013).
  23. A. Allard, L. Hébert-Dufresne, P.-A. Noël, V. Marceau, and L. J. Dubé, J. Phys. A 45, 405005 (2012).
  24. A. Allard, L. Hébert-Dufresne, J.-G. Young, and L. J. Dubé, Phys. Rev. E. 92, 062807 (2015).
  25. B. Karrer and M. E. J. Newman, Phys. Rev. E. 82, 066118 (2010).
  26. A. Allard, L. Hébert-Dufresne, P.-A. Noël, V. Marceau, and L. J. Dubé, Europhys. Lett. 98, 16001 (2012).
  27. J. Adler and A. Aharony, J. Phys. A: Math. Gen. 21, 1387 (1988).
  28. J. C. Miller, Phys. Rev. E 94, 032313 (2016).
  29. P. Holme, Phys. Rev. E 96, 062305 (2017).
  30. J. P. Gleeson and M. A. Porter, arXiv:1703.08046 (2017).

Outline

Information

Phys. Rev. E 97, 032302– Published 2 March, 2018
  • Received 7 November 2017
Crossmark - Check for updates button

©2018 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation