Abstract
The paper presents a double-threshold flow model based on the model called “resource network” [1]. Resource network is a non-classical diffusion model where vertices of directed weighted graph exchange homogeneous resource along incident edges in discrete time. There is a threshold value in this model, specific for every topology: when the total resource amount is large (above this threshold value), the certain vertices start accumulating resource. They are called “attractor vertices”. In a novel model described in this paper, attractor vertices have limits on their capacities. Thus, another set of vertices (“secondary attractors”) accumulates the remaining surplus of resource. Another threshold value appears in such a network. It is shown that the process of resource redistribution, when its amount is above the second threshold, is described by a non-homogeneous Markov chain. The vertex’ ability of being an attractor (primary, secondary, etc.) can be used as a new integer measure of centrality in networks with arbitrary semantics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Kuznetsov, O.P., Zhilyakova, L.Y.: Bidirectional resource networks: a new flow model. Dokl. Math. 82(1), 643–646 (2010)
Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Ahuja, R.К., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications, p. 846. Prentice Hall, New Jersey (1993)
Szeto, W., Iraqi, Y., Boutaba, R.: A multi-commodity flow based approach to virtual network resource allocation. In: Proceedings of Global Telecommunications Conference. GLOBECOM 2003, vol. 6. pp. 3004–3008. IEEE (2003)
Zhilyakova, L.Yu.: Using resource networks to model substance distribution in aqueous medium. Autom. Remote Control 73(9), 1581–1589 (2012). https://doi.org/10.1134/S0005117912090111
Blanchard, Ph., Volchenkov, D.: Random Walks and Diffusions on Graphs and Databases: An Introduction. Springer Series in Synergetics. Springer-Verlag, Berlin (2011). https://doi.org/10.1007/978-3-642-19592-1
Björner, A., Lovasz, L., Shor, P.: Chip-firing games on graphs. Eur. J. Comb. 12, 283–291 (1991)
Björner, A., Lovasz, L.: Chip-firing games on directed graphs. J. Algebraic Comb. 1, 305–328 (1992)
Biggs, N.L.: Chip-firing and the critical group of a graph. J. Algebraic Comb. 9, 25–45 (1999). Kluwer Academic Publishers, Netherlands
Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality. Phys. Rev. A 38, 364–374 (1988)
Bak, P.: How Nature Works: The Science of Self-Organized Criticality. Copernicus, New York (1996)
Dhar, D.: The Abelian sandpile and related models. Phys. A: Stat. Mech. Appl. 263(1–4), 4–25 (1999)
Zhilyakova, LYu.: Dynamic graph models and their properties. Autom. Remote Control 76(8), 1417–1435 (2015). https://doi.org/10.1134/S000511791508007X
Kuznetsov, O.P.: Uniform resource networks. I. Complete graphs. Autom. Remote Control 70(11), 1767–1775 (2009). Moscow
Zhilyakova, L.Yu., Kuznetsov, O.P.: Resource Network Theory: Monograph. RIOR: INFRA-M, Moscow (2017). (Science). 283 p. https://doi.org/10.12737/21451
Zhilyakova, L.Yu.: Resource Networks with Limitations on Vertex Capacities: Monograph. RIOR, Moscow (2018). 160 p. https://doi.org/10.12737/1745-6
Erusalimskii, Ya.M.: Flows in Networks with Nonstandard Reachability, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki, no. 1, pp. 5–7 (2012)
Jungnickel, D.: Graphs, Networks and Algorithms, 3rd edn. Springer, Berlin (2007). 650 p.
Basu, A., Blanning, R.W.: Metagraphs and Their Applications. Springer, New York (2007). 172 p. https://doi.org/10.1007/978-0-387-37234-1
Chartrand, G., Lesniak, L., Zhang, P.: Graphs & Digraphs, 6th edn. CRC Press, Boca Raton (2016). 625 p.
Gross, J.L., Yellen, J., Zhang, P. (eds.): Handbook of Graph Theory. Discrete Mathematics and Applications. CRC Press, Boca Raton (2014). 1630 p.
Knuth, D.E.: Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees-History of Combinatorial Generation. Addison-Wesley Professional, Boston (2006). 128 p.
Acknowledgments
This work was partially supported by the Russian Foundation for Basic Research, project no. 17-07-00541.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhilyakova, L.Y. (2018). Resource Network with Limitations on Vertex Capacities: A Double-Threshold Dynamic Flow Model. In: Kuznetsov, S., Osipov, G., Stefanuk, V. (eds) Artificial Intelligence. RCAI 2018. Communications in Computer and Information Science, vol 934. Springer, Cham. https://doi.org/10.1007/978-3-030-00617-4_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-00617-4_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-00616-7
Online ISBN: 978-3-030-00617-4
eBook Packages: Computer ScienceComputer Science (R0)