Update sequence stability in graph dynamical systems

Previous Article
Conjectures for the existence of an idempotent in $\omega $-polynomial algebras
DCDS-S Home
This Issue
Next Article
Nongeneric bifurcations near heterodimensional cycles with inclination flip in $\mathbb{R}^4$

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

Abstract
Related Papers

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 and 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.
[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.
[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.
[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.
[5]	A. Björner and F. Brenti, "Combinatorics of Coxeter Groups,'' Springer-Verlag, New York, 2005.
[6]	B. Bollobàs, "Random Graphs,'' Cambridge University Press, 2001.
[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.
[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.
[9]	A. Å. Hansson, H. S. Mortveit and C. M. Reidys, On asynchronous cellular automata, Adv. Complex Systems, 8 (2005), no. 4, 521-538.
[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.
[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.
[12]	V. S. A. Kumar, M. Macauley and H. S. Mortveit, Limit set reachability in asynchronous graph dynamical systems, RP 2009, 217-232.
[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.
[14]	M. Macauley, J. McCammond and H. S. Mortveit, Order independence in asynchronous cellular automata, J. Cell. Autom., 3 (2008), 37-56.
[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.
[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.
[17]	H. S. Mortveit and C. M. Reidys, "An Introduction to Sequential Dynamical Systems," Universitext, Springer Verlag, 2007.
[18]	C. M. Reidys, Sequential dynamical systems over words, Ann. Comb., 10 (2006), 481-498. doi: 10.1007/s00026-006-0301-y.
[19]	C. M. Reidys, Combinatorics of sequential dynamical systems, Discrete Math., 308 (2007), 514-528. doi: 10.1016/j.disc.2007.03.033.
[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.
[21]	S. Wolfram, "Theory and Applications of Cellular Automata," Adv. Ser. Complex Systems, 1, World Scientific Publishing Company, 1986.

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.
[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.
[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.
[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.
[5]	A. Björner and F. Brenti, "Combinatorics of Coxeter Groups,'' Springer-Verlag, New York, 2005.
[6]	B. Bollobàs, "Random Graphs,'' Cambridge University Press, 2001.
[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.
[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.
[9]	A. Å. Hansson, H. S. Mortveit and C. M. Reidys, On asynchronous cellular automata, Adv. Complex Systems, 8 (2005), no. 4, 521-538.
[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.
[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.
[12]	V. S. A. Kumar, M. Macauley and H. S. Mortveit, Limit set reachability in asynchronous graph dynamical systems, RP 2009, 217-232.
[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.
[14]	M. Macauley, J. McCammond and H. S. Mortveit, Order independence in asynchronous cellular automata, J. Cell. Autom., 3 (2008), 37-56.
[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.
[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.
[17]	H. S. Mortveit and C. M. Reidys, "An Introduction to Sequential Dynamical Systems," Universitext, Springer Verlag, 2007.
[18]	C. M. Reidys, Sequential dynamical systems over words, Ann. Comb., 10 (2006), 481-498. doi: 10.1007/s00026-006-0301-y.
[19]	C. M. Reidys, Combinatorics of sequential dynamical systems, Discrete Math., 308 (2007), 514-528. doi: 10.1016/j.disc.2007.03.033.
[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.
[21]	S. Wolfram, "Theory and Applications of Cellular Automata," Adv. Ser. Complex Systems, 1, World Scientific Publishing Company, 1986.

[1]	Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial and 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 and Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038
[3]	Hong Seng Sim, Chuei Yee Chen, Wah June Leong, Jiao Li. Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021143
[4]	Jakub Šotola. Relationship between Li-Yorke chaos and positive topological sequence entropy in nonautonomous dynamical systems. Discrete and Continuous Dynamical Systems, 2018, 38 (10) : 5119-5128. doi: 10.3934/dcds.2018225
[5]	Karl P. Hadeler. Quiescent phases and stability in discrete time dynamical systems. Discrete and Continuous Dynamical Systems - B, 2015, 20 (1) : 129-152. doi: 10.3934/dcdsb.2015.20.129
[6]	S.Durga Bhavani, K. Viswanath. A general approach to stability and sensitivity in dynamical systems. Discrete and Continuous Dynamical Systems, 1998, 4 (1) : 131-140. doi: 10.3934/dcds.1998.4.131
[7]	Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discrete-time coupled systems with multi-diffusion by graph-theoretic approach and its application. Discrete and Continuous Dynamical Systems - B, 2016, 21 (1) : 253-269. doi: 10.3934/dcdsb.2016.21.253
[8]	Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete and Continuous Dynamical Systems, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261
[9]	Henri Schurz. Moment attractivity, stability and contractivity exponents of stochastic dynamical systems. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 487-515. doi: 10.3934/dcds.2001.7.487
[10]	Michael Schönlein. Asymptotic stability and smooth Lyapunov functions for a class of abstract dynamical systems. Discrete and Continuous Dynamical Systems, 2017, 37 (7) : 4053-4069. doi: 10.3934/dcds.2017172
[11]	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
[12]	Noriaki Kawaguchi. Topological stability and shadowing of zero-dimensional dynamical systems. Discrete and Continuous Dynamical Systems, 2019, 39 (5) : 2743-2761. doi: 10.3934/dcds.2019115
[13]	Alexandra Rodkina, Henri Schurz, Leonid Shaikhet. Almost sure stability of some stochastic dynamical systems with memory. Discrete and Continuous Dynamical Systems, 2008, 21 (2) : 571-593. doi: 10.3934/dcds.2008.21.571
[14]	Daniel Franco, Juan Perán, Juan Segura. Stability for one-dimensional discrete dynamical systems revisited. Discrete and Continuous Dynamical Systems - B, 2020, 25 (2) : 635-650. doi: 10.3934/dcdsb.2019258
[15]	Giovanni Russo, Fabian Wirth. Matrix measures, stability and contraction theory for dynamical systems on time scales. Discrete and Continuous Dynamical Systems - B, 2022, 27 (6) : 3345-3374. doi: 10.3934/dcdsb.2021188
[16]	Chun-Xiang Guo, Guo Qiang, Jin Mao-Zhu, Zhihan Lv. Dynamic systems based on preference graph and distance. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1139-1154. doi: 10.3934/dcdss.2015.8.1139
[17]	Mario Roy, Mariusz Urbański. Multifractal analysis for conformal graph directed Markov systems. Discrete and Continuous Dynamical Systems, 2009, 25 (2) : 627-650. doi: 10.3934/dcds.2009.25.627
[18]	Chunmei Zhang, Wenxue Li, Ke Wang. Graph-theoretic approach to stability of multi-group models with dispersal. Discrete and Continuous Dynamical Systems - B, 2015, 20 (1) : 259-280. doi: 10.3934/dcdsb.2015.20.259
[19]	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
[20]	Radosław Czaja. Pullback attractors via quasi-stability for non-autonomous lattice dynamical systems. Discrete and Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021276

2020 Impact Factor: 2.425

Tools

Metrics

Other articles
by authors

on AIMS
Matthew Macauley Henning S. Mortveit
on Google Scholar
Matthew Macauley Henning S. Mortveit

[Back to Top]