OPEN ACCESS
Analysis of real network systems with high accuracy leads to building complex high-dimension models. When the time for determining system, parameters plays an important role the system modeling, time becomes a critical parameter. So, one needs to find an approximate simpler representation of such network systems while preserving the characteristic properties of the higher dimension system. In this paper, an approach related to formal transformations of the system structure model using multilevel aggregation has been applied to obtain a reduction in computational complexity and faster modeling. Software implementation of the developed algorithm allowed evaluating the effectiveness of the approach. The efficiency of the approach is demonstrated using an example of solving the maximum flow problem. Multilevel structural model transformations result in the dimension reduction of a network system presentation and, consequently, a decrease in the execution time of computational procedures.
aggregation, element connection scheme, large scale system, structure model reduction, UML diagram
Modern technical and technological objects are characterized by many elements, a variety of links and a significant amount of processed information. Complex systems are systems in which the pattern of interactions between a system’s constituent parts is itself complex and is evolving together with the system’s dynamics. Complex systems are those where the number of states determined by the states of elements or by the interrelations between elements is combinatorically large or uncountable. It provides the system with essential properties and imposes a number of restrictions on the study of such systems. Complex systems require specific methods for analysis and design. The main purpose of these methods is that they reduce the system to a smaller dimension, using its aggregation or decomposition.
Three groups of problems should be solved for them:
(1) The analysis of properties and behavior of the system, depending on its structure and the value of its parameters.
(2) The selection of the structure and values of the parameters based on the properties of the system.
(3) The construction of complex systems.
In the context of network theory, a complex network is a network with non-trivial topological features and with a multitude of non-trivial statistical challenges [1, 2].
The subject of research is network systems including discrete, dynamic and stochastic systems with discrete or continuous-time, where the flow balance law takes place [3].
This work is devoted to the problems of formal transformations of the structural models of network systems with the purpose of reducing the dimension of the system, when the time of evaluating system metrics plays an important role in solving real-time control problems, and when the time of modeling the system is a critical parameter.
Over the past decade, the number of papers devoted to the study of so-called «complex networks» or, in other words, complex systems with network topology, has increased.
Networks are used as a common model of a wide variety of complex systems. The following classification of complex networks is widely used at present [4, 5]: Technological, biological, ecological and social. Much attention is paid to the theory of networks, network modeling.
Many complex systems can be represented as multilevel networks composed by distinct elements, interacting and depending on each other. The basic elements of real-world systems are connected by diﬀerent types of interactions. For example, in technological networks, a network element can be hardware, software, data, processes (including processes for providing service to users), facilities; in the case of social networks, in which the same set of people might have political or ﬁnancial relationships, or might be interacting using diﬀerent platforms like e-mail, Twitter, Facebook, phone calls, etc.; in ecological networks, network models are composed of a set of compartments, describing either species or functional groups, and a set of links that represent interactions or energy or biomass flows among compartments.
One of the challenges for ecological and biological-network models is to study deferent properties of systems. For example, complexity and stability, controllability and observability. To study the properties of ecological systems, multilevel network models are constructed using a series of aggregation process. The construction of ecological multilevel network models is extremely difficult problem because of the limitations in data availability associated with the difference in type of network models, level aggregation and timescale. The authors [6] state that machine learning and better data sharing between ecologists represent very important areas for advances in ecological networks.
It is known that the mathematical model of a technological network system consists of two parts: a description of its elements and a description of the structure of the system. The formal technics describing mathematical models of technological systems is well studied and includes: queueing theory, Petri nets, process algebra, and set theory.
A number of problems of the system analysis require an investigation of the structural model of a complex system. At the same time, some of them are solved only by transforming the existing structure into a kind that allows to achieve the solution of the tasks assigned to the research.
The authors [7] apply the aggregation of elements of a queuing network with the purpose of reducing its dimension and decreasing simulation time. The main point of the aggregation consists in dividing the network into two parts - the main nodes, being of interest, and the remaining nodes. It is claimed that the method is effective only in a limited range of statistical characteristics of the nodes.
The authors [8] consider the method of investigating a complex network system based on its decomposition. The method reduces the dimension of the system model and improves the performance of the modeling system on parallel platforms.
Concept of aggregation is used it the paper [9] to ﬁnding shortest paths in a graph. This is used for the satellite navigation to be able to eﬃciently respond in real-time to traﬃc updates.
The authors [10] investigate aggregation schemes for Markov processes. The approach was to lump states of a Markov process together in groups and propose a Markov process on the set of groups which has the aggregated stationary probability. The potential benefits are efficient computation, including recomputation to take into account local changes.
In the paper [11], the authors demonstrate how structure model metrics of a complex network system can be used to create random networks. The developed random networks estimate the types of network failures and their associated consequences.
The tasks of topological analysis of systems represent a range of complex problems, the solution of which requires large computing resources and the development of mathematical methods. They can be combined into such groups:
(1) Development of a valid structural description of a complex system. The tasks of this group compose a topological structure on the base of an original specification of a complex system, that is, determine elements and subsystems of a complex system and their connectivity.
(2) Determination of characteristics of a complex system with a specified topological structure. For example, a definition of strongly connected components, shortest paths, cycles, races, etc. In addition, the system structure model is used to analyze the quality metrics of the structure. For example, the number of links among subsystems; weighted number of links, whose weights are usually the functions of length, bandwidth or other characteristics of the channels, the rate of message transmission over channels, and so on.
(3) Optimal design, equivalent transformations of the topological structure of a complex system.
Most of the tasks of the third group are tasks of the increased complexity. The structure design for network systems is one of the main tasks and consists in choosing the optimal scheme for connecting nodes, selecting the transmission capacity of channels and optimal routing. The choice of a topological structure is carried out using various criteria and takes into account the constraints for time delay, the reliability of information transfer, etc.
The problem of equivalent transformations considered in this paper belongs to the third group of topological analysis tasks. Equivalent transformations can be applied in the following cases:
(1) Redistribution of links and interaction schemes within the framework of the initial structure.
(2) Aggregation and decomposition of the system components.
(3) Analysis of the model structure for detecting parallelism, deadlocks and solving the problem of mutual exclusions.
(4) Reducing the dimension of a system, when the time of metrics evaluation plays an important role in solving real-time control tasks, and also when the time of modeling the system is a critical parameter.
This section is devoted to the construction of a system structure model and development of an algorithm for its multi-level aggregation. Here, we consider the problems related only to transformations of an element connection scheme. The dynamic of a system is not considered.
A complex system S contains elements C_{i }($\mathrm{i}=\overline{0, \mathrm{N}}$ ), where N is a fixed number, and an external environment denoted by С_{0}. Let’s consider the formal model of a complex system structure [12, 13].
We formulate the first assumption as follows. Elementary signals are transmitted in a system over elementary channels. The elementary channel l connected to the output of the element C_{j} can transmit only elementary signals y_{l}^{(j)}(t) having a fixed index l.
This assumption admits the following interpretation. The input of element С_{j} consists of m_{j} input contacts; the contact Х_{i}^{(j)} receives the elementary signals x_{i}^{(j)}(t); $\mathrm{i}=\overline{0, \mathrm{m}_{\mathrm{j}}}$ . Similarly, the output of element С_{j} consists of r_{j} output contacts; the contact Y_{l}^{(j)} gives out the elementary signals y_{l}^{(j)}(t) which are accepted by one or more elements; $1=\overline{0, \mathrm{r}_{\mathrm{j}}}$. Thus, the mathematical model of the element С_{j} used for the formal description of its connection with other elements is a pair of sets: $\left[\mathrm{X}_{\mathrm{i}}^{(\mathrm{j})}\right]_{1}^{\mathrm{m}}$ and $\left[\mathrm{Y}_{1}^{(\mathrm{j})}\right]_{1}^{\mathrm{r}}$, where for simplicity we use the notations m = m_{j}, r = r_{j}.
The second assumption. Not more than one elementary channel is connected to the input contact of any element of system; any finite number of elementary channels can be connected to the output contact.
We introduce the single-valued operator [14]:
$\mathrm{Y}_{1}^{(\mathrm{k})}=\mathrm{R}\left(\mathrm{X}_{\mathrm{i}}^{(\mathrm{j})}\right)$ (1)
where, the domain of the operator is the set $\bigcup_{j=0}^{N}\left[X_{i}^{(j)}\right]_{1}^{m}$ and the codomain of the operator is the set $\bigcup_{\mathrm{k}=0}^{\mathrm{N}}\left[\mathrm{Y}_{1}^{(\mathrm{k})}\right]_{1}^{\mathrm{r}}$.
The operator in Eq. (1) assigns the output contact Y_{l}^{(k)} to the input contact X_{i}^{(j)}. If no elementary channel is connected to the contact X_{i}^{(j)} in the system under consideration, then the operator R is not defined for this X_{i}^{(j)}. The operator in Eq. (1) we will call the operator of elements connections.
The operator of elements connections, its domain and codomain we will call the elements connections scheme of system or the formal model of the system structure. The elements connections scheme of system contains exhaustive information about the connections of system elements.
The form of the operator R plays an important role. It will affect the performance of any data processing algorithms especially in the case of large systems.
Consider the system, which structure is represented in Figure 1.
Figure 1. The structure of system S
Note, the inverse operator R_{j}^{-1} is not single-valued.
$\mathrm{X}_{\mathrm{i}}^{(\mathrm{j})}=\mathrm{R}^{-1}\left(\mathrm{Y}_{1}^{(\mathrm{k})}\right)$ (2)
Create the operator of elements connections R in a tabular form. The Table 1 shows the values of the operator R for the considered example of the system S.
In the Table 1, the numbers of rows correspond to the numbers of elements. The numbers of columns correspond to the numbers of the input contacts of elements. At the intersection of the row j and the column i there is a pair of numbers (k, l) indicating the number of the element k and the number of its output contact l, to which the contact X_{i}^{(j)} is connected.
Table 1. The operator R of the elements connections for the system S
j\i |
1 |
2 |
3 |
4 |
0 |
1,2 |
6,1 |
10,4 |
-,- |
1 |
3,1 |
2,2 |
-,- |
-,- |
2 |
0,3 |
0,1 |
8,1 |
-,- |
3 |
1,1 |
4,1 |
10,2 |
-,- |
4 |
1,1 |
2,3 |
3,2 |
10,1 |
5 |
6,2 |
1,1 |
2,1 |
-,- |
6 |
5,1 |
12,1 |
9,1 |
-,- |
7 |
2,3 |
0,3 |
8,2 |
-,- |
8 |
0,3 |
12,4 |
-,- |
-,- |
9 |
4,2 |
0,2 |
10,3 |
-,- |
10 |
9,2 |
3,3 |
12,3 |
-,- |
11 |
6,3 |
12,2 |
7,1 |
-,- |
12 |
11,1 |
1,1 |
0,3 |
-,- |
The aggregation of the considered system on the subsystems can be realized as follows: Sµ_{0} = {С_{0}}; Sµ_{1} = {С_{1}, С_{2}}; Sµ_{2} = {С_{3}, С_{4}}; Sµ_{3} = {С_{5}, С_{6}}; Sµ_{4} = {С_{7}, С_{8}}; Sµ_{5} = {С_{9}, С_{10}}; Sµ_{6} = {С_{11}, С_{12}}. The aggregation proposed is depicted in the Figure 2.
It is obvious that a subsystem S_{μi}, on the one hand, can itself be an independent system, just like the system S, and on the other hand, it can be an element of the system S. Further, for simplicity the subsystem S_{μi} will be considered as S_{μ}.
In this paper, the construction of the elements’ connections scheme and its implementation for these two cases are considered. In any case, the construction of the elements connections scheme consists of two steps: definition of the fictitious contacts on the border of the subsystem S_{μi} and construction of the operator of the elements connections.
Step 1. Definition of the fictitious contacts. Each subsystem on the border must have fictitious input and fictitious output contacts for communication with other subsystems of the system S. The fictitious contacts play the role of male-female connectors that connect the blocks of complex electronic devices.
In the first case, the subsystem S_{μ}, considered as an independent system, has to have an external environment, which is denoted as an external element С_{0}^{μ} or subsystem S^{′}_{μ0}.
The internal structure of the external environment S^{′}_{μ0} is invisible to the elements of the subsystem S_{μ}. The subsystem S_{μ} interacts with the external environment S^{′}_{μ0 }through its fictitious input contacts X_{i}^{(0)μ}, which are connected to output contacts of the elements of the subsystem S_{μ}, and through its fictitious output contacts Y_{l}^{(0)μ}, which are connected to input contacts of the elements of the subsystem S_{μ}.
In the second case, the system S is divided into several subsystems S_{μ}. Each of the subsystems is considered as an element of the system S. The internal structure of a subsystem S_{μ} is invisible to other subsystems of the system S. Each subsystem (on the border) must also have fictitious input X_{i}^{(μ)} and fictitious output Y_{l}^{(μ)} contacts for communication with other subsystems of the system S.
Combining these two cases, we come to the fact that the pair of contacts X_{i}^{(μ)} and Y_{j}^{(0)μ} and also X_{i}^{(0)μ} and Y_{l}^{(μ)} are combined into double fictitious contacts on the border of the subsystem S_{μ} (Figure 2).
Figure 2. The aggregation of the system S on the subsystems $S_{\mu i}$
Introducing the concept of fictitious contacts for each subsystem Sμ plays an important role. In a project, if necessary, it is easy to replace the subsystem Sμ with a new one. In comparison with the old subsystem Sμ, a new one can: use a faster circuitry, which can improve the performance of a system S; allow extending functionality, for example, by integrating additional security mechanism and so on.
Determine the fictitious contacts. It is obvious that the input and output fictitious contacts of the subsystem $\mathbf{S}_{\mu}$ are defined for the elements of two sets:
(1) [Y_{l}^{(j)}]_{μ} is a set of the output contacts of all elements С_{j}, where С_{j}∈$\mathbf{S}_{\mu}$, connected to the input contacts of the elements С_{k}, where C_{k}∉S_{μ}, as well as to the input contacts of the external environment С_{0}.
(2) [X_{i}^{(j)}]_{μ} is a set of the input contacts of all elements С_{j}, where С_{j}∈$\mathbf{S}_{\mu}$, connected to the output contacts of the elements С_{k}, where C_{k}∉S_{μ}, as well as to the output contacts of the external environment С_{0}.
So, the set [Y_{l}^{(j)}]_{μ} is determined as:
$\left[\mathrm{Y}_{1}^{(\mathrm{j})}\right]_{\mu}=\bigcup_{\mathrm{C}_{j} \in \mathrm{S}_{\mu}}\left\{\left[\mathrm{Y}^{(\mathrm{j}, 0)}\right] \cup\left(\bigcup_{\mathrm{C}_{\mathrm{k}} \notin \mathrm{S}_{\mu}}\left[\mathrm{Y}^{(\mathrm{j}, \mathrm{k})}\right]\right)\right\}$ (3)
where, [Y^{(j,k)}] is a set of output contacts of an element C_{j} connected to corresponding input contacts of an element C_{k}, where C_{k}∉S_{μ}.
Selecting contacts Y_{l}^{(j)} for inclusion in the set [Y_{l}^{(j)}]_{μ}, in general case, we can meet the same contact Y_{l}^{(j)} several times. According to the Idempotent Law of union of sets, the same contacts Y_{l}^{(j)} are not repeated. Thus, for each Y_{l}^{(j)}∈[Y_{l}^{(j)}]_{μ} it is sufficient to have only one fictitious contact Y_{l}^{(μ}^{)}.
Each Y_{l}^{(j)}∈[Y_{l}^{(j)}]_{μ} generates a double fictitious contact on the border of the subsystem S_{m}. A pair of operators is used to define this double fictitious contact:
$Y_{1}^{(\mu)}=Q_{\mu}\left(Y_{1}^{(j)}\right)$
$\mathrm{X}_{\mathrm{i}}^{(0) \mu}=\mathrm{Q}_{\mu}^{\prime}\left(\mathrm{Y}_{1}^{(\mathrm{j})}\right)$ (4)
The operators in Eq. (4) are called the numbering operators of fictitious contacts of the subsystem S_{μ}. The operator Q_{μ} defines an output fictitious contacts Y_{l}^{(μ) }of the subsystem S_{μ} (second case) (Figure 2). The operator Q′_{μ} defines an input fictitious contacts X_{i}^{(0)μ} of the external environment S′µ_{0} (first case). In fact, each of these operators symbolizes a procedure of assigning values to fictitious contacts. The values of the operators in Eq. (4) can be represented by a table of numbering fictitious contacts.
As an example, the Table 2 contains the numbers of fictitious contacts of the subsystem S_{µ1}, connected to contacts of the set [Y_{l}^{(j)}]_{μ}_{1} with the help of operators Q_{μ} and Q′_{μ}.
Table 2. The values of the operators Q_{μ} and Q^{′}_{μ}
Y_{l}^{(j)} (j,l) |
1,1 |
1,2 |
2,1 |
2,3 |
Qµ |
1 |
2 |
3 |
4 |
Q′µ |
1 |
2 |
3 |
4 |
$\left[\mathrm{X}_{1}^{(\mathrm{i})}\right]_{\mu}=\bigcup_{\mathrm{C}_{5} \in \mathrm{S}_{\mu}}\left\{\left[\mathrm{X}^{(\mathrm{j}, 0)}\right] \cup\left(\bigcup_{C_{\mathrm{k}} \notin \mathrm{S}_{\mu}}\left[\mathrm{X}^{(\mathrm{j}, \mathrm{k})}\right]\right)\right\}$ (5)
where, [X^{(j,k)}] is the set of input contacts of an element C_{j} connected to the corresponding output contacts of an element C_{k}, where C_{k}∉S_{μ}.
According to the Idempotent Law of union of sets, only different contacts X_{l}^{(j)} enter the set [X_{l}^{(j)}]_{μ}. For numbering of the fictitious contacts X_{i}^{(μ}^{)}, we introduce the pair of operators:
$\mathrm{X}_{\mathrm{i}}^{(\mu)}=\mathrm{P}_{\mu}\left(\mathrm{X}_{\mathrm{i}}^{(\mathrm{j})}\right)$
$Y_{1}^{(0) \mu}=P_{\mu}^{\prime}\left(X_{i}^{(j)}\right)$ (6)
The operators in Eq. (6) are called the numbering operators of the fictitious contacts of the subsystem S_{μ}. The operator P_{μ} defines the input fictitious contacts X_{i}^{(μ)} of the subsystem S_{μ} (second case) (Figure 2). The operator P′_{μ} defines the output fictitious contacts Y_{l}^{(0)μ} of the external environment S′_{µ0} (first case). In fact, each of these operators symbolizes a procedure of assigning values to the fictitious contacts. The values of the operators in Eq. (6) can be represented by the table of numbering the fictitious contacts.
Table 3. The values of the operators P_{μ} and P′_{μ}
X_{i}^{(j)} (j,i) |
1,1 |
2,1 |
2,2 |
2,3 |
Pµ |
1 |
2 |
3 |
4 |
P′µ |
1 |
2 |
3 |
4 |
As an example, the Table 3 contains the numbers of fictitious contacts of the subsystem S_{µ1}, connected to contacts of the set [X_{l}^{(j)}]_{μ1} with the help of operators P_{μ} and P′_{μ}.
Step 2. Construction of the operator of the elements connections. This step, in turn, should be considered for two cases: first case, a subsystem S_{μ} is considered as an independent system, just like the system S; second case, a subsystem S_{μ} is considered as an element of the system S.
Construction of the operator of the elements connections for first case. Denote this operator by R_{μ}.
Consider a subsystem Sm as an independent system. It means that all other elements of the system S including С_{0} represent the external environment S^{′}_{μ0} in relation to the subsystem S_{μ}. There are two types of connections within the elements of the subsystem S_{μ}.
The connections of first type are internal connections of input and output contacts of elements C_{j}, where С_{j}∈S_{μ}.
The connections of second type are connections of input and output contacts of the elements C_{j} of the subsystem S_{μ} to input and output contacts of the element S^{′}_{μ0}. The external environment S^{′}_{μ0} interacts with the subsystem S_{μ} through its input contacts X_{i}^{(0)μ}, which are connected to output contacts of elements C_{j}, where С_{j}∈S_{μ}, and through the output contacts Y_{l}^{(0)μ}, which are connected to input contacts of elements C_{j}, where С_{j}∈S_{μ}.
In the first case, the sets of the contacts [X(j) i]_{μ} 1 and [Y(j) 1]r 1 of the elements С_{j}, where С_{j}ÎS_{μ} are given. The operator of the elements connections R_{μ} for this case is equal to R.
In the second case, the subsystem S_{μ} has to connect with the subsystem S^{′}_{μ0} in the following manner: input contacts of the subsystem S^{′}_{μ0} to output contacts of the elements of the subsystem S_{μ} and output contacts of the subsystem S^{′}_{μ0} to input contacts of the elements of the subsystem S_{μ}. Thus, the operators Q′_{μ} in Eq. (4) and P′_{μ} in Eq. (6) define the input X_{i}^{(0)μ} and output Y_{l}^{(0)μ} contacts respectively:
$\mathrm{X}_{\mathrm{i}}^{(0) \mu}=\mathrm{Q}_{\mu}^{\prime}\left(\mathrm{Y}_{1}^{(\mathrm{j})}\right)$
$Y_{1}^{(0) \mu}=P_{\mu}^{\prime}\left(X_{i}^{(j)}\right)$ (7)
Finally, the operator R_{μ} is determined as:
$\mathrm{Y}_{1}^{(\mathrm{k})}=\mathrm{R}_{\mu}\left(\mathrm{X}_{\mathrm{i}}^{(\mathrm{j})}\right)$ (8)
where, the domain of the operator is the set:
$\left\{\left[\mathrm{X}_{\mathrm{i}}^{(0) \mu}\right]_{1}^{\mathrm{m}} \cup\left(\bigcup_{\mathrm{C}_{\mathrm{j}} \in \mathrm{S}_{\mu}}\left[\mathrm{X}_{\mathrm{i}}^{(\mathrm{j})}\right]_{1}^{\mathrm{m}}\right)\right\}$ (9)
and the codomain of the operator is the set:
$\left\{\left[\mathrm{Y}_{1}^{(0) \mu}\right]_{1}^{\mathrm{r}} \cup\left(\bigcup_{\mathrm{C}_{\mathrm{j}} \in \mathrm{S}_{\mu}}\left[\mathrm{Y}_{1}^{(\mathrm{k})}\right]_{1}^{\mathrm{r}}\right)\right\}$ (10)
Consider an algorithm of forming a set of codomains of the operator R_{μ}. Analyzing the expression in Eq. (9), we conclude that the domain of R_{μ} consists of three subsets.
The first subset. A contact $X_{1}^{(j)}$ of an element Cj, where Cj∈Sμ, is connected to a contact $\mathrm{Y}_{1}^{(\mathrm{k})}$ of an element Ck, where Ck∈Sμ. It can be written:
$\left[\mathrm{X}_{1}^{(\mathrm{j})}\right]_{\mu}=\bigcup_{C_{k} \in S_{\mu}}\left[\mathrm{X}^{(\mathrm{j}, \mathrm{k})}\right]$ (11)
In this particular case, it is evident the contact Y_{l}^{(k)} is defined as
$Y_{1}^{(k)}=R\left(X_{i}^{(j)}\right)$ (12)
Thus, the operator R_{μ} is equal to the operator R:
$\mathrm{R}_{\mu}=\mathrm{R}$ (13)
A procedure of forming the first subset in Eq. (11) of the subsystem S_{μ} consists of two steps.
Step 1. Consider all rows j (where С_{j}∈S_{μ}) and the pairs of numbers (k, l) in the Table 1. If the first number k is such that C_{k}∈S_{μ}, then the second one l denotes the number of the output contact of the element С_{k} connected to the input contact X_{i}^{(j)}.
Step 2. The value of the operator R_{μ} has to be determined, using the expression in Eq. (11).
The two-step operation has to be executed for all rows j of the Table 1, where С_{j}∈S_{μ}.
The second subset. A contact X_{i}^{(j)} of the element С_{j}, where С_{j}∈S_{μ}, is connected to the contact Y_{l}^{(k)} of the element C_{k}, where C_{k}∉S_{μ}. It can be written:
$\left[X_{1}^{(j)}\right]_{\mu}=\bigcup_{C_{k} \notin S_{\mu}}\left[X^{(j, k)}\right]$ (14)
In this case, it is necessary to form a fictitious contact Y_{l}^{(0)μ} on the border of the subsystem S_{μ}, using the operator P′_{μ} in Eq. (7). The procedure of forming the second subset in Eq. (14) of the subsystem S_{μ} consists of two steps.
Step 1. Сonsider all rows j (such as С_{j}∈S_{μ}) and the pairs of the numbers (k, l) in the Table 1. If the first number k is such that С_{k}∉S_{μ}, then the second number l is the number of the output contact of the element С_{k} connected to the input contact X_{i}^{(j)}.
Step 2. The operator R_{μ} has to be determined. It is equal to the operator P'_{μ} in Eq. (7). So,
$\mathrm{R}_{\mu}=\mathrm{P}_{\mu}^{\prime}$ (15)
Finally, the fictitious contact has to be found as:
$\mathrm{Y}_{1}^{(0) \mu}=\mathrm{R}_{\mu}\left(\mathrm{X}_{\mathrm{i}}^{(\mathrm{j})}\right)$ (16)
The third subset. Consider the third subset that consists of fictitious input contacts X_{i}^{(0)μ} of the external environment S′_{μ0}. The operator Q′_{μ} in Eq. (7) has to be used in order to determine a contacts Y_{l}^{(k)}, which is connected to the fictitious contacts X_{i}^{(0)μ}. It is easy to conclude that:
$\mathrm{Y}_{1}^{(\mathrm{k})}=\left(\mathrm{Q}_{\mu}^{\prime}\right)^{-1}\left(\mathrm{X}_{\mathrm{i}}^{(0) \mathrm{i}}\right)$ (17)
where, the operator (Q′_{μ})^{-1} is an inverse operator
Thus,
$\mathrm{R}_{\mu}=\left(\mathrm{Q}_{\mu}^{\prime}\right)^{-1}$ (18)
Note, the operator Q′_{μ} is a one-to-one operator.
Finally, the procedure of constructing the operator R_{μ} is defined by the expression:
$Y_{1}^{(k)}=\left\{\begin{array}{l}R\left(X_{i}^{(j)}\right) \text { for } X_{i}^{(j)} \in \bigcup_{C_{j} \in S_{\mu}, C_{k} \in S_{\mu}}\left[X^{(j, k)}\right] \\ P_{\mu}^{1}\left(X_{i}^{(j)}\right) \text { for } X_{i}^{(j)} \in \bigcup_{C_{j} \in S_{\mu}} \bigcup_{C_{k} \in S_{\mu}}\left[X^{(j, k)}\right] \\ \left(Q_{\mu}^{1}\right)^{-1}\left(X_{i}^{(0) \mu}\right) \text { for } X_{i}^{(0) \mu} \in\left[X_{i}^{(0) \mu}\right]_{1}^{m}\end{array}\right.$ (19)
As an example, the values of the operator R_{m} where m=m1 are given in Table 4. Like the Table 1, the Table 4 shows the values of the operator R_{μ1}. The row 0 in this table corresponds to the external environment S^{′}_{μ0}. The fictitious contacts X_{i}^{(0)μ} and Y_{l}^{(0)μ} correspond to the input and output contacts of S′_{μ0}, respectively. The rows 1 and 2 correspond to the elements С_{1} and С_{2}, respectively. The number of columns of this table is equal to the maximum number of input contacts among the С_{1}, С_{2} and S′_{μ0} and is equal to 4. At the intersection of rows and columns there are pairs of numbers (k, l) indicating the number of the element k (where C_{k}∈S_{μ} and S′_{μ0}) and the number of its output contact l, to which the input contact X_{i}^{(j)} is connected
The case, where a subsystem S_{μ} is considered as an independent system has been applied to the design of secure hardware systems. In the paper [15], hardware obfuscation technique on the base of proposed formalism is described.
Table 4. The operator R_{μ} for the subsystem S_{µ1}
j\i |
1 |
2 |
3 |
4 |
0 |
1,1 |
1,2 |
2,1 |
2,3 |
1 |
0,1 |
2,2 |
-,- |
-,- |
2 |
0,2 |
0,3 |
0,4 |
-,- |
Now, consider construction of the operator of the elements connections for the case where a subsystem S_{μ} is considered as an element of the system S (second case). In fact, that is an operator of subsystems connections or a two-level operator of the elements connections. Denote this operator by R_{II}. Similar to the operator R, determine the operator R_{II} as:
$\mathrm{Y}_{1}^{(\mathrm{v})}=\mathrm{R}_{\mathrm{II}}\left(\mathrm{X}_{\mathrm{i}}^{(\mathrm{\mu})}\right)$ (20)
where, the domain of the operator is the set of fictitious output contacts of subsystem $\mathrm{S}_{\mu} \bigcup_{\mu=\mu_{0}}^{\mu_{\mathrm{M}}}\left[\mathrm{X}_{\mathrm{i}}^{(\mu)}\right]_{\mathrm{i}}^{\mathrm{m}}$, and the codomain of the operator is the set of fictitious input contacts of subsystem $\bigcup_{\mu=\mu_{0}}^{\mu_{\mathrm{M}}}\left[Y_{\mathrm{i}}^{(\mu)}\right]_{1}^{\mathrm{r}}$.
If no elementary channel is connected to the contact Х_{i}^{(μ)}, then the operator R_{II} is not defined for this Х_{i}^{(μ)}.
Consider an algorithm of forming a set of codomains of the operator R_{II}. A procedure of the operator R_{II} is based on an analysis of a chain to which the contacts X_{i}^{(μ)} and Y_{l}^{(}^{n}^{)} belong. This procedure consists of two steps.
Step 1. For a fictitious contact X_{i}^{(μ)}, there is always a contact Х_{i}^{(j)} (where С_{j}∈S_{μ}), which can be determined using the expression:
$\mathrm{X}_{\mathrm{i}}^{(\mathrm{j})}=\mathrm{P}_{\mu}^{-1}\left(\mathrm{X}_{\mathrm{i}}^{(\mu)}\right)$ (21)
where, P_{μ}^{-1} is the inverse operator P_{μ} in Eq. (6).
The operator P_{μ}^{-1}(X_{i}^{(μ)}) is not a one-valued operator. Thus, there can be more than one contact Х_{i}^{(j)} for a fictitious contact X_{i}^{(μ)}, but it does not matter. If the fictitious contact X_{i}^{(μ)} corresponds to more than one contact Х_{i}^{(j)}, the output contact Y_{l}^{(k)}, where С_{k}∉S_{μ}, will always be the same.
Step 2. Definition of a fictitious output contact Y_{l}^{(}^{n}^{)}. If for a contact Х_{i}^{(j)} there exists an output contact Y_{l}^{(k)} of the component С_{k}, such that С_{k}∉S_{μ} and С_{k}∈S_{v}, then there always exists an operator:
$\mathrm{Y}_{1}^{(\mathrm{k})}=\mathrm{R}\left(\mathrm{X}_{\mathrm{i}}^{(\mathrm{j})}\right)$ (22)
Therefore, we define the required fictitious contact Y_{l}^{(}^{v}^{)} with the help of the operator in Eq. (4):
$\mathrm{Y}_{1}^{(\mathrm{v})}=\mathrm{Q}_{\mathrm{v}}\left(\mathrm{Y}_{1}^{(\mathrm{k})}\right)$ (23)
Thus,
$\mathrm{R}_{\mathrm{II}}=\mathrm{Q}_{\mathrm{v}}$ (24)
Consider a particular case, when k С_{0}, fictitious contacts Y_{l}^{(μ0)} and X_{i}^{(μ0)} of the subsystem S_{μ0} coincide with the corresponding contacts Y_{l}^{(0)} and X_{i}^{(0)} of the element С_{0}. Formally, the contacts Y_{l}^{(μ0)} and X_{i}^{(μ0)} are obtained as a result of applying the operators Q_{μ0} in Eq. (4) and P_{μ0} in Eq. (6), respectively. In this case, the value of the operator R_{II} is obtained using the operator:
$\mathrm{Y}_{1}^{(\mathrm{\mu} 0)}=\mathrm{Q}_{\mu 0}\left(\mathrm{Y}_{1}^{(0)}\right)$ (25)
Finally, the operator R_{II} is defined by the expression:
$Y_{1}^{(v)}=\left\{\begin{array}{l}Q_{v}\left(Y_{1}^{(k)}\right), \text { if } k \neq 0, C_{k} \in S_{v} \\ Y_{1}^{(?)}=Q_{\mu 0}\left(Y_{1}^{(0)}\right), \text { if } k=0\end{array}\right.$ (26)
The values of the operator R_{II} for the considered example are given in Table 5.where, Y_{l}^{(k)} = R[P_{μ}^{-1}(X_{i}^{(μ)})].
Table 5. The operator R_{II} for the considered system S
j\i |
1 |
2 |
3 |
4 |
0 |
1,2 |
3,1 |
5,4 |
-,- |
1 |
2,1 |
0,3 |
0,1 |
4,2 |
2 |
1,1 |
5,3 |
1,4 |
5,2 |
3 |
1,1 |
1,3 |
6,1 |
5,1 |
4 |
1,4 |
0,3 |
6,3 |
-,- |
5 |
2,3 |
0,2 |
2,2 |
6,2 |
6 |
3,2 |
4,1 |
1,1 |
0,3 |
Like the Table 1, the Table 5 shows the values of the operator R_{II}. The row number in the table corresponds to the subsystem numbers of the second level. The column number in the table correspond to the number of fictitious input contact of subsystem of the second level. At the intersection of the rows and the columns there are pairs of numbers (k, l) indicating the number of the subsystem k and the number of its fictitious output contact l, to which fictitious input contacts of subsystems are connected.
To solve many practical problems related to network systems, it is necessary to aggregate subsystems S_{m} into larger subsystems S^{3}_{μ} (third level), and those, in turn, into even larger ones, etc. In this case, it is necessary to consider a three-level R_{III} or four-level operator of the elements connections R_{IV}, and so on. Algorithmic implementation of operator construction for higher levels is invariant. Like the second level the construction of the subsystem’s connections scheme for third and larger level consists of two steps: definition of the fictitious contacts on the border of the subsystem S^{3}_{μ}; construction of the operator of the elements connections. The content of each of these steps for each level is the same. The construction of a multilevel aggregation scheme can be performed recurrently.
Table 6. The operator R_{III} for the considered example of the system S
j\i |
1 |
2 |
3 |
4 |
5 |
0 |
1,2 |
3,1 |
2,3 |
-,- |
-,- |
1 |
2,1 |
0,3 |
0,1 |
3,3 |
-,- |
2 |
1,1 |
1,4 |
0,2 |
3,2 |
-,- |
3 |
1,1 |
1,3 |
2,2 |
1,5 |
0,3 |
As an example, in the work the third level aggregation was performed. The subsystems S_{μ} of second level have been aggregated as follows: S^{3}μ_{0 }= {C_{0}}; S^{3}μ_{1 }= {Sμ_{1}, Sμ_{4}}; S^{3}μ_{2 }= {Sμ_{2}, Sμ_{5}}; S^{3}μ_{3 }= {Sμ_{3}, Sμ6}. Table 6 shows the values of the operator R_{III} for the considered example of the system S.
Thus, the application of the multilevel aggregation algorithm shows that, in comparison with the first level, at the third level of the system the number of elements has decreased by sixty-nine per cent and the number of connections has decreased by fifty-eight per cent.
It is easy to show that all elements connections schemes (one-level, two-level and three-level and so on) are equivalent from the following point of view. To each elementary channel connecting the contacts Х_{i}^{(j)} and Y_{l}^{(k)} = R(Х_{i}^{(j)}) in one-level elements connections scheme corresponds an elementary channel connecting these contacts in multilevel elements connections schemes.
This section is devoted to the description of the program implementation. The algorithm of multilevel aggregation of the network system has been programed. The program is written in the Java programming language and consists of fourteen classes, ten of which display the structure and functionality of the program, four are test classes. Simplified UML diagram with class names and fields is represented in Figure 3.
For the practical implementation of this task, it was necessary to construct classes that would reflect the structure and behavior of the system. The following structural parts were identified: a system that contains components; component; component port; connection between components. On the basis of this division such classes as SystemOfComponents, Component, Gate, Connection were constructed.
This system is a multilevel system, and to represent its levels the LevelOfSystem class was created. To store the layers of the system a collection was created in the SystemOfComponents class.
To create a hierarchical structure, the components were combined into subsystems. The component is both a component and an independent system. For the software implementation of this aspect, the inheritance mechanism was applied and, as consequence, the Component class was inherited from the LevelOfSystem class.
Figure 3. Simplified UML diagram with class names and fields
Each component has input and output ports which have a fundamental difference: only one connection can enter the input port, while several connections may leave the output port. However, at the same time, these ports have the same functions. Thus, to represent the ports of the component, the Gate class was created.
The next task was to represent the connection between two components. To solve it, the Connection class was created. To determine the beginning and the end of communication it was necessary to create a certain object that would store the component and port from which the connection leaves, and the component and port into which this connection enters. Thus, the following classes were created: the ConnectionElement class that stores the component and the ConnectionElementIn and ConnectionElementOut classes that inherit ConnectionElement class and store the input and output ports respectively. To create a connection between components, a mapping collection was created in the Connection class, the key of which is the ConnectionElementIn object, and the value is ConnectionElementOut.
As a result of the program implementation, the Tables 46 were obtained, representing the connections of the subsystems at each level of the system.
The formal transformations of the system structure model, using a multilevel aggregation, results in reduction in computational complexity and faster modeling. The efficiency of the approach is demonstrated using an example of solving the maximum flow problem [16]. The maximum flow problem belongs to the group of topological analysis problems whose purpose is to distribute network flows to achieve the maximum values of communication efficiency.
The maximum flow problem is formulated as follows: the maximum possible total value of the flow between the source and the sink has to be found for given network with established initial distribution of flows for graph edges and capacities. It means that the flow has to be increased if it has not reached the maximum value. The maximum flow value is equal to the sum of weights of the edges in the minimum cut in accordance with the theorem proved by Ford and Fulkerson, which is applied for solving the maximum flow problem [17].
The Ford-Fulkerson algorithm consists of the following steps.
(1) A path from the souse to the sink which is called an augmenting path has to be found in the given flow network.
(2) The maximum value of the flow in the augmenting path which is called the residual capacity has to be found. Each edge in the augmenting path must be labeled with the its capacity and residual capacity via slash notation. The flow value must be nonnegative and must not exceed the given capacity, but can be equal to it.
(3) If the flow is equal to the capacity of the edge, this edge is saturated. As a result, it cannot be considered in searching next augmenting path.
(4) Enumeration finishes when transfer from the source to the sink becomes impossible due to no augmenting paths exist.
(5) The value of the maximum flow is equal to the capacity of the minimum cut. It can be found as the sum of the flow values of the edges which are incoming to the sink.
The maximum flow of the network is calculated according to the formula:
$\mathbf{f}=\sum_{i=1}^{n} f_{i}$ (27)
where, n is the amount of the edges which are incoming to the sink; f_{i} is the flow value of the edge which is incoming to the sink.
The average length of the augmenting path is calculated according to the formula:
$\mathrm{L}_{\mathrm{avg}}=\frac{\sum_{i=1}^{\mathrm{n}} \mathrm{L}_{\mathrm{i}}}{\mathrm{n}}$ (28)
where, n is the amount of the augmenting paths; L_{i} is the length of the augmenting path.
Implementation of the approach is shown below. To evaluate the efficiency of the approach proposed, an experiment has been performed. For each of three levels of structural system model the maximum flow has been calculated. Consider this experiment in detail.
First, find the maximum flow for the initial network (first level) applying the Ford-Fulkerson algorithm. For the initial network (Figure 1), we assign the capacity values of the channels, which connect the components. We transform the Table 1 of the elements connections into the Table 7, where the channel capacities are indicated by the third values.
The graph of the system was constructed (Figure 4), where the source combines the output contacts of the external environment and the sink combines the input contacts of the external environment. The weight of each edge is equal to the capacity of the corresponding channel.
The search of the maximum flow was fulfilled using the Ford-Fulkerson algorithm. An augmenting path from the source to the sink was chosen on each iteration. Each edge was labeled with capacity and maximum possible flow via slash notation. The enumeration of the possible augmenting paths finished when transfer from the source to the sink became impossible in consequence of the saturation of the edges of the graph. After that, the maximum flow of the network was found as a result of the summation of the flow values of the edges which are incoming to the sink.
Table 7. The first level elements connections with capacity values
i\j |
1 |
2 |
3 |
4 |
0 |
1,2,20 |
6,1,25 |
10,4,10 |
-,- |
1 |
3,1,15 |
2,2,10 |
-,- |
-,- |
2 |
0,3,30 |
0,1,75 |
8,1,15 |
-,- |
3 |
1,1,15 |
4,1,15 |
10,2,10 |
-,- |
4 |
1,1,10 |
2,3,5 |
3,2,25 |
10,1,10 |
5 |
6,2,15 |
1,1,5 |
2,1,5 |
-,- |
6 |
5,1,15 |
12,1,5 |
9,1,25 |
-,- |
7 |
2,3,15 |
0,3,45 |
8,2,25 |
-,- |
8 |
0,3,60 |
12,4,10 |
-,- |
-,- |
9 |
4,2,5 |
0,2,45 |
10,3,15 |
-,- |
10 |
9,2,15 |
3,3,10 |
12,3,15 |
-,- |
11 |
6,3,5 |
12,2,10 |
7,1,10 |
-,- |
12 |
11,1,10 |
1,1,10 |
0,3,50 |
-,- |
Table 8. Result of the graph traversal
№ |
Augmenting path |
Residual capacity |
Amount of the traversed edges |
1 |
Source–2–1–Sink |
10 |
3 |
2 |
Source–2–5–6–Sink |
5 |
4 |
3 |
Source–2–4–3–1–Sink |
5 |
5 |
4 |
Source–9–6–Sink |
20 |
3 |
5 |
Source–9–6–11–12–10–Sink |
5 |
6 |
6 |
Source–9–10–Sink |
5 |
3 |
7 |
Source–9–10–3–1–Sink |
5 |
5 |
Figure 4. Graph of the first level of the system
Thus, the maximum flow of the network was found according to the formula in Eq. (27):
$\mathrm{f}_{1}=20+25+10=55$
The seven augmenting paths were traversed during algorithm implementation. The average length of the path was found according to the formula in Eq. (28):
$\mathrm{L}_{\mathrm{avg} 1}=\frac{3+4+5+3+6+3+5}{7}=4,14$
By analogy with the first level, the maximum flow was found for the second and third levels.
As a result of using this method, the number of the elements and the number of the connections between the elements have decreased. Moreover, the number of graph traversal iterations has declined by fifty-seven per cent in finding the maximum network flow at the third level of the system. In addition to this, the average length of the augmenting path from the source to the sink has decreased by thirty-six per cent.
The final results of the computational experiment are given in the Table 9.
Summarizing:
(1) The value of the maximum flow for each of three levels of system structural model is the same. This is an indirect confirmation of the equivalence of multilevel structural model transformations, as well as the correctness of algorithmic and software implementation.
(2) Multilevel structural model transformations result in the dimension reduction of a network system presentation and, consequently, a decrease in the execution time of computational procedures. The results of the evaluation of the efficacy of the composition method: the number of the element of the system decreased by 69%; the number of the connections among the elements of the system decreased by 58%; the number of the graph traversal iterations decreased by 57%; average length of the path from the source to the sink decreased by 36%.
Table 9. Results of the evaluation of the effectiveness of the composition method
Parameters |
First level |
Second level |
Third level |
Result: decreased by |
The number of the element of the system |
13 |
7 |
4 |
69% |
The number of the connections between elements of the system |
38 |
26 |
16 |
58% |
The number of the graph traversal iterations |
7 |
4 |
3 |
57% |
Average length of the path from the source to the sink |
4,14 |
3 |
2,67 |
36% |
Maximum flow |
55 |
55 |
55 |
- |
In this paper, we examined the technique of formal transformations of structural models of complex systems and its application. We demonstrated, that:
(1) Multilevel structural model transformation techniques provide a simpler representation of network systems while preserving the topological properties of the higher dimension system.
(2) The results of the work can be used to study and solve problems associated with streaming processes in networks, when throughput or other parameter changes over time and the time of system modeling is a critical parameter.
(3) The formal transformations of the structural models of complex systems with the purpose of reducing the dimension of the system, can be leveraged in the multi-tier telecommunication network management model. This will allow the management system to make decisions in real time to identify bottlenecks in a network, meet customer needs for rapid deployment of new services, meet strict quality of service requirements.
(4) The application of the object-oriented concept in the program implementation allows making the transformation techniques invariant to the way of a formal presentation of a system structural model.
Within the framework of the future study, we can present such ideas:
(1) Development of a generator of structural models with specified topological characteristics of large-scale network systems. This will allow evaluating the effectiveness of proposed technologies to solve various optimization problems associated with large networks.
(2) In various problems of managing complex network systems, time is a critical parameter. These problems include detecting bottlenecks, parallelism, as well as mutual exclusion, deadlocks etc. Therefore, the study of the application of equivalent multilevel topological transformations for these problems is an important task.
[1] Kolaczyk, E.D. (2009). Statistical analysis of network data: Methods and Models. Springer, New York. https://doi.org/10.1007/978-0-387-88146-1
[2] Newman, M. (2010). Networks: An Introduction. Oxford University Press. https://doi.org/10.1093/acprof:oso/9780199206650.001.0001
[3] Denning, P.J., Buzen, J.P. (1978). The operational analysis of queuing network models. Computing Surveys, 10(3): 225-261. https://doi.org/10.1145/356733.356735
[4] Lu, J., Chen, G., Ogorzalek, M., Trajkovic, L. (2013). Theory and applications of complex networks: Advances and challenges. Proceedings of the IEEE International Symposium on Circuits and Systems, Beijing, China, pp. 2291-2294. https://doi.org/10.1109/ISCAS.2013.6572335
[5] Landi, P., Minoarivelo, O.H., Brännström, Å., Hui, C., Dieckmann, U. (2018). Complexity and stability of ecological networks: A review of the theory. Population Ecology, 60(4): 319-345. https://doi.org/10.1007/s10144-018-0628-3
[6] Bohan, D., Dumbrell, A., Woodward, G., Jackson, M. (2018). Next Generation Biomonitoring: Part 1. Advances in Ecological Research, Academic Press.
[7] Shortle, J.F., Mark, B.L., Gross, D. (2009). Reduction of closed queueing networks for efficient simulation. ACM Transactions on Modeling and Computer Simulation, 19(3). https://doi.org/10.1145/1540530.1540531
[8] Liu, J.X., Vorst, N.V. (2012). Realizing large-scale interactive network simulation via model splitting. Proceedings of the 26th Workshop on Principles of Advanced and Distributed Simulation (PADS 2012), Zhangjiajie, China, pp. 3-12.
[9] MacKay, R.S. (2011). Hierarchical aggregation of complex systems. Proceedings of the ECCS’11, Vienna, Austria.
[10] MacKay, R.S., Robinson, J.D. (2018). Aggregation of Markov fows I: Theory. Philosophical Transactions of The Royal Society A Mathematical Physical and Engineering Sciences. https://doi.org/10.1098/rsta.2017.0232
[11] Hackl, J., Adey, B.T. (2017). Generation of Spatially Embedded Random Networks to Model Complex Transportation Networks. In: Caspeele R., Taerwe L., Proske D. (eds) 14th International Probabilistic Workshop. Springer, Cham, pp. 217-230. https://doi.org/10.1007/978-3-319-47886-9_15
[12] Mesarović, M., Mako, D., Takahara, Y. (1977). Theory of Hierarchical Multilevel Systems. New York: Academic.
[13] Grossman, P. (1995). Discrete Mathematics for Computing. Palgrave, London. https://doi.org/10.1007/978-1-349-13908-8
[14] Gorbachov, V., Batiaa, A.K., Ponomarenko, O., Romanenkov, Y. (2018). Formal transformations of stuctural models of complex network systems. Proceedings of the IEEE 9th International Conference on Dependable Systems, Services and Technologies DESSERT′2018, Kyiv, Ukraine, pp. 473-477.
[15] Gorbachov, V., Batiaa, A.K., Ponomarenko, O., Kulak, E. (2018). Securing computer hardware on the base of reference monitor obfuscation. Proceedings of the IEEE International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T′2018), Kharkiv, Ukraine, pp. 406-410.
[16] Cormen, T., Leiserson, C., Rivest, R., Stein, C. (2009). Introduction to Algorithms, Third Edition, The MIT Press.
[17] Ford L.R., Fulkerson D.R. (2009) Maximal Flow Through a Network. In: Gessel I., Rota GC. (eds) Classic Papers in Combinatorics. Modern Birkhäuser Classics. Birkhäuser Boston. https://doi.org/10.1007/978-0-8176-4842-8_15