Abstract
The review of a number of non-classical flow models and threshold models of spreading activity in a network is given. The description of flow models with nonstandard reachability is provided. Integer-valued threshold models to which “chip-firing game” and “probabilistic abacus” belongs are described. The model of self-organized criticality and its graph interpretation is described. We show the basic properties of a real “real-valued network” threshold model, and perform comparative analysis of these kinds of models.
Similar content being viewed by others
References
Barabási, A.-L. and Albert, R., Emergence of Scaling in Random Networks, Science, 1999, vol. 86, no. 5439, pp. 509–512.
Watts, D.J. and Strogatz, Sh., Collective Dynamics of “Small-World” Networks, Nature, 1998, vol. 393, no. 6684, pp. 440–442.
Kochkarov, A.A., Salpagarov, M.B., and Kochkarov, R.A., Modeling the Destruction of Complex Systems with Acyclic Structure, Upravlen. Bol’shimi Sist., 2007, no. 17, pp. 103–120.
Kochkarov, A.A., Salpagarov, M.B., and El’kanova, L.M., A Discrete Model of Structural Destruction for Complex Systems, Probl. Upravlen., 2007, no. 5, pp. 21–26.
Blanchard, Ph. and Volchenkov, D., Random Walks and Diffusions on Graphs and Databases: An Introduction, Springer Series in Synergetics, Berlin: Springer-Verlag, 2011.
Kuznetsov, O.P., Uniform Resource Networks I. Complete Graphs, Autom. Remote Control, 2009, vol. 70, no. 11, pp. 1889–1900.
Kuznetsov, O.P. and Zhilyakova, L.Yu., Two-Sided Resource Networks: A New Flow Model, Dokl. Akad. Nauk, 2010, vol. 433, no. 5, pp. 609–612.
Zhilyakova, L.Yu., Asymmetrical Resource Networks. I. Stabilization Processes for Low Resources, Autom. Remote Control, 2011, vol. 72, no. 4, pp. 798–807.
Zhilyakova, L.Yu., Asymmetric Resource Networks. II. Flows for Large Resources and Their Stabilization, Autom. Remote Control, 2012, vol. 73, no. 6, pp. 1016–1028.
Zhilyakova, L.Yu., Asymmetric Resource Networks. III. A Study of Limit States, Autom. Remote Control, 2012, vol. 73, no. 7, pp. 1165–1172.
Zhilyakova, L.Yu., A Study of Euler Resource Networks, Upravlen. Bol’shimi Sist., 2013, no. 41, pp. 28–50.
Zhilyakova, L.Yu., Ergodic Cyclical Resource Networks. I, Upravlen. Bol’shimi Sist., 2013, no. 43, pp. 34–54.
Zhilyakova, L.Yu., Ergodic Cyclical Resource Networks. II, Upravlen. Bol’shimi Sist., 2013, no. 45, pp. 6–29.
Zhilyakova, L.Yu., Control for Limit States in Absorbing Resource Networks, Probl. Upravlen., 2013, no. 3, pp. 46–51.
Zhilyakova, L.Yu., Applying Resource Networks to Model the Spread of Substances in an Aquatic Medium, Probl. Upravlen., 2011, no. 2, pp. 46–51.
Adel’son-Vel’skii, G.M., Dinits, E.A., and Karzanov, A.V., Potokovye algoritmy (Flow Algorithms), Moscow: Nauka, 1975.
Ford, L.R., Jr. and Fulkerson, D.R., Flows in Networks, Princeton: Princeton Univ. Press, 1962. Translated under the title Potoki v setyakh, Moscow: Mir, 1966.
Swamy, M.N.S. and Thulasiraman, K., Graphs, Networks, and Algorithms, New York: Wiley, 1981. Translated under the title Grafy, seti and algoritmy, Moscow: Mir, 1984.
Sedgewick, R., Algorithms in C++, Reading: Addison-Wesley, 1998. Translated under the title Fundamental’nye algoritmy na C++. Algoritmy na graphakh, St. Petersburg: DiaSoftYuP, 2002.
Lazarev, A.A. and Gafarov, E.R., Teoriya raspisanii. Issledovanie zadach s otnosheniyami predshestvovaniya i resursnymi ogranicheniyami (Scheduling Theory. A Study of Problems with Precedence Relations and Resource Constraints), Moscow: Vychisl. Tsentr Ross. Akad. Nauk, 2007.
Lovasz, L. and Plummer, M.D., Matching Theory, Budapest: Akademiai Kiado, 1986. Translated under the title Prikladnye zadachi teorii grafov. Teoriya parosochetanii v matematike, fizike, khimii, Moscow: Mir, 1998.
Ahuja, R.K., Magnati, T.L., and Orlin, J.B., Network Flows: Theory, Algorithms and Applications, New Jersey: Prentice Hall, 1993.
Erzin, A.I. and Takhonov, I.I., The Balanced Flow Problem, Sib. Zh. Industr. Mat., 2006, vol. IX, no. 4 (28), pp. 50–63.
Erzin, A.I. and Takhonov, I.I., Equilibrium Distribution of Resources in a Network Model, Sib. Zh. Industr. Mat., 2005, vol. VII, no. 3(23), pp. 58–68.
Basangova, E.O. and Erusalimskii, Ya.M., Different Kinds of Mixed Reachability, in Algebra i diskretnaya matematika (Algebra and Discrete Mathematics), Elista: KGU, 1985, pp. 70–75.
Basangova, E.O. and Erusalimskii, Ya.M., Mixed Reachability on Partially Directed Graphs, in Vychislitel’nye sistemy i algoritmy (Computing Systems and Algorithms), Rostov-on-Don: Rostov. Gos. Univ., 1983, pp. 135–140.
Erusalimskii, Ya.M., Flows in Networks with Nonstandard Reachability, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki, 2012, no. 1, pp. 5–7.
Erusalimskii, Ya.M. and Petrosyan, A.G., Random Processes in Networks with Bipolar Magnetism, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki, 2005, no. 11, pp. 10–16.
Erusalimskii, Ya.M., Skorokhodov, V.A., Kuz’minova, M.V., and Petrosyan, A.G., Grafy s nestandartnoi dostizhimost’yu: zadachi, prilozheniya (Graphs with Nonstandard Reachability: Problems and Applications), Rostov-on-Don: Yuzhn. Federal. Univ., 2009.
Petrosyan, A.G., A Flow Problem in Multiproduct Networks with Nonstandard Reachability, in Sovremennye problemy matematicheskogo modelirovaniya (Modern Problems of Mathematical Modeling), Rostov-on-Don, 2005, pp. 334–340.
Petrosyan, A.G., Flows in Networks with Bipolar Reachability, Izv. Vyssh. Uchebn. Zaved., Severo- Kavkaz. Region, Estestv. Nauki, 2006, no. 3, pp. 32–37.
Erusalimskii, Ya.M. and Skorokhodov, V.A., Graphs with Circuit Reachability. Markov Processes and Flows in Networks, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki, 2003, no. 2, pp. 3–5.
Kuz’minova, M.V., Restricted Magnetic Reachability on Directed Graphs, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki, 2006, no. 6, pp. 12–26.
Erusalimskii, Ya.M. and Petrosyan, A.G., Multiproduct Flows in Networks with Nonstandard Reachability, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki, 2005, no. 6, pp. 8–16.
Erusalimskii, Ya.M., A General Method for Solving Reachability Problems on Directed Graphs, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki, 2000, no. 3, pp. 62–63.
Erusalimskii, Ya.M. and Skorokhodov, V.A., A General Approach to Nonstandard Reachability on Graphs, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki, 2005, Special Issue Pseudodifferential Equations and Problems of Mathematical Physics, pp. 64–67.
Erusalimskii, Ya.M. and Vodolazov, N.N., Nonstationary Flow in a Network, Vest. DGTU, 2009, vol. 9, no. 3, pp. 402–409.
Erusalimskii, Ya.M. and Vodolazov, N.N., Maximal Jump in a Network and Maximal Capacity of a Network, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki, 2010, no. 6, pp. 9–13.
Lovász, L. and Winkler, P., Mixing of Random Walks and Other Diffusions on a Graph, in Surveys in Combinatorics, Rowlinson, P., Ed., London Math. Soc., Lecture Notes Series 218, Cambridge Univ. Press, 1995, pp. 119–154.
Aiello, W., Awerbuch, B., Maggs, B., and Rao, S., Approximate Load Balancing on Dynamic and Asynchronous Networks, Proc. 25 ACM Sympos. Theory Comput., 1993, pp. 632–634.
Dasgupta, K., Singh, R., Viswanathan, B., et al., Social Ties and Their Relevance to Churn in Mobile Telecom Networks, Proc. 11 Int. Conf. Extending Database Technol. EDBT’08: Advances in Database Technology, ACM New York, USA, 2008, pp. 668–677.
Gubanov, D.A., Novikov, D.A., and Chkhartishvili, A.G., Sotsial’nye seti. Modeli informatsionnogo vliyaniya, upravleniya i protivoborstva (Social Networks. Models of Informational Influence, Control, and Competition), Moscow: Fizmatlit, 2010.
Gubanov, D.A. and Novikov, D.A., Models of Unified Information Control in Uniform Social Networks, Upravlen. Bol’shimi Sist., Special issue 30.1 “Network Models in Control,” 2010, pp. 722–742.
Novikov, D.A., Setevye struktury i organizatsionnye sistemy (Network Structures and Organizational Systems), Moscow: Inst. Probl. Upravlen., 2003.
Brin, S. and Page, L., The PageRank Citation Ranking: Bringing Order to the Web, URL: http://infolab.stanford.edu/backrub/pageranksub.ps.
Kussul’, N. and Soklov, A., Adaptive Anomaly Detection in the Behavior of the Users of Computer Systems with Variable Order Markov Chains, Part 2, Probl. Upravlen. Informat., 2003, no. 4, pp. 83–88.
Ye, N., A Markov Chain Model of Temporal Behavior for Anomaly Detection, Proc. 2000 IEEE Workshop Inform. Assurance Security United States Military Acad. West Point, New York, 6–7 June, 2000, pp. 171–174.
Agaev, R.P. and Chebotarev, P.Yu., Convergence and Stability in Problems of Reconciling Characteristics (a Survey of Fundamental Results), Upravlen. Bol’shimi Sist., Special Issue 30.1 “Network Models in Control,” 2010, pp. 470–505.
Agaev, R.P. and Chebotarev, P.Yu., The ProjectionMethod for Reaching Consensus and the Regularized Power Limit of a Stochastic Matrix, Autom. Remote Control, 2011, vol. 72, no. 12, pp. 2458–2476.
Anderson, R.J., Lovász, L., Shor, P.W., et al., Disks, Balls, and Walls: Analysis of a Combinatorial Game, Am. Math. Monthly, 1989, vol. 96, no. 6, pp. 481–493.
Biggs, N.L., Chip-Firing and the Critical Group of a Graph, J. Algebr. Combinat., 1999, vol. 9, no. 1, pp. 25–45.
Biggs, N., The Tutte Polynomial as a Growth Function, J. Algebr. Combinat., 2000, vol. 10, no. 2, pp. 115–133.
Björner, A., Lovász, L., and Shor, P., Chip-Firing Games on Graphs, Eur. J. Combinat., 1991, vol. 12, pp. 283–291.
Björner, A. and Lovász, L., Chip-Firing Game on Directed Graphs, J. Algebr. Combinat., 1992, no. 1, pp. 305–328.
Spencer, J., Balancing Vectors in the Max Norm, Combinatorica, 1986, vol. 6, pp. 55–66.
Chung, F. and Ellis, R., A Chip-Firing Game and Dirichlet Eigenvalues, Discrete Math., 2002, vol. 257, no. 2-3, pp. 341–355.
Chung, F., Laplacians and the Cheeger Inequality for Directed Graphs, Ann. Combinat., 2005, vol. 9, no. 1, pp. 1–19.
Lopez, C.M., Chip-Firing and the Tutte Polynomial, Ann. Combinat., 1997, vol. 1, no. 1, pp. 253–259.
Prisner, E., Parallel Chip Firing on Digraphs, Complex Syst., 1994, no. 8, pp. 367–383.
Sevast’yanov, B.A., Vetvyashchiesya protsessy (Branching Processes), Moscow: Nauka, 1971.
Burman, Yu.M., Mnogochlen Tatta i model’ sluchainykh klasterov (Tutte Polynomial and the Random Clusters Model), Mat. Prosv., Ser. 3, 11, Moscow: MTsNMO, 2007, pp. 47–60.
Engel, A., The Probabilistic Abacus, Educ. Stud. Math., 1975, vol. 6, no. 1, pp. 1–22.
Engel, A., Why Does the Probabilistic Abacus Work?, Educ. Stud. Math., 1976, vol. 7, no. 1, pp. 59–69.
Gantmakher, F.R., Teoriya matrits (Theory of Matrices), Moscow: Fizmatlit, 2004.
Lancaster, P., Theory of Matrices, New York: Academic, 1969. Translated under the title Teoriya matrits, Moscow: Nauka, 1982.
Bak, P., How Nature Works: The Science of Self-Organized Criticality, New York: Copernicus, 1996. Translated under the title Kak rabotaet priroda: Teoriya samoorganizovannoi kritichnosti, Moscow: Librokom, 2013.
Bak, P., Tang, C., and Wiesenfeld, K., Self-Organized Criticality, Phys. Rev. A, 1988, vol. 38, no. 1, pp. 364–374.
Bak, P. and Chen, K., Self-Organized Criticality, Scientif. Am., 1991, no. 264, pp. 46–53.
Dhar, D., Self-Organized Critical State of Sandpile Automaton Models, Phys. Rev. Lett., 1990, vol. 64, pp. 1613–1616.
Dhar, D., The Abelian Sandpile and Related Models, Phys. A: Statist. Mechan. Appl., vol. 263, nos. 1–4, pp. 4–25.
Dhar, D., Sadhu, T., and Chandra, S., Pattern Formation in Growing Sandpiles, Eur. Phys. Lett., 2009, vol. 85, no. 4, 48002, arXiv:0808.1732 [cond-mat.stat-mech].
Dhar, D., Ruelle, P., Sen, S., and Verma, D.-N., Algebraic Aspects of Abelian Sandpile Models, 1994, arXiv:cond-mat/9408020.
Meester, R., Redig, F., and Znamenski, D., The Abelian Sandpile: a Mathematical Introduction, 2008, URL: http://www.cs.vu.nl/~rmeester/onderwijs/introduc-tion_spatial_models/sandpile2.pdf.
Redig, F., Mathematical Aspects of the Abelian Sandpile Model, June 2005, URL: http://www.math.leidenuniv.nl/~redig/sandpilelectures.pdf.
Kemeny, J. and Snell, J., Finite Markov Chains, Princeton: Van Nostrand, 1960. Translated under the title Konechnye tsepi Markova, Moscow: Nauka, 1970.
Roberts, F.S., Discrete Mathematical Models with Application to Social, Biological, and Environmental Problems, Englewood Cliffs: Prentice Hall, 1976. Translated under the title Diskretnye matematicheskie modeli s prilozheniem k sotsial’nym, biologicheskim i ekologicheskim zadacham, Moscow: Nauka, 1986.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © L.Yu. Zhilyakova, 2015, published in Avtomatika i Telemekhanika, 2015, No. 8, pp. 115–139.
Rights and permissions
About this article
Cite this article
Zhilyakova, L.Y. Dynamic graph models and their properties. Autom Remote Control 76, 1417–1435 (2015). https://doi.org/10.1134/S000511791508007X
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S000511791508007X