Graph Dynamic Threshold Model Resource Network: Key Features

Full Text (PDF, 437KB), PP.28-38

Views: 0 Downloads: 0

Author(s)

L. Yu. Zhilyakova 1

1. V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences 65, Profsoyuznaya street, Moscow 117997, Russia

* Corresponding author.

DOI: https://doi.org/10.5815/ijmsc.2017.03.03

Received: 1 May 2017 / Revised: 31 May 2017 / Accepted: 2 Jun. 2017 / Published: 8 Jul. 2017

Index Terms

Graph dynamic models, threshold models, flows in networks, Markov chains, diffusion on graphs, resource networks

Abstract

In this paper, we describe a graph dynamic threshold model called resource network, and briefly present the main results obtained during several years of research. Resource Network is represented by a connected oriented with weighted graph with an arbitrary topology. Weights of edges denote their throughput capacities for an abstract resource. The resource is stored in vertices, which can contain its unlimited amount. Network operates in discrete time. The total amount of resource is constant, while pieces of resource are reallocating among vertices every time step, according to certain rules with threshold switching. The main objective of our research is to define for a network with an arbitrary topology all its basic characteristics: the vectors of limit state and flow for every total amount of resource W; the threshold value of total recourse T, which switches laws of operating of the network; description of these laws. It turned out that there exists several classes of networks depending on their topologies and capacities. Each class demonstrates fundamentally different behavior. All these classes and their characteristics will be reviewed below.

Cite This Paper

L. Yu. Zhilyakova,"Graph Dynamic Threshold Model Resource Network: Key Features", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.3, No.3, pp.28-38, 2017.DOI: 10.5815/ijmsc.2017.03.03

Reference

[1]Ford L.R., Jr. and Fulkerson D.R. Flows in Networks, Princeton Univ. Press, Princeton. 1962.

[2]Ahuja R.К., Magnati T.L., and Orlin J.B. Network Flows: Theory, Algorithms and Applications. Prentice Hall, New Jersey. 1993

[3]Fleischer, L. and Skutella, M., Minimum Cost Flows Over Time without Intermediate Storage, in Proc.35th ACM/SIAM Symp. on Discrete Algorithms (SODA), January 2003, pp. 66–75.

[4]Szeto W., Iraqi Y., and Boutaba R. A multi-commodity flow based approach to virtual network resource allocation. Proceedings of Global Telecommunications Conference. GLOBECOM '03. IEEE. 2003.

[5]Zhilyakova L.Yu. Using resource networks to model substance distribution in aqueous medium // Automation and Remote Control, 2012. V. 73, No. 9. P. 1581-1589. DOI: 10.1134/S0005117912090111

[6]Blanchard, Ph. and Volchenkov, D., Random Walks and Diffusions on Graphs and Databases: An Introduction, Springer Series in Synergetics, Berlin: Springer-Verlag, 2011.

[7]Björner A., Lovasz L. and Shor P. Chip-firing games on graphs, Europ. J. Comb. 12 (1991), 283–291.

[8]Björner A., Lovasz L. Chip-firing games on directed graphs, J. Algebraic Combinatorics 1 (1992), 305–328.

[9]Biggs, N.L. Chip-Firing and the Critical Group of a Graph // Journal of Algebraic Combinatorics 9 (1999), pp. 25–45. Kluwer Academic Publishers. Netherlands. 1999.

[10]Bak, P., Tang, C. and Wiesenfeld, K. Self-organized criticality, Physical Review A 38. 1988, P. 364 – 374.

[11]Bak, P. How Nature Works: The Science of Self-Organized Criticality. New York: Copernicus. 1996.

[12]Dhar, D. The abelian sandpile and related models // Physica A: Statistical Mechanics and its applications. Volume 263, Issues 1–4, 1 February 1999, pp. 4 – 25.

[13]Speer, E. R. Asymmetric abelian sandpile models // Journal of Statistical Physics. April 1993, Volume 71, Issue 1-2, pp. 61 – 74.

[14]Zhilyakova L.Yu. Dynamic Graph Models and Their Properties// Automation and Remote Control, 2015, Vol. 76, No. 8, pp. 1417–1435. DOI: 10.1134/S000511791508007X

[15]Kuznetsov O.P. Uniform Resource Networks. I. Complete Graphs. // Automation and Remote Control, vol.70, No.11, Moscow, 2009. pp.1767–1775.

[16]Roberts F.S., Discrete Mathematical Models with Application to Social, Biological, and Environmental Problems, Englewood Cliffs: Prentice Hall, 1976.

[17]Kemeny J.G. and Snell, J.L. Finite Markov Chains. Van Nostrand_Reinhold, New York. 1960.

[18]Zhilyakova L.Yu. Asymmetrical Resource Networks. I. Stabilization Processes for Low Resources // Automation and Remote Control, 2011. Vol. 72, No.4. P. 798-807. doi: 10.1134/S0005117911040102

[19]Zhilyakova L.Yu. Asymmetric resource networks. III. A study of limit states // Automation and Remote Control. 2012. V. 73. No. 7. P. 1165 – 1172. doi: 10.1134/S0005117912070065

[20]Zhilyakova L. Yu. A study of Euler resource networks // Automation and Remote Control. 2014. V.75. No. 12. P. 2248–2261 DOI: 10.1134/S0005117914120145

[21]Zhilyakova L.Yu. Control of limit states in absorbing resource networks // Automation and Remote Control, 2014, 75:2, 360–372. DOI: 10.1134/S0005117914020143

[22]Zhilyakova L.Yu. Allocation of resource among attractor-vertices in nonsymmetric regular resource networks UBS, 60 (2016), 82–118.