American Institute of Mathematical Sciences

Advanced
December  2011, 4(6): 1533-1541. doi: 10.3934/dcdss.2011.4.1533

Update sequence stability in graph dynamical systems

Matthew Macauley 1, and  Henning S. Mortveit 2,

1. 

Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, United States
2. 

Department of Mathematics, NDSSL, Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, VA 24061, United States

Received  May 2009 Revised  November 2009 Published  December 2010

In this article, we study finite dynamical systems defined over graphs, where the functions are applied asynchronously. Our goal is to quantify and understand stability of the dynamics with respect to the update sequence, and to relate this to structural properties of the graph. We introduce and analyze three different notions of update sequence stability, each capturing different aspects of the dynamics. When compared to each other, these stability concepts yield different conclusions regarding the relationship between stability and graph structure, painting a more complete picture of update sequence stability.
Keywords: graph dynamical systems, update sequence., Asychronous update schedule, stability.
Mathematics Subject Classification: Primary: 93D99, 37B99; Secondary: 05C9.
Citation: Matthew Macauley, Henning S. Mortveit. Update sequence stability in graph dynamical systems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1533-1541. doi: 10.3934/dcdss.2011.4.1533
References:
[1]

C. L. Barrett, H. H. Hunt, M. V. Marathe, S. S. Ravi, D. Rosenkrantz, R. Stearns and P. Tosic, Gardens of Eden and fixed point in sequential dynamical systems, DM-CCG 2001, 95-110.  Google Scholar

[2]

C. L. Barrett, H. S. Mortveit and C. M. Reidys, Elements of a theory of simulation III: Equivalence of SDS, Appl. Math. Comput., 122 (2001), 325-340. doi: 10.1016/S0096-3003(00)00042-4.  Google Scholar

[3]

C. L. Barrett, H. S. Mortveit and C. M. Reidys, Elements of a theory of simulation IV: Fixed points, invertibility and equivalence, Appl. Math. Comput., 134 (2003), 153-172. doi: 10.1016/S0096-3003(01)00277-6.  Google Scholar

[4]

C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, Predecessor and permutation existence problems for sequential dynamical systems, DMTCS 2003, 69-80. Google Scholar

[5]

A. Björner and F. Brenti, "Combinatorics of Coxeter Groups,'' Springer-Verlag, New York, 2005. Google Scholar

[6]

B. Bollobàs, "Random Graphs,'' Cambridge University Press, 2001. Google Scholar

[7]

R. Laubenbacher E. Sontag, A. Veliz-Cuba and A. Salam Jarrah, The effect of negative feedback loops on the dynamics of Boolean networks, Biophys. J., 95 (2008), 518-526. doi: 10.1529/biophysj.107.125021.  Google Scholar

[8]

D. L. Vertigan F. Jaeger and D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990), 35-53. doi: 10.1017/S0305004100068936.  Google Scholar

[9]

A. Å. Hansson, H. S. Mortveit and C. M. Reidys, On asynchronous cellular automata, Adv. Complex Systems, 8 (2005), no. 4, 521-538.  Google Scholar

[10]

U. Karaoz, T. M. Murali, S. Letovsky, Y. Zheng, C. Ding, C. R. Cantor and S. Kasif, Whole-genome annotation by using evidence integration in functional-linkage networks, Proc. Nat. Acad. Sci., 101 (2004), 2888-2893. doi: 10.1073/pnas.0307326101.  Google Scholar

[11]

W. O. Kermack and A. G. McKendrick, A contribution to the mathematical theory of epidemics, Proc. Royal Soc. London A, 115 (1927), 700-721. doi: 10.1098/rspa.1927.0118.  Google Scholar

[12]

V. S. A. Kumar, M. Macauley and H. S. Mortveit, Limit set reachability in asynchronous graph dynamical systems, RP 2009, 217-232. Google Scholar

[13]

M. Macauley, J. McCammond and H. S. Mortveit, Dynamics groups of asynchronous cellular automata, J. Algebraic Combinat, 33 (2011), 11-35. doi: 10.1007/s10801-010-0231-y.  Google Scholar

[14]

M. Macauley, J. McCammond and H. S. Mortveit, Order independence in asynchronous cellular automata, J. Cell. Autom., 3 (2008), 37-56.  Google Scholar

[15]

M. Macauley and H. S. Mortveit, On enumeration of conjugacy classes of Coxeter elements, Proc. Amer. Math. Soc., 136 (2008), 4157-4165. doi: 10.1090/S0002-9939-08-09543-9.  Google Scholar

[16]

M. Macauley and H. S. Mortveit, Cycle equivalence of graph dynamical systems, Nonlinearity, 22 (2009), 421-436. doi: 10.1088/0951-7715/22/2/010.  Google Scholar

[17]

H. S. Mortveit and C. M. Reidys, "An Introduction to Sequential Dynamical Systems," Universitext, Springer Verlag, 2007. Google Scholar

[18]

C. M. Reidys, Sequential dynamical systems over words, Ann. Comb., 10 (2006), 481-498. doi: 10.1007/s00026-006-0301-y.  Google Scholar

[19]

C. M. Reidys, Combinatorics of sequential dynamical systems, Discrete Math., 308 (2007), 514-528. doi: 10.1016/j.disc.2007.03.033.  Google Scholar

[20]

I. Shmulevich, E. R. Dougherty and W. Zhang, From Boolean to probabilistic Boolean networks as models of genetic regulatory networks, Proc. IEEE, 90 (2002), 1778-1792. doi: 10.1109/JPROC.2002.804686.  Google Scholar

[21]

S. Wolfram, "Theory and Applications of Cellular Automata," Adv. Ser. Complex Systems, 1, World Scientific Publishing Company, 1986.  Google Scholar

show all references

References:
[1]

C. L. Barrett, H. H. Hunt, M. V. Marathe, S. S. Ravi, D. Rosenkrantz, R. Stearns and P. Tosic, Gardens of Eden and fixed point in sequential dynamical systems, DM-CCG 2001, 95-110.  Google Scholar

[2]

C. L. Barrett, H. S. Mortveit and C. M. Reidys, Elements of a theory of simulation III: Equivalence of SDS, Appl. Math. Comput., 122 (2001), 325-340. doi: 10.1016/S0096-3003(00)00042-4.  Google Scholar

[3]

C. L. Barrett, H. S. Mortveit and C. M. Reidys, Elements of a theory of simulation IV: Fixed points, invertibility and equivalence, Appl. Math. Comput., 134 (2003), 153-172. doi: 10.1016/S0096-3003(01)00277-6.  Google Scholar

[4]

C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, Predecessor and permutation existence problems for sequential dynamical systems, DMTCS 2003, 69-80. Google Scholar

[5]

A. Björner and F. Brenti, "Combinatorics of Coxeter Groups,'' Springer-Verlag, New York, 2005. Google Scholar

[6]

B. Bollobàs, "Random Graphs,'' Cambridge University Press, 2001. Google Scholar

[7]

R. Laubenbacher E. Sontag, A. Veliz-Cuba and A. Salam Jarrah, The effect of negative feedback loops on the dynamics of Boolean networks, Biophys. J., 95 (2008), 518-526. doi: 10.1529/biophysj.107.125021.  Google Scholar

[8]

D. L. Vertigan F. Jaeger and D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990), 35-53. doi: 10.1017/S0305004100068936.  Google Scholar

[9]

A. Å. Hansson, H. S. Mortveit and C. M. Reidys, On asynchronous cellular automata, Adv. Complex Systems, 8 (2005), no. 4, 521-538.  Google Scholar

[10]

U. Karaoz, T. M. Murali, S. Letovsky, Y. Zheng, C. Ding, C. R. Cantor and S. Kasif, Whole-genome annotation by using evidence integration in functional-linkage networks, Proc. Nat. Acad. Sci., 101 (2004), 2888-2893. doi: 10.1073/pnas.0307326101.  Google Scholar

[11]

W. O. Kermack and A. G. McKendrick, A contribution to the mathematical theory of epidemics, Proc. Royal Soc. London A, 115 (1927), 700-721. doi: 10.1098/rspa.1927.0118.  Google Scholar

[12]

V. S. A. Kumar, M. Macauley and H. S. Mortveit, Limit set reachability in asynchronous graph dynamical systems, RP 2009, 217-232. Google Scholar

[13]

M. Macauley, J. McCammond and H. S. Mortveit, Dynamics groups of asynchronous cellular automata, J. Algebraic Combinat, 33 (2011), 11-35. doi: 10.1007/s10801-010-0231-y.  Google Scholar

[14]

M. Macauley, J. McCammond and H. S. Mortveit, Order independence in asynchronous cellular automata, J. Cell. Autom., 3 (2008), 37-56.  Google Scholar

[15]

M. Macauley and H. S. Mortveit, On enumeration of conjugacy classes of Coxeter elements, Proc. Amer. Math. Soc., 136 (2008), 4157-4165. doi: 10.1090/S0002-9939-08-09543-9.  Google Scholar

[16]

M. Macauley and H. S. Mortveit, Cycle equivalence of graph dynamical systems, Nonlinearity, 22 (2009), 421-436. doi: 10.1088/0951-7715/22/2/010.  Google Scholar

[17]

H. S. Mortveit and C. M. Reidys, "An Introduction to Sequential Dynamical Systems," Universitext, Springer Verlag, 2007. Google Scholar

[18]

C. M. Reidys, Sequential dynamical systems over words, Ann. Comb., 10 (2006), 481-498. doi: 10.1007/s00026-006-0301-y.  Google Scholar

[19]

C. M. Reidys, Combinatorics of sequential dynamical systems, Discrete Math., 308 (2007), 514-528. doi: 10.1016/j.disc.2007.03.033.  Google Scholar

[20]

I. Shmulevich, E. R. Dougherty and W. Zhang, From Boolean to probabilistic Boolean networks as models of genetic regulatory networks, Proc. IEEE, 90 (2002), 1778-1792. doi: 10.1109/JPROC.2002.804686.  Google Scholar

[21]

S. Wolfram, "Theory and Applications of Cellular Automata," Adv. Ser. Complex Systems, 1, World Scientific Publishing Company, 1986.  Google Scholar

[1]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381
[2]

Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial & Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038
[3]

Jakub Šotola. Relationship between Li-Yorke chaos and positive topological sequence entropy in nonautonomous dynamical systems. Discrete & Continuous Dynamical Systems, 2018, 38 (10) : 5119-5128. doi: 10.3934/dcds.2018225
[4]

Karl P. Hadeler. Quiescent phases and stability in discrete time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2015, 20 (1) : 129-152. doi: 10.3934/dcdsb.2015.20.129
[5]

S.Durga Bhavani, K. Viswanath. A general approach to stability and sensitivity in dynamical systems. Discrete & Continuous Dynamical Systems, 1998, 4 (1) : 131-140. doi: 10.3934/dcds.1998.4.131
[6]

Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discrete-time coupled systems with multi-diffusion by graph-theoretic approach and its application. Discrete & Continuous Dynamical Systems - B, 2016, 21 (1) : 253-269. doi: 10.3934/dcdsb.2016.21.253
[7]

Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261
[8]

Henri Schurz. Moment attractivity, stability and contractivity exponents of stochastic dynamical systems. Discrete & Continuous Dynamical Systems, 2001, 7 (3) : 487-515. doi: 10.3934/dcds.2001.7.487
[9]

Michael Schönlein. Asymptotic stability and smooth Lyapunov functions for a class of abstract dynamical systems. Discrete & Continuous Dynamical Systems, 2017, 37 (7) : 4053-4069. doi: 10.3934/dcds.2017172
[10]

J. Gwinner. On differential variational inequalities and projected dynamical systems - equivalence and a stability result. Conference Publications, 2007, 2007 (Special) : 467-476. doi: 10.3934/proc.2007.2007.467
[11]

Noriaki Kawaguchi. Topological stability and shadowing of zero-dimensional dynamical systems. Discrete & Continuous Dynamical Systems, 2019, 39 (5) : 2743-2761. doi: 10.3934/dcds.2019115
[12]

Alexandra Rodkina, Henri Schurz, Leonid Shaikhet. Almost sure stability of some stochastic dynamical systems with memory. Discrete & Continuous Dynamical Systems, 2008, 21 (2) : 571-593. doi: 10.3934/dcds.2008.21.571
[13]

Daniel Franco, Juan Perán, Juan Segura. Stability for one-dimensional discrete dynamical systems revisited. Discrete & Continuous Dynamical Systems - B, 2020, 25 (2) : 635-650. doi: 10.3934/dcdsb.2019258
[14]

Chun-Xiang Guo, Guo Qiang, Jin Mao-Zhu, Zhihan Lv. Dynamic systems based on preference graph and distance. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1139-1154. doi: 10.3934/dcdss.2015.8.1139
[15]

Mario Roy, Mariusz Urbański. Multifractal analysis for conformal graph directed Markov systems. Discrete & Continuous Dynamical Systems, 2009, 25 (2) : 627-650. doi: 10.3934/dcds.2009.25.627
[16]

Chunmei Zhang, Wenxue Li, Ke Wang. Graph-theoretic approach to stability of multi-group models with dispersal. Discrete & Continuous Dynamical Systems - B, 2015, 20 (1) : 259-280. doi: 10.3934/dcdsb.2015.20.259
[17]

Ken Shirakawa. Asymptotic stability for dynamical systems associated with the one-dimensional Frémond model of shape memory alloys. Conference Publications, 2003, 2003 (Special) : 798-808. doi: 10.3934/proc.2003.2003.798
[18]

Mario Roy. A new variation of Bowen's formula for graph directed Markov systems. Discrete & Continuous Dynamical Systems, 2012, 32 (7) : 2533-2551. doi: 10.3934/dcds.2012.32.2533
[19]

El Houcein El Abdalaoui, Sylvain Bonnot, Ali Messaoudi, Olivier Sester. On the Fibonacci complex dynamical systems. Discrete & Continuous Dynamical Systems, 2016, 36 (5) : 2449-2471. doi: 10.3934/dcds.2016.36.2449
[20]

Lianfa He, Hongwen Zheng, Yujun Zhu. Shadowing in random dynamical systems. Discrete & Continuous Dynamical Systems, 2005, 12 (2) : 355-362. doi: 10.3934/dcds.2005.12.355

2019 Impact Factor: 1.233

Tools

Metrics

  • PDF downloads (45)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences