Reduction of the complexity of models of network structures and systems

Polishchuk, OD
Dopov. Nac. akad. nauk Ukr. 2019, 6:12-18
https://doi.org/10.15407/dopovidi2019.06.012
Section: Information Science and Cybernetics
Language: Ukrainian
Abstract: 

The problem of complexity of network structures and systems is analyzed. The quantitative indicators of the dimensional and connective network complexity are determined, and examples of their application for choosing an effective model of the system structure are given. The methods of reduction of the complexity of models of network systems are offered, taking into account that such systems can be investigated only in general. The first of these approaches consists in the identification and exclusion of fictitious elements from the network, i.e. nodes and edges are formally included in the structure, but not involved in the system operation. This allows us to reduce the complexity of many real system models by dozens. The concepts of flow adjacency matrix and the flow core of a network system determining the most functionally important components of it are introduced. In the simplest case, the flow cores allow us to exclude the transit nodes from the system model, i.e. elements which do not add or remove the part of flows that are moving through the network. The specific weight of the flow core determines how adequate is its model in comparison with the source network model. A number of examples show that the flow cores significantly reduce the complexity of system models. The method of encapsulation of the components of supplements to flow cores is proposed to increase the adequacy of their models. The main features of subnets that can be encapsulated are determined, and examples of real systems are given, for which the encapsulation method reduces the dimension of their models by dozens and more without significant loss of adequacy.

Keywords: adequacy, complexity, core, encapsulation, network system, reduction
References: 

1. Dorogovtsev, S. N. & Mendes, J. F. F. (2013). Evolution of networks: From biological Nets to the Internet and WWW. Oxford: Oxford Univ. Press.
2. Caldarelli, G. & Vespignani, A. (2007). Large scale structure and dynamics of complex networks: From information technology to finance and natural science. New York: World Scientific. doi: https://doi.org/10.1142/6455
3. Spickermann, C. (2011). Entropies of condensed phases and complex systems. Berlin: Springer. doi: https://doi.org/10.1007/978-3-642-15736-3
4. The supercomputer created models of spiral galaxies for several months. Available: http://hyser.com.ua/tehnology/superkompyuter-neskolko-mesyatsev-sozdaval... (in Russian).
5. Polishchuk, O. (2014). Solution of double-sided boundary value problems for the Laplacian in R3 by means of potential theory methods. In Proc. of the XIХ-th Intern. Seminar on Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory, pp. 140-142. doi: https://doi.org/10.1109/DIPED.2014.6958350
6. Polishchuk, O. D. (2016). On the removal of singularities in the numerical solution of integral equations of the potential theory. J. Math. Sci. No. 1, pp. 27-37. doi: https://doi.org/10.1007/s10958-015-2646-4
7. Prell, C. (2012). Social Network Analysis: History, Theory and Methodology. New York: SAGE.
8. Francis, W. N. & Kucera, H. (1982). Frequency Analysis of English Usage. Boston: Houghton Mifflin.
9. Polishchuk, D., Polishchuk, O. & Yadzhak, M. (2014). Complex evaluation of hierarchically-network systems. Automatic Control and Information Sciences. Vol. 2 (2), pp. 32-44. doi: https://doi.org/10.12691/acis-2-2-1
10. Dorogovtsev, S. N., Goltsev, A. V. & Mendes, J. F. F. (2006). k-core organization of complex networks. Phys. Rev. Let., 96 (4), 040601. doi: https://doi.org/10.1103/PhysRevLett.96.040601
11. Polishchuk, O. D. & Yadzhak, M. S. (2018). Network structures and systems: II. Cores of networks and multiplexes. Systems research and information technologies. No. 3, pp. 38-51 (in Ukrainian). doi: https://doi.org/10.20535/SRIT.2308-8893.2018.3.04