Number of attractors and cyclic states in finite dynamic systems of complete graphs orientations

A. V. Zharkova

Prikladnaâ diskretnaâ matematika, no. 1 (2024), pp. 91-101.

Résumé

Graph models occupy an important place in information security tasks, including the construction of models and methods for managing the continuous operation of systems and system recovery, countering denials of service. Finite dynamic systems of complete graphs orientations are considered. States of a dynamic system $(\Gamma_{K_n},\alpha)$, $n \geq 1$, are all possible orientations of the complete graph ${K_n}$, and evolutionary function transforms the graph orientation by reversing all the arcs that enter into sinks, and there are no other differences between the given and the next digraphs. Formulas are obtained for counting the number of cyclic (belonging to attractors) system states and the number of states that are not cyclic (not belonging to attractors), namely, the number of states belonging to attractors is $1$, if $n=1$; $2^{{(n-1)(n-2)}/{2}}(2^{n-1}-n)+n!$, if $n>1$, the number of states not belonging to attractors is $0$, if $n=1$; $n \cdot 2^{{(n-1)(n-2)}/{ 2}} - n!$, if $n>1$. Formulas are obtained for counting the number of attractors of the system, including various types, namely, the number of attractors of length $1$ is $1$, if $n=1$; $2^{{(n-1)(n-2)}/{2}}(2^{ n-1}-n)$, if $n>1$, the number of attractors of length $n$ is $(n-1)!$, the number of attractors (basins) is $1$, if $n=1$; $2^{{(n-1)(n-2)}/{2 }}(2^{n-1}-n)+(n-1)!$, if $n>1$. The corresponding tables are given for $n=1,\ldots,20$.

Détail

Keywords: attractor, complete graph, cybersecurity, cyclic state, evolutionary function, fault-tolerance, finite dynamic system, graph.

Bibliographie

[1] Grigorchuk R. I., Nekrashevych V. V., Sushchansky V. I., “Automata, Dynamic Systems and Groups”, Trudy MIAN, 231, 2000, 134–214 (in Russian) | Zbl

[2] Barbosa V. C., An Atlas of Edge-Reversal Dynamics, Chapman/CRC, London, 2001, 372 pp. | MR | Zbl

[3] Salii V. N., “On a class of finite dynamic systems”, Vestnik Tomskogo Gosuniversiteta. Prilozhenie, 2005, no. 14, 23–26 (in Russian)

[4] Osipenko G., Dynamical Systems, Graphs, and Algorithms, Springer Verlag, Berlin–Heidelberg, 2007, 300 pp. | MR | Zbl

[5] Shcherbina O. A., “Methodological aspects of dynamic programming”, Dinamicheskie Sistemy, 2007, no. 22, 21–36 (in Russian)

[6] Zavlanos M. M. and Pappas G. J., “A dynamical systems approach to weighted graph matching”, Automatica, 44:11 (2008), 2817–2824 | DOI | MR | Zbl

[7] Macauley M. and Mortveit H. S., “Cycle equivalence of graph dynamical systems”, Nonlinearity, 22:2 (2009), 421–436 | DOI | MR | Zbl

[8] Kuhlman C. J., Kumar V. S. A., Marathe M. V., et al., “A general-purpose graph dynamical system modeling framework”, Proc. 2011 Winter Simulation Conf. (Phoenix, USA, 2011), 296–308

[9] Ara P. and Exel R., “Dynamical systems associated to separated graphs, graph algebras, and paradoxical decompositions”, Adv. Math., 252 (2014), 748–804 | DOI | MR | Zbl

[10] Abdelhamid S. H. E., Kuhlman C. J., Marathe M. V., et al., “GDSCalc: a web-based application for evaluating discrete graph dynamical systems”, PLoS ONE, 10:8 (2015), 24 pp. https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0133660

[11] Aledo J. A., Martinez S., and Valverde J. C., “Graph dynamical systems with general Boolean states”, Appl. Math. Inform. Sci., 9:4 (2015), 1803–1808 | MR

[12] Kadyrov A. A. and Kadyrov A. A., “Conceptual foundations of general theory of discrete dynamic, relay and logical-dynamic systems based on physical decomposition and graph models”, Vestnik VolSU, Ser. 10, Innov. Deyat., 2015, no. 2(17), 80–89 (in Russian) | MR

[13] Volgina M. A., “Formalization of information flows of graph models of dynamical systems”, Al'manakh Sovremennoy Nauki i Obrazovaniya, 2015, no. 3(93), 23–26 (in Russian)

[14] Aledo J. A., Diaz L. G., Martinez S., and Valverde J. C., “Coexistence of periods in parallel and sequential boolean graph dynamical systems over directed graphs”, Math., 8:10 (2020), 1812–1825 | DOI | MR

[15] Gadouleau M., “On the influence of the interaction graph on a finite dynamical system”, Natural Computing, 19 (2020), 15–28 | DOI | MR | Zbl

[16] Zharkova A. V., “On the number of cyclic states in finite dynamic systems of complete graphs orientations”, Komp'iuternye Nauki i Informatsionnye Tekhnologii (Saratov, 2018), 149–151 (in Russian)

[17] Zharkova A. V., “On the number of attractors in finite dynamic systems of complete graphs orientations”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2018, no. 11, 106–109 (in Russian)

[18] Bogomolov A. M. and Salii V. N., Algebraic Foundations of the Theory of Discrete Systems, Nauka Publ., M., 1997, 368 pp. (in Russian) | MR

[19] Vlasova A. V., Attractors in Dynamic Systems of Binary Vectors, Dep. in VINITI 23.06.2010, no. 392-B, 2010, 19 pp. (in Russian)

[20] Zharkova A. V., “Attractors and cyclic states in finite dynamic systems of complete graphs orientations”, Prikladnaya Diskretnaya Matematika, 2023, no. 59, 80–87 (in Russian) | MR | Zbl