Volume 16 Number 3
June 2019
Article Contents
Alexander Tselykh, Vladislav Vasilev and Larisa Tselykh. Management of Control Impacts Based on Maximizing the Spread of Influence. International Journal of Automation and Computing, vol. 16, no. 3, pp. 341-353, 2019. doi: 10.1007/s11633-018-1167-2
Cite as: Alexander Tselykh, Vladislav Vasilev and Larisa Tselykh. Management of Control Impacts Based on Maximizing the Spread of Influence. International Journal of Automation and Computing, vol. 16, no. 3, pp. 341-353, 2019. doi: 10.1007/s11633-018-1167-2

Management of Control Impacts Based on Maximizing the Spread of Influence

Author Biography:
  • Alexander Tselykh received the Ph. D. degree in applied mathematics from Rostov State University, Russia in 1990 and became a full professor of computer science in 2000. His research interests include expert systems, decision making, fuzzy sets, mathematical methods and algorithms. E-mail: ant@sfedu.ru ORCID iD: 0000-0001-6956-5315

    Vladislav Vasilev received the Ph. D. degree in applied mathematics from Rostov State University, Russia in 1997. His research interests include optimization methods, math modelling, and computational mathematics. E-mail: vsvasilev@sfedu.ru ORCID iD: 0000-0001-7485-8614

    Larisa Tselykh received the Ph. D. degree in economics from Rostov State University of Economics, Russia in 2006. Her research interests include expert systems, decision making, mathematical methods and algorithms. E-mail: l.tselykh58@gmail.com (Corresponding author) ORCID iD: 0000-0001-5663-1563

  • Received: 2017-08-04
  • Accepted: 2018-11-14
  • Published Online: 2019-02-15
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures (4)  / Tables (4)

Metrics

Abstract Views (809) PDF downloads (16) Citations (0)

Management of Control Impacts Based on Maximizing the Spread of Influence

Abstract: The choice of fulcrums for control of socio-economic systems represented by directed weighted signed graphs is a topic of current interest. This article proposes a new method for identifying nodes of impact and influential nodes, which will provide a guaranteed positive system response over the growth model. The task is posed as an optimization problem to maximize the ratio of the norms of the accumulated increments of the growth vector and the exogenous impact vector. The algorithm is reduced to solving a quadratic programming problem with nonlinear restrictions. The selection of the most effective vertices is based on the cumulative gains of the component projections onto the solution vector. Numerical examples are provided to illustrate the effectiveness of the proposed method.

Alexander Tselykh, Vladislav Vasilev and Larisa Tselykh. Management of Control Impacts Based on Maximizing the Spread of Influence. International Journal of Automation and Computing, vol. 16, no. 3, pp. 341-353, 2019. doi: 10.1007/s11633-018-1167-2
Citation: Alexander Tselykh, Vladislav Vasilev and Larisa Tselykh. Management of Control Impacts Based on Maximizing the Spread of Influence. International Journal of Automation and Computing, vol. 16, no. 3, pp. 341-353, 2019. doi: 10.1007/s11633-018-1167-2
    • Management decisions in complex systems are implemented through the application of control impacts with the expectation of achieving maximum results. The choice of fulcrums for control impacts is a complex topic of current interest.

      Socio-economic systems are poorly formalized. The representation of complex systems in the form of graphs helps to formalize the relationships between actors in the system. Because of the complexity of both the actors and the links between them, simple methods for determining the major factors of the system in decision support problems are not applicable. The most significant properties of socio-economic systems that distinguish them from social systems are 1) the multiplicity and complexity of the links, 2) the directed and coercive nature of the links between factors, and 3) heterogeneity of factors (usually not having cognate parameters).

      Much research has been devoted to the identification of influential nodes in social networks using various models of information spread (diffusion[1], entropy[2], etc.). It is assumed that the availability of information may be of interest to the user and may prompt the user to take certain actions, for example, to persuade a buyer to make a purchase or a voter to vote for a particular candidate. In this case, the spread of information is not aimed at inducing the action of a particular individual; rather it targets a wide range of individuals. In addition, relationships in social networks are based on equality. Therefore, traditional methods for determining influential nodes in social networks are based, in essence, on various topological characteristics of networks expressed through various metrics (centrality, etc.).

      As noted in survey articles [1, 3], the current scientific research in the field pertaining to identification of influential nodes on graphs is “in its infant stage”[3]. The main research in this area seeks solutions to problems related to undirected unweighted graphs that represent relationships in social networks. Some solutions, e.g., [47], take into account the weight on a graph′s edge, which is a specially computed metric that reflects the characteristics of the node (e.g., the total number of node links and number of input or output node links). Studies in the area of identifying influential nodes on directed signed weighted graphs are in the rudimentary stage of positing the problem. Simplified techniques using known algorithms (the directionality and weight on the edges are simply ignored) do not provide satisfactory results since some of the underlying definitional semantics are not retained.

      Control theory, solves the problem of selecting pinning nodes and allows complete control of the whole network so that it can be directed towards a desired goal[8]. The model is based on controlling the behavior of the system. Therefore, there must be a fundamental understanding of the system′s operation, including knowledge of the general form of the equation that describes the behavior of the system. In addition, the system should operate according to the concept of Kalman state controllability which presumes the stability of the system. For socio-economic systems, such stable conditions are not possible.

      In addition, a solution of the problem of identifying qualifying factors that can be used in the socio-economic system was proposed and made use of the theory of fuzzy cognitive maps[911]. The basis of this approach is the system stationary state model, which implies that the system is in a certain achieved state space, wherein the main characteristics of the system do not change with time or change insignificantly. For models considered in fuzzy cognitive map theory, a stationary solution exists but is trivial. Namely, the problem of conserving the stationary (previously achieved) state of the system is solved. Therefore, the factors of the system obtained as a result of solving such a problem, although significant, are only responsible for maintaining the achieved state of the system.

      The evolution of a system requires leaving the stationary state. To do this, it is necessary to develop another control model that will represent the future direction of the progress of the system and will also spur the development of new algorithms. These evolutionary reasons and considerations have motivated this paper′s proposal of a new algorithm that uses the control model (the growth model and barrier-breakthrough model).

      Influence in socio-economic systems, unlike influence in social networks, is a compelling factor for particular actors within the system. For example, the issuance of an executive order is mandatory and must be executed. However, it does not guarantee the expected result (e.g., a sharp increase in labor productivity). Thus, the task of choosing an object of control impact is important to ensure the efficiency of the system. It is assumed that when a control impact is applied to such an object (objects), we will get the specified response. The main issues to be addressed are 1) the choice of the appropriate model, 2) ranking of the impact and influence factors, and 3) the choice of factors of the directed control impact providing a certain guaranteed result. To determine and select the key factors presented in the form of graph vertices, two models are considered most characteristic for the transfer of control impacts: a delay model and a growth model. To ensure the achievement of the guaranteed result, an effectiveness control model has been developed with some restrictions to the model factors.

      The primary contribution of this paper is the proposal of a new algorithm based on maximizing the spread of influence. This algorithm identifies influential factors in socio-economic systems that act as effective fulcrums for control impacts. Socio-economic systems are represented by a directed weighted signed graph with cause-and-effect links on the edges. The proposed algorithm operates in novel way by taking into account the direction of edges in computing the influence metric.

      In this article, we present a solution (for the growth model) by restricting the non-negativity of the resulting factor, which is the system′s response. The task is posed as an optimization problem to maximize the ratio of the norms (or the ratio of the squared norms) of accumulated increments of the growth vector and the exogenous impact vector. At the same time, within the barrier-breakthrough model under consideration, it is necessary to maintain high increments of the vertex indices in the next step (or several subsequent steps). For the graph of socio-economic systems, the formulated task is to find the vector of control actions, which leads to the maximum growth of the indices of the target factors under the restriction of non-negativity. The control factors and target factors are not set by the decision-makers (experts) but are determined by solving a system of linear equations (SLE). In the experiments, we demonstrate the ability of the proposed algorithm to determine effective controls through the use of examples of real-world graph models that simulate management tasks in a socio-economic system.

    • The task of identifying the most influential nodes has been the focus of many studies. It is possible to single out two distinct directions for solving such tasks. The first one is based on information distribution models, while the second one is based on control theory models. The former is widely used to solve the problem of spreading influence in social networks. Their action is generally aimed at the breadth of reach of the audience. The latter is used in technical systems where stability and controllability are necessary conditions for operation. We consider both areas of research because these methods can be used to solve the problems encountered in the use of control models for socio-economic systems.

      We considered articles[4, 1215] for ways of representing the first direction. In their fundamental work, Kempe et. al.[4] approached the task of maximizing influence as a problem of combinatorial optimization. They proposed to solve the problem using a standard greedy algorithm. In subsequent studies, other researchers considered the solution to this problem using various methods, including heuristic algorithms, with various modifications to the models proposed in [4] and using different strategies[14, 15]. The models considered in [4, 1215] are based on diffusion-type propagation processes. In these processes, determining a precise solution is impossible, the space of high gradients is smoothed out. In all models, a stationary solution is determined, which in the case of the models presented in [12, 13] requires the fulfilment of the stability condition. If stochastic matrices are used, the stability conditions are satisfied. However, stochasticity restricts these approaches. In [14, 15], the model used is similar to the concept of Markov chains, and the task of determining the minimum number of vertices for counter-influence is solved. The system′s response here means the activation of a subset of nodes without taking into account the accumulation of information and the power of influence. In contrast to this approach, in the effectiveness models, only a few vertices with the maximum increase in the state index are determined, instead of the maximum coverage of the vertices. In [12, 13], the model can be classified as a control model. The model in [12] is reduced to an optimization problem, where the objective function depends on both the control vector and the state vector. In the problem, restrictions are expressed as inequalities. In addition, in the study [12], the sum of the squared norms of the influence and response vectors is minimized, reduced to solutions such as the uniform distribution of the response over the vertices. This is the opposite of the task of finding the few vertices that are most effective in their response.

      The studies [8, 1619] were considered to represent the second direction (solving the problem of identifying the most influential nodes), which is based on control theory models. This approach uses an evolution equation to obtain a stationary solution when the stability conditions are fulfilled, its own functions are determined. The control involves impulse actions during the few first steps over a small number of vertices. The impact itself is proportional to the difference between the achieved state and the desired stationary state. If the maximum eigenvalues of the matrices have very large values ($\sim 10^3 \div 10^6$), this approach is not applicable. The model in question is designed to identify the minimum number of driver nodes to achieve complete control over system dynamics. At the same time, such a model allows for the problem formulation in the form of minimizing the norm of the control impact over a given norm of the output response. In this case, it is necessary that the stability conditions of the adjacency matrix be satisfied, while the network must satisfy Kalman′s controllability rank criterion. The requirement that the stability conditions for this model be fulfilled is of crucial importance, which makes applying this approach to barrier-breakthrough models or effectiveness models impossible.

      In [20], the classical control system represented by the graph model is considered. The study compares two approaches: the search for a stationary autonomous solution and the search for the response of system $\vec{x}$ under the exogenous impact $\vec{e}$. The authors note that although the vector $\vec{e}$ can be an arbitrary impact, in this study a single impact vector is assigned to all vertices of the network. For the task of searching for the few most influential vertices, the exogenous assignment of vector $\vec{e}$ can degenerate into a problem of exponential complexity that reduces to taking a brute force approach.

      In our study, we present a new control approach for a complex domain system, based on the growth model under restrictions to the resulting increments. The proposed approach provides the maximum increments of the resultant indices in one or several steps. In this setting, the stationary solution is of no interest, since it may not exist. As a consequence, stability conditions are not required. The problem mathematically defined here can be mapped as quadratic programming problems with non-linear restrictions. The solutions of these problems contain pairs of control and response vectors with respect to the maximum ratio of the norms. The rest of this article is organized as follows. Section 3 presents the main results describing effectiveness control models by directed weighted signed graphs, and the proposed methods for solving the resulting optimization problems. Section 4 presents the experimental results. Section 5 provides an analysis of the results that were obtained. Section 6 completes the work by drawing conclusions and outlining directions for further work.

    • Allowing for the above considerations, we believe that the most appropriate approach to building models that take into account the specifics of the environment of socio-economic systems are cognitive maps. A socio-economic system is represented by an oriented signed weighted graph having cycles that represent cause-effect relationships. The vertices correspond to the factors of the system that have certain parameters. The indices of the vertices can be both externally and internally influenced. It is assumed that the external influence on a vertex parameter does not change the parameter itself, it only causes a change in the indices of the connected vertices. The spread of internal influences is determined by the weights of the arcs, which can be positive and negative.

      To solve management problems in a socio-economic system, two models can be considered:

      1) A growth model (model 1), which is presented in the following form:

      $ {x_j} = {u_j} + \delta \sum\limits_{i = 1}^n {{a_{ij}}{x_i}} $

      where $x_{j}$ is the increment value of the vertex index $v_{j}$, $u_{j}$ is the control impact to vertex $v_{j}$, $\delta$ is the damping factor, $a_{ij}$ is the weight of the arc from the vertex $v_{i}$ to vertex $v_{j}$ on the interval $-1\leq a_{ij} \leq 1$, $x_i$ is the increment value of the vertex index $v_{i}$.

      2) An after-effect model (model 2), described by the following equation:

      $ x_{j} = \sum\limits_{i=1}^n{a_{ij}} \left( u_{i} + \delta \sum\limits_{k=1}^n{a_{ki} x_{k}} \right) $

      where $x_j$ is the increment value of the vertex index $v_j$, $a_{ij}$ is the weight of the arc from the vertex $v_{i}$ to vertex $v_{j}$ on the interval $-1\leq a_{ij} \leq 1$, $u_{i}$ is the control impact to vertex $v_{i}$, $\delta$ is the damping factor, $a_{ki}$ is the weight of the arc from the vertex $v_{k}$ to vertex $v_{i}$ on the interval $-1\leq a_{ki} \leq 1$, $x_{k}$ is the increment value of the vertex index $v_{k}$.

      A graphical interpretation of these models is considered for a simple model consisting of 3 vertices (model factors) and two arcs (cause-effect relationships) connecting the vertices in series and is shown in Figs.1(a) and 1(b), respectively. The following notations are used in Figs.1(a) and 1(b): $t$ are the instants of time for the states of the model, $x$ are the increments of the vertex indices at time $t$, $u$ are the control impacts to the vertex, $a$ is the weight of the arc of the connecting vertex, the subscript indicates the vertex number, and the superscript indicates the time $t$. The relevant computed parameter values for the vertices are shown in Tables 1 and 2.

      Figure 1.  Graphical interpretation for the growth model (a) and after-effect model (b)

      $ {t_0}$ $ {t_1}$ $ {t_2}$ $ {t_3}$
      $ {{{v}}_1}$ $ {{{x}}_1^{(0)}}$ $ {{{x}}_1^{(1)}= {{u}}_1^{(0)}}$ $ {{{x}}_1^{(2)}= {{u}}_1^{(1)}}$ $ {{{x}}_1^{(3)}= {{u}}_1^{(2)}}$
      $ {{{v}}_2}$ $ {{{x}}_2^{(0)}}$ $ {{{x}}_2^{(1)}= {{u}}_2^{(0)}+{{a}}_{12} {{x}}_1^{(0)}}$ $ {{{x}}_2^{(2)}= {{u}}_2^{(1)}+{{a}}_{12} {{x}}_1^{(1)}}$ $ {{{x}}_2^{(3)}= {{u}}_2^{(2)}+{{a}}_{12} {{x}}_1^{(2)}}$
      $ {{{v}}_3}$ $ {{{x}}_3^{(0)}}$ $ {{{x}}_3^{(1)}= {{u}}_3^{(0)}+{{a}}_{23} {{x}}_2^{(0)}}$ $ {{{x}}_3^{(2)}= {{u}}_3^{(1)}+{{a}}_{23} {{x}}_2^{(1)}}$ $ {{{x}}_3^{(3)}= {{u}}_3^{(2)}+{{a}}_{23} {{x}}_2^{(2)}}$

      Table 1.  Solution for the growth model

      $ {t_0}$ $ {t_1}$ $ {t_2}$ $ {t_3}$
      $ {{{v}}_1}$ $ {{{x}}_1^{(0)}}$ $ {{{x}}_1^{(1)}= 0}$ $ {{{x}}_1^{(2)}= 0}$ $ {{{x}}_1^{(3)}= 0}$
      $ {{{v}}_2}$ $ {{{x}}_2^{(0)}}$ $ {{{x}}_2^{(1)}= {{a}}_{12} {{u}}_1^{(0)}}$ $ {{{x}}_2^{(2)}= {{a}}_{12} {{u}}_1^{(1)}}$ $ {{{x}}_2^{(3)}= {{a}}_{12} {{u}}_1^{(2)}}$
      $ {{{v}}_3}$ $ {{{x}}_3^{(0)}}$ $ {{{x}}_3^{(1)}= {{a}}_{23} {{u}}_2^{(0)}}$ $ {{{x}}_3^{(2)}= {{a}}_{23} \left( {{u}}_2^{(1)}+{{a}}_{12} {{x}}_1^{(0)} \right)}$ $ {{{x}}_3^{(3)}= {{a}}_{23} \left( {{u}}_2^{(2)}+{{a}}_{12} {{x}}_1^{(1)} \right) }$

      Table 2.  Solution for after-effect model

      The graphical interpretation above shows that for these models, two types of influences are taken into account: a) direct impacts to the factors of the model (graph vertices) and b) the cause-effect influence exerted by one factor on another, spread along the graph arcs. Let us consider the behaviour of the models at the corresponding instants of time. Under model 1, the perfect impact on the $i$-th factor at time $t_0$ is taken into account directly in the computation of the increment of the $i$-th factor at time $t_1$, the impact at $t_1$ is taken into account at $t_2$, etc. Under model 2, the implemented impact to the $i$-th factor at $t_0$ is taken into account indirectly through the arc weight in computing the increment of the $j$-th factor index at time $t_1$. The change in the vertex index through the cause-effect relationship (the second type of influence) is taken into account in a different way. Under model 1, the change in the $i$-th vertex index at time $t_1$ is taken into account as the indirect increment of the index of the preceding vertex $k$ by the weight of the connected arc at time $t_0$. Under model 2, the change in the $i$-th vertex index at time $t_2$ is taken into account as the indirect increment of the index of the preceding vertex $k-1$ by the weights of the arcs connected in series at $t_0$. Thus, under the second model, the spread of influence of both types is delayed by one step in comparison with the first model.

      Based on the description of the models, the following conclusions can be made regarding their application to socio-economic systems:

      1) Model 1 can be used in responding to emergencies or in controlling production processes. The second model is more amenable to socio-economic systems and can be used more frequently for management decision making.

      2) The models describe increments in factor (vertex) indices ${{x}}$, not absolute values of factors (vertices). Therefore, the incremental values can be either positive or negative. The restriction of $x\geq 0$ for the resulting increment lies in the need to achieve only positive index increments.

    • Definition 1. The system model is represented by a graph (network) consisting of nodes $\{ v_1, v_2, \cdots, v_j \}$, in a certain activated state at time instants $\{ t_1, t_2, \cdots, t_j \}$, and of directed arcs having weights $a_{ij}$ and connecting node $i$ with node $j$.

      Here, the weight of directed arc $a_{ij}$ is defined on the interval $-1\leq a_{ij} \leq 1$ and represents a causal relationship from node $i$ to node $j$, where node $i$ is the cause, and the node $j$ is the effect.

      Remark 1. Control impacts $\{ u_1, u_2, \cdots, u_j \}$ denote the time-dependent control signals of the nodes $\{ v_1, v_2, \cdots, v_j \}$ over the graph and additional increments to the vertex indices.

      Remark 2. The changes (increments) to the indices of the nodes state $\{ x_1, x_2, \cdots, x_j \}$, called the system response, occur under the influence of the control impacts $\{ u_1, u_2, \cdots, u_j \}$, spread along the directed arcs over the graph and are defined by equation:

      $ \begin{split} & {{D}} \left( {{E}} + \theta_1 {{A}} + \theta_2 {{A}}^2 + \dots + \theta_p {{A}}^p \right) {{D}}^{-1} {{x}} = \\ & \qquad \quad \;{{D}} \left( \phi_0 {{E}} + \phi_1 {{A}} + \phi_2 {{A}}^2 + \dots + \phi_q {{A}}^q \right){{u}} \end{split} $

      where ${{D}}$ is the mapping matrix and ${{E}}$ is the identity matrix, $\theta_0, \theta_1, \cdots, \theta_p $ and $ \phi_0, \phi_1, \cdots, \phi_q $ are the coefficients of the increment components of indices ${{x}}$ and of control impacts ${{u}}$, ${{A}}$ is the transpose of the adjacency matrix, and $p$ and $q$ are finite orders for aftereffect.

      Definition 2. The optimal control impact is the normalized control vector ${{u}}$ that ensures the maximum response of the system. It is necessary to determine the direction of the change of the vertex indices allowing maximum amplification and to determine the control impact providing this maximum amplification at least at the next step or at several subsequent steps.

      Mathematically, optimal control $\{ u_1, u_2, \cdots, u_j \}$ maximizes the ratio of norms (or ratios of squared norms) of the vector of accumulated growth of the increments of vertex indices and the external influence vector:

      $ \frac {\left( {{x}}, {{x}} \right)}{\left( {{u}}, {{u}} \right)} \rightarrow {\max}. $

      Remark 3. The optimal control impact with restrictions to the non-negativity of its components is the vector of control impacts which produces the maximum growth of indices of the target factors under the restriction ${{u}}\geq 0$.

      Remark 4. The optimal control vector $\left\{ u_1, u_2, \cdots,\right.$$ \left. u_j \right\}$ is an ordered set of absolute values of control vector components that maximizes the absolute values of the components of the response vector $\{ x_1, x_2, \cdots, x_j \}$.

      Remark 5. The optimal system response $\left\{ x_1,x_2, \cdots,\right.$$ \left. x_j \right\}$ forms an ordered set of absolute values of the response vector components generated by the optimal control vector $\{ u_1, u_2, \cdots, u_j \}$.

      Remark 6. The conditions for selecting optimal control and optimal response vectors for the system are formed based on an analysis of the solution obtained and are expressed by the addition of restrictions to the components.

    • The task is to find a vector (vectors) of external influences that maximizes the cumulative growth of the vertex indices. In this formulation, the task is connected to the problem of determining the resonant properties of the system represented by the adjacency matrix for an oriented weighted signed graph, namely, finding the eigenvalues and eigenvectors of the adjacency matrix. In the general case, one should expect complex eigenvalues and complex eigenvectors components. If the elements of the adjacency matrix are real numbers, then the eigenvalues and eigenvectors decompose into pairs of complex adjoint numbers and pairs of vectors with complex adjoint components. This makes it difficult to interpret the results as indices of the socio-economic system.

      The proposed approach is as follows. To evaluate the maximization of the vector value (the accumulated growth of the vertex indices), let us introduce a certain vector norm. Then, the main task is posed as maximizing the ratio of norms (or ratio of squared norms) of the accumulated increments of the growth vector and exogenous impact vector. Such a scalar formulation reduces to symmetrization of the matrix with respect to the base quadratic form. The eigenvalues and components of the eigenvectors of this symmetric matrix are real numbers. Moreover, the eigenvectors of a symmetric matrix corresponding to different eigenvalues are orthogonal.

      The statement of the problem allows for a generalization of conditional optimization, i.e., it requires finding a solution that satisfies certain restrictions. However, since vectors differing by only a multiplicative factor have the same direction, the restrictions should not express conditions on the components of the desired vectors, but attribute the required vector to a certain (linear) spectrum generated by a set of given vectors. We propose to investigate the possibility of constructing an algorithm for solving the problem of conditional optimization, which is as efficient as the acceleration of the Gram-Schmidt orthogonalization process[21]. This is in comparison with the solution of a quadratic programming problem with nonlinear restrictions. Since the directions of interest are often those corresponding to first several eigenvalues with the largest values, acceptable accuracy of the solution of the problem can be achieved.

      Consider the graph $G= \langle {V, E} \rangle$ for the socio-economic system, where $V= \{ V_1, V_2, \cdots, V_N \}$ is a set of vertices and $E \in V\times V$ is a set of arcs. The graph is determined by the adjacency matrix ${{A}}^{\rm{T}}= \parallel a_{j, i} \parallel_{n}$, where $a_{j, i}$ is the weight of the arc from vertex $V_i$ to vertex $V_j$ on the interval $-1\leq a_{i, j} \leq 1$.

      Let the socio-economic system at time $t_0, t_1, \cdots, t_j, \cdots$ be characterized by an increment of indices ${{x}}^{(0)},{{x}}^{(1)}, \cdots,$$ {{x}}^{(j)}, \cdots$ and have control impacts ${{u}}^{(0)}, {{u}}^{(1)}, \cdots, {{u}}^{(j)}, \cdots$. Let the value of the index increment ${{x}}^{(0)}$ be determined by control impact ${{u}}^{(0)}$:

      $ {{x}}^{(0)} = \alpha_0 {{D}} {{u}}^{(0)}, $

      (1)

      the value of index $x^{(1)}$ is determined by control impacts ${{u}}^{(0)}$ and ${{u}}^{(1)}$:

      $ {{x}}^{(1)} = {{D}} \left(\alpha_0 {{u}}^{(1)} + \alpha_1 {{A}} {{u}}^{(0)} \right), $

      (2)

      the value of index ${{x}}^{(2)}$ is determined by control impacts ${{u}}^{(0)}$, ${{u}}^{(1)}$ and ${{u}}^{(2)}$:

      $ {{x}}^{(2)} = {{D}} \left(\alpha_0 {{u}}^{(2)} + \alpha_1 {{A}} {{u}}^{(1)}+ \alpha_2 {{A}} {{A}} {{u}}^{(0)} \right), $

      (3)

      etc., where ${{D}}$ is the mapping matrix and $\alpha_1, \alpha_2, $$\cdots, {\alpha}_j $ are constant attenuation coefficients. In general,

      $ \begin{split} {{x}}^{(j)} = & {{D}} \left(\alpha_0 {{u}}^{(j)} + \alpha_1 {{A}} {{u}}^{(j-1)}+ \alpha_2 {{A}}^2 {{u}}^{(j-2)} + \cdots \right. \\ & \left. + \alpha_j {{A}}^{j} {{u}}^{(0)}\right). \end{split} $

      (4)

      If ${{D}}$ is nonsingular and $\alpha \neq 0$, then (1) – (4) are invertible. Substituting vector ${{u}}^{(0)}$ from (1) in (2), we get

      $ {{x}}^{(1)} - \alpha_0^{-1} \alpha_1 {{D}} {{A}} {{D}}^{-1}{{x}}^{(0)} = \alpha_1 {{D}} {{u}}^{(1)}. $

      (5)

      Substituting vectors ${{u}}^{(0)}$ and ${{u}}^{(1)}$ from (1) and (5) in (3), we get

      $ \begin{aligned} {{x}}^{(2)} & - \frac{\alpha_1}{\alpha_0} {{D}} {{A}} {{D}}^{-1} \left({{x}}^{(1)} - \frac{\alpha_1}{\alpha_0} {{D}} {{A}} {{D}}^{-1} {{x}}^{(0)} \right) -\\ & \frac{\alpha_1}{\alpha_0} {{D}} {{A}} {{A}} {{D}}^{-1} {{x}}^{(0)} = \alpha_0 {{D}} {{u}}^{(2)}, \end{aligned} $

      etc. In general:

      $ \begin{aligned} {{x}}^{(j)}+ & \beta_1 {{D}} {{A}} {{D}}^{-1} {{x}}^{(j-1)} + \beta_2 {{D}} {{A}}^2 {{D}}^{-1} {{x}}^{(j-2)} + \dots +\\ & \beta_{j} {{D}} {{A}}^{j} {{D}}^{-1} {{x}}^{(0)} = {{D}} {{u}}^{(2)}. \end{aligned} $

      Consider a model of finite orders $p$ and $q$ for after-effect (by analogy with the Box-Jenkins models[22, 23]):

      $ \begin{aligned} {{x}}^{(j)} + & \theta_1 {{D}} {{A}} {{D}}^{-1} {{x}}^{(j-1)} + \theta_2 {{D}} {{A}}^2 {{D}}^{-1} {{x}}^{(j-2)} + \dots +\\ & \theta_{p} {{D}} {{A}}^{p} {{D}}^{-1} {{x}}^{(j-p)} =\\ & {{D}} \left(\phi_0 {{u}}^{(j)} + \phi_1 {{A}} {{u}}^{(j-1)}+ \dots + \phi_{q} {{A}}^{q} {{u}}^{(j-q)} \right) \end{aligned} $

      where $ \theta_0, \theta_1, \cdots, \theta_p $ and $ \phi_0, \phi_1, \cdots, \phi_q $ are the coefficients of the component increments of indices ${{x}}$ and of impacts ${{u}}$, respectively.

      For the solution in the form of stationary vectors of impacts ${{u}}^{(j)} = {{u}}$ and of indices ${{x}}^{(j)} = {{x}}$, we get

      $ \begin{split} & {{D}} \left({{E}} + \theta_1 {{A}} + \theta_2 {{A}}^2 + \dots + \theta_{p} {{A}}^{p} \right) {{D}}^{-1}{{x}}=\\ & \;\;\quad\quad {{D}} \left(\phi_0 {{E}} + \phi_1 {{A}} + \phi_2 {{A}}^2 + \cdots + \phi_{q} {{A}}^{q} \right) {{u}}. \end{split} $

      (6)

      The optimal control impact is called impact ${{u}}$ which maximizes the ratio of the squared norm of vertex indices ${{x}}$ to the squared norm of the impact vector ${{u}}$:

      $ \frac {\left( {{x}}, {{x}} \right)}{\left( {{u}}, {{u}} \right)} \rightarrow {\max}. $

      (7)

      If the matrices on the left-hand side of (6) are nonsingular, then the problem of unconditional optimization (7) is equivalent to the following spectral problem, and we have

      $ \frac {\left( {{B}} {{u}}, {{u}} \right)}{\left( {{u}}, {{u}} \right)} \rightarrow {\max} $

      where ${{B}}={{C}}^{\rm{T}} {{C}}$, and

      $ \begin{aligned} {{C}} & = {{D}} \left({{E}} + \theta_1 {{A}} + \theta_2 {{A}}^2 + \dots + \theta_{p} {{A}}^{p} \right)^{-1} \phi_{0} {{E}} +\\ & \quad \phi_1 {\bf{A}} + \phi_2 {{A}}^2 + \dots + \phi_{q} {{A}}^{q}. \end{aligned} $

      Matrix ${{B}}$ is symmetric and has a fixed sign.

      Previously, we considered a delayed system[24], where ${{D}} = {{E}}$, $p = 2$, $\theta_1 = 0$, $\theta_2 = -\delta$, $q = 1$, $\phi_{0} = 0$, $\phi_{1} = 1$, ${{C}} = \left( {{E}} - \delta {{A}}^2 \right)^{-1} {{A}}$.

      The problem of conditional optimization with restrictions on control impacts can be solved. Let ${{v}}_{1}, {{v}}_{2}, \cdots, {{v}}_{m}$ be linearly independent vectors and the set of linear combinations $ {{v}} = \xi_1 {{v}}_1 + \xi_2 {{v}}_2 +\cdots + \xi_{m} {{v}}_{m}$ be a linear manifold generated by the vectors, where $\xi_1 \geq 0$, $\xi_2 \geq 0, \cdots $, $\xi_{m} \geq 0$ are nonnegative numbers.

      If the decomposition of vector ${{u}}$ into vectors ${{v}}_1, {{v}}_2, \cdots, {{v}}_{m}$ is nonnegative, then vector ${{u}}$ belongs to the linear manifold, and we have:

      $ {{u}} = c_1 {{v}}_1 + c_2 {{v}}_2 + \dots + c_{m} {{v}}_{m} $

      (8)

      where $c_1 \geq 0, c_2 \geq 0, \cdots, c_{m} \geq 0$. Under the conditions of (8), we can determine the decomposition coefficients by solving this system of equations:

      $ \begin{array}{*{20}{l}} {\left(\!\!\!\!{\begin{array}{*{20}{c}} {({v_1},{v_1})} & {({v_1},{v_2})}\!\!\!&\!\!\!\ldots \!\!\!&\!\!\!{({v_1},{v_m})}\\ {({v_2},{v_1})}\!\!\!&\!\!\!{({v_2},{v_2})}\!\!\!&\!\!\!\ldots \!\!\!&\!\!\!{({v_2},{v_m})}\\ \vdots \!\!\!&\!\!\!\vdots \!\!\!&\!\!\!\ddots \!\!\!&\!\!\!\vdots \\ {({v_m},{v_1})}\!\!\!&\!\!\!{({v_m},{v_2})}\!\!\!&\!\!\!\ldots\!\!\!&\!\!\!{({v_m},{v_m})} \end{array}}\!\!\!\!\right)\!\!\!\left(\!\!\!\!{\begin{array}{*{20}{c}} {{c_1}}\\ {{c_2}}\\ \vdots \\ {{c_m}} \end{array}}\!\!\!\!\right) \!\! = \!\!\left(\!\!\!\!{\begin{array}{*{20}{c}} {({{{v}}_1},{{u}})}\\ {({{{v}}_2},{{u}})}\\ \vdots \\ {({{{v}}_m},{{u}})} \end{array}}\!\!\!\!\right)\!.} \end{array}\!\!\!\!\! $

      (9)

      The SLE matrix is nonsingular with respect to the Gram matrix[21, 25], it exists by virtue of the linear independence of vectors ${{v}}_1, {{v}}_2, \cdots, {{v}}_{m}$.

      Let ${{V}}$ be a matrix whose columns are the vectors ${{v}}_1, {{v}}_2, \cdots, {{v}}_{m}$, then (9) reduces the SLE to the form:

      $ {{V}}^{\rm{T}} {{V}} {{c}} = {{V}}^{\rm{T}} {{u}} $

      where ${{c}} = \left( c_1 c_2 \dots c_m \right)^{\rm{T}}$ is the vector of coefficients. Thus, the condition of non-negativity of the decomposition coefficients reduces to a system of inequalities that represents the restriction:

      $ {{c}} = \left({{V}}^{\rm{T}} {{V}}\right)^{-1} {{V}}^{\rm{T}} {{u}} \geq {{0}}. $

      Since the optimal direction is determined, the nonlinear non-quadratic programming problem becomes

      $ \frac {\left( {{B}} {{u}}, {{u}} \right)}{\left( {{u}}, {{u}} \right)} \rightarrow {\max}, \qquad \left({{V}}^{\rm{T}} {{V}}\right)^{-1} {{V}}^{\rm{T}} {{u}} \geq {\bf{0}} $

      where ${{B}}$ is a symmetric non-negative definite matrix. The problem can be reduced to an equivalent quadratic programming problem with nonlinear restrictions:

      $ -\left( {{B}} {{u}}, {{u}} \right) \rightarrow {\min}, \quad \left({{u}}, {{u}}\right) = 1, \quad \left( {{V}}^{\rm{T}} {{V}}\right)^{-1} {{V}}^{\rm{T}} {{u}} \geq {\bf{0}}. $

      The Lagrange function for this problem has the form:

      $ \begin{split} L = & -\left( {{B}} {{u}}, {{u}} \right) + {\lambda} \left(\left({{u}}, {{u}}\right) - 1\right)- \\ & \left(\left({{V}}^{\rm{T}} {{V}}\right)^{-1} {{V}}^{\rm{T}} {{u}}, {{\mu}} \right) \rightarrow {\min} \end{split} $

      where ${\bf{\lambda}}$ and ${\bf{\mu}} = \left( \mu_{1}, \mu_{2}, \cdots, \mu_{m} \right)^{\rm{T}}$ are Lagrange multipliers. Taking into account [26], we obtain the necessary conditions to solve for the minimum of this system of nonlinear equations:

      $ \left\{\begin{aligned} & {{\nabla _u}L = \!-\! \left( {{{B}} + {{{B}}^{\rm{T}}}} \right){{u}} \!+\! 2\lambda {{u}} - {{V}}{{\left( {{{{V}}^{\rm{T}}}{{V}}} \right)}^{ - 1}}{\bf{\mu }} \!=\! {\bf{0}}}\\ & {{\nabla _\lambda }L = \left( {{{u}},{{u}}} \right) - 1 = 0}\\ & {{\nabla _\mu }L = - {{\left( {{{\widetilde {{V}}}^{\rm{T}}}\widetilde {{V}}} \right)}^{ - 1}}{{\widetilde {{V}}}^{\rm{T}}}{{u}} = {\bf{0}}.} \end{aligned}\right. $

      (10)

      We have the linearized system of equations:

      $ \left\{\begin{aligned} & { - \left( {{{B}} + {{{B}}^{\rm{T}}}} \right){{u}} + 2\lambda {{u}} - {{V}}{{\left( {{{{V}}^{\rm{T}}}{{V}}} \right)}^{ - 1}}{{\mu }}-}\\ & \quad\;\quad { \left( {{{B}} \!+\! {{{B}}^{\rm{T}}}} \right)\left( {\widehat {{u}} \!-\! {{u}}} \right) \!+\! 2\lambda \left( {\widehat {{u}} - {{u}}} \right) \!+\! 2\left( {\hat \lambda \!-\! \lambda } \right){{u}}}\\ & { {{V}}{{\left( {{{{V}}^{\rm{T}}}{{V}}} \right)}^{ - 1}}\left( {\widehat {{\mu }} - {{\mu }}} \right) = {{0}}}\\ & {\left( {{{u}},{{u}}} \right) - 1 + 2\left( {{{u}},\widehat {{u}} - {{u}}} \right) = 0}\\ & { - {{\left( {{{\widetilde {{V}}}^{\rm{T}}}\widetilde {{V}}} \right)}^{ - 1}}{{\widetilde {{V}}}^{\rm{T}}}{{u}} - {{\left( {{{\widetilde {{V}}}^{\rm{T}}}\widetilde {{V}}} \right)}^{ - 1}}{{\widetilde {{V}}}^{\rm{T}}}\left( {\widehat {{u}} - {{u}}} \right) = {\bf{0}}} \end{aligned}\right. $

      (11)

      and the transformation reduces (11) to the form:

      $ \left\{\begin{aligned} & {2\lambda \widehat {{u}} \!-\! \left( {{{B}} \!+\! {{{B}}^{\rm{T}}}} \right)\widehat {{u}} + 2\hat \lambda {{u}} \!-\! \widetilde {{V}}{{\left( {{{\widetilde {{V}}}^{\rm{T}}}\widetilde {{V}}} \right)}^{ - 1}}\widetilde {{\mu }} = 2\lambda {{u}}}\!\!\!\!\\ & {2\left( {\widehat {{u}},{{u}}} \right) = \left( {{{u}},{{u}}} \right) + 1}\\ & {{{\left( {{{\widetilde {{V}}}^{\rm{T}}}\widetilde {{V}}} \right)}^{ - 1}}{{\widetilde {{V}}}^{\rm{T}}}\widehat {{u}} = {\bf{0}}.} \end{aligned}\right. $

      (12)

      Suppose the optimal directions ${{u}}_1, {{u}}_2, \cdots, {{u}}_k$ are defined in sequence such that each successive ${{u}}_i$ is orthogonal to all the previous ${{u}}_1, {{u}}_2, \cdots, {{u}}_{i-1}$. Then, the quadratic programming problem reduces to the form:

      $ \begin{aligned} & -\left( {{B}} {{u}}, {{u}} \right) \rightarrow {\min}\\ & {{U}}^{\rm{T}}_{i-1} {{u}}_{i} = {\bf{0}}, \quad \left({{u}}_{i}, {{u}}_{i}\right) = 1, \quad \left( {{V}}^{\rm{T}} {{V}}\right)^{-1}{{V}}^{\rm{T}} {{u}}_{i}\geq {{0}} \end{aligned} $

      where ${{U}}_{i-1}$ is a matrix whose columns are orthonormal vectors ${{u}}_1, {{u}}_2, \cdots, {{u}}_{i-1}$. The Lagrange function for this problem has the form:

      $ \begin{aligned} & {\rm{L}}_{i} = -\left( {{B}} {{u}}_{i}, {{u}}_{i}\right) + \left({{U}}^{\rm{T}}_{i-1} {{u}}_{i}, {\lambda}_{i-1}\right) + {\lambda}_{i} \left(\left({{u}}_{i}, {{u}}_{i}\right) - 1\right)- \\ & \quad\quad \left( \left({{V}}^{\rm{T}} {{V}}\right)^{-1} {{V}}^{\rm{T}} {{u}}_{i}, {{\mu}}_{i} \right) \end{aligned} $

      where ${\bf{\lambda}}_{i-1} = ( \lambda_1, \lambda_2, \cdots, \lambda_{i-1})^{\rm{T}}$, $\lambda_{i}$ and ${\bf{\mu}}_{i}$ are Lagrange multipliers. We obtain the necessary conditions to solve for the minimum of this system of nonlinear equations:

      $ \left\{\begin{aligned} & {{\nabla _u}{L_i} = - ({{B}} + {{{B}}^{\rm{T}}}){{{u}}_i} + {{{U}}_{i - 1}}{{{\lambda }}_{{\bf{i}} - {\bf{1}}}} + 2{\lambda _i}{{{u}}_i}}-\\ & \quad\;\;\quad\quad { {{V}}{{\left( {{{{V}}^{\rm{T}}}{{V}}} \right)}^{ - 1}}{{{\mu }}_{\bf{i}}} = {{0}}}\\ & {{\nabla _\lambda }{L_i} = {{U}}_{{\rm{i}} - 1}^{\rm{T}}{{{u}}_{\bf{i}}} = {\bf{0}}}\\ & {{\nabla _{\lambda ,i}}{L_i} = ({{{u}}_i},{{{u}}_i}) - 1 = 0}\\ & {{\nabla _\mu }{L_i} = - {{\left( {{{\widetilde {{V}}}^{\rm{T}}}\widetilde {{V}}} \right)}^{ - 1}}{{\widetilde {{V}}}^{\rm{T}}}{{{u}}_i} = {\bf{0}}.} \end{aligned}\right. $

      After transformation, the linearized system of equations has the form:

      $ \left\{\begin{aligned} & {2{\lambda _i}{{\widehat {{u}}}_i} - \left( {{{B}} + {{{B}}^{\rm{T}}}} \right){{\widehat {{u}}}_i} + {{{U}}_{i - 1}}{{\bf{\lambda }}_{{{i}} - {\bf{1}}}} + 2{{\hat \lambda }_i}{{{u}}_i}} -\\ & \quad\quad\;\;{ \widetilde {{V}}{{\left( {{{\widetilde {{V}}}^{\rm{T}}}\widetilde {\bf{V}}} \right)}^{ - 1}}{{\widehat {{\mu }}}_i} = 2{\lambda _i}{{\widehat {{u}}}_i}}\\ & {{{U}}_{i - 1}^{\rm{T}}{{\widehat {{u}}}_i} = {\bf{0}}}\\ & {2\left( {{{\widehat {{u}}}_i},{{{u}}_i}} \right) = \left( {{{{u}}_i},{{{u}}_i}} \right) + 1}\\ & {{{\left( {{{\widetilde {{V}}}^{\rm{T}}}\widetilde {{V}}} \right)}^{ - 1}}\widetilde {{V}}{{\widehat {{u}}}_i} = {\bf{0}}.} \end{aligned}\right. $

      The following Algorithms for determining the prevailing controls implements the actions mentioned above (Algorithms 1 and 2).

      Algorithm 1. Algorithm for determining a unique prevailing control

      Require: ${{B}}$, ${{V}}$, ${{u}}$, $\lambda$, ${\bf{\mu}}$ are initial approximations

      Ensure: $\left(\hat{\lambda}, \hat{{{\mu}}}\right)$, $\hat{{{u}}}$ is the optimal control

      1) repeat

      2)  Solve SLE: ${{y}} = 2 \left(2\lambda {{E}} - ({{B}} + {{B}}^{\rm{T}})\right)^{-1} {{u}}$

      3)  $\hat{\lambda} = \lambda - \displaystyle\frac{1}{2} \frac{{\left(\left({{u}}, {{u}}\right)+1\right)}}{{\left({{u}}, {{y}}\right)}}$

      4)  $\hat{{{u}}} = \left(\lambda - \hat{\lambda}\right) {{y}}$

      5)  Solve SLE: $\tilde{{{V}}}\left(\tilde{{{V}}}^{\rm{T}} \tilde{{{V}}}\right)^{-1} \hat{\mu} = 2 (2\lambda {{E}} - ({{B}} + $$ {{B}}^{\rm{T}})) + 2\left(\hat{\lambda} - \lambda\right) {{u}}$

      6) until $\parallel \hat{{{u}}} - {{u}} \parallel < \varepsilon.$

      Algorithm 2. Algorithm for determining numerous prevailing controls

      Require: ${{B}}$, ${{V}}$, the initial approximation ${{u}}_{i}$, ${\bf{\lambda}}_{i-1}$, $\lambda_{i}$, ${\bf{\mu}}_{i}$

      Ensure: ${{U}}_{k}$ is a two-dimensional array whose columns are the optimal controls.

      1) for i = 2 to $k$

      2)  repeat

      3)    Solve SLE: ${{y}} = 2 \left(2{{E}} - ({{B}} + {{B}}^{\rm{T}})\right)^{-1} {{u}}_{i}$, ${{Z}} = -\left(2{{E}} - ({{B}} + {{B}}^{\rm{T}})\right)^{-1} {{U}}_{i-1} $

      4)    Solve SLE:

      $\begin{array}{*{20}{l}} {\left( {\begin{array}{*{20}{c}} {{\lambda _i} - {{\hat \lambda }_i}}\\ {{\lambda _{i - 1}}} \end{array}} \right) = {{\left( {\left( {\begin{array}{*{20}{c}} {{{U}}_{i - 1}^{\rm{T}}}\\ {{{u}}_i^{\rm{T}}} \end{array}} \right)\left( {\begin{array}{*{20}{c}} {{Z}} & {{y}} \end{array}} \right)} \right)}^{ - 1}}\left( {\begin{array}{*{20}{c}} {\bf{0}}\\ {({{u}},{{u}}) + 1} \end{array}} \right)} \end{array}$

      5)    $\hat{{{u}}} = \left(\lambda_{i} - \hat{\lambda}_{i}\right) {{y}} + {{Z}} \lambda_{i}$

      6)    Solve SLE: ${\tilde{{V}}}\left({\tilde{{{V}}}}^{\rm{T}}{\tilde{{V}}}\right)^{-1} \hat{{\bf{\mu}}}_{l} = ( 2\lambda {{E}} - ({{B}} +$$ {{B}}^{\rm{T}})) \hat{{{u}}}_{l} - {{Z}} \lambda_{i} - 2\left(\hat{\lambda}_{i} - \lambda_{i}\right) {{{u}}}_{i}$

      7)  until $\parallel \hat{{{u}}}_{i} - {{u}}_{i} \parallel < \varepsilon$

      8)  Matrix expansion ${{U}}_{i}$ by column ${{u}}_{i}$

      9) end for.

    • A numerical experiment for finding the effective components of effective controls under the imposed restriction of non-negativity increments in the values of factors is considered. The example is of cognitive models represented as directed weighted signed graphs with cause-effect relations on the graph edges and having cycles. The feasibility of the proposed algorithm has been tested with real-world datasets. In this article, the following datasets are used for the numerical experiment: a) a 75 × 75 matrix – a cognitive map from [27]; b) the 72 × 72 adjacency matrix from [28]; c) the 25 × 25 adjacency matrix from [29]; d) the 24 × 24 adjacency matrix from [30]. Graphs are represented by adjacency matrices with the corresponding characteristics (Table 3).

      Indicators of computed results by influence (responses) Indicators of computed results by impact
      $ {N}$ vertices $ {r_{i, j}^2}$ Cumulative $ {r_{i, j}^2}$ $ {N}$ vertices $ {v_{i, j}^2}$ Cumulative $ {v_{i, j}^2}$
      Matrix a): $ {75\times 75}$ on 411 arcs of cumulative weight 216.5
      47 0.216 827 0.216 827 37 0.145 136 0.145 136
      51 0.201 887 0.418 714 6 0.123 891 0.269 027
      52 0.171 254 0.589 968 34 0.108 118 0.377 145
      25 0.129 799 0.719 767 55 0.107 73 0.484 875
      Matrix b): $ {72\times 72}$ on 586 arcs of cumulative weight 290.6
      62 0.292 181 0.292 181 49 0.098 086 0.098 086
      50 0.286 346 0.578 527 10 0.079 896 0.177 982
      68 0.172 491 0.751 018 44 0.071 564 0.249 546
      54 0.141 029 0.892 047 4 0.052 477 0.302 023
      Matrix c): $ {25\times 25}$ on 35 arcs of cumulative weight 35.0
      16 0.263 177 0.263 177 15 0.415 907 0.415 907
      12 0.233 274 0.496 451 6 0.119 845 0.535 751
      23 0.156 316 0.652 767 11 0.077 496 0.613 247
      17 0.112 739 0.765 506 12 0.064 801 0.678 048
      Matrix d): $ {24\times 24}$ on 41 arcs of cumulative weight 41.0
      1 0.136 237 0.136 237 21 0.218 18 0.218 18
      5 0.134 855 0.271 092 12 0.130 548 0.348 729
      2 0.124 934 0.396 025 3 0.084 498 0.433 226
      10 0.124 094 0.520 119 4 0.084 498 0.517 724

      Table 3.  Selected model factors with corresponding index values

      The numerical experiment was performed using model (7), for which the relationship between the influences and responses is shown by (6) with the following parameters: ${{D}} = {{E}}$, $p = 1$, $\theta_1 = -\delta$, $q = 0$, $\phi_{0} = 1$, $\phi_{1} = 1$, ${{C}} = ( {{E}} - \delta {\bf{A}}^{-1})$. The solution is provided by Algorithm 1 under the restrictions of $x\geq 0$.

      The results show that the functioning of the system is determined by one or two leading directions that very strongly prevail over the others. Sorting the values $R_1, R_2, \cdots, R_n$ that were obtained shows a significant lag on the value of the first vector from the value of the second $(3 \times 10^3)$. In line with the structure of the matrix, the effect on any factor produces the same growth vector, though with different scales, because of the strong interrelationships between the factors. It is sufficient to select one controlled factor (maximum). For more effective control, it was decided to select factors whose indices have a large lag from the others, providing more than 50% of the maximum growth (Table 3). The results show the possibility of selecting an effective control for the socio-economic system represented by the cognitive model (Fig.2).

      Figure 2.  Values of the influences ①, effectiveness index ②, cumulative effectiveness index ③, impacts ④, ensuring controllability index ⑤, and cumulative ensuring controllability index ⑥ for 4 matrices using models: a, b, c, and d.

    • Five different criteria were applied to evaluate our approach:

      1) Applicability for a specific domain

      The research showed the applicability of our approach based on the system theory for the analysis of directed weighted signed graphs representing cognitive models for social and economic systems. The method does not impose restrictions on the signs or ranges of weights of the edges or the directions of the edges. The matrices used in the SLE solutions are positive semidefinite, and symmetric.

      2) Feasibility

      The matrices used in the solution of the problem are matrices of second order partial differential equations of quadratic forms, i.e., they are symmetric and sign definite when constructed. Under the simple restriction of ${{u}}\geq {\bf{0}}$, Newtonian convergence was observed, i.e., the number of iterations remained within 5–7. Since the SLE is solved by direct methods, the algorithm has shown that it works with matrix dimensions up to $n\leq 100$. Models whose matrices contain single loops can produce singular matrices when determining the SLE. Even in the case of matrix singularity in models with single loops at the vertices of the graph, the corresponding SLE can be solved using the regularization of the problem by Tikhonov and Arsenin[31].

      3) Output format

      As a result of the application of the algorithm, the selection of the effective components and corresponding effective large impacts representing the key vertices is performed. This is mapped to a user-specified value of the equivalence level for the system as a whole. The number of vertices was reduced to a reasonable number of vertices and connections, which allows the graph model to reach an acceptable level of informativeness for the decision maker (expert).

      4) Complexity of the solution obtained

      The computational complexity of the algorithm is $O(n^3)$. The ratio of the norms (vector) of changes $\displaystyle\frac{{\varepsilon_{i}}} {{\varepsilon_{0}}}$ for the 6 cognitive models in which the eigenvalues of the matrices have very large values ($\sim 10^3 \div 10^6$) is shown in (Fig.3 (a)). The decision time of the algorithm is polynomial and is a fraction of a second (Fig. 3 (b)).

      Figure 3.  Algorithm complexity parameters the value of the ratios of norms (vector) of changes $\displaystyle\frac{{\varepsilon_{i}}}{{\varepsilon_{0}}}$ under 6 cognitive models decision time

      5) Comparison with other algorithms

      The results of comparing the proposed algorithm with the most prominent algorithms from [8, 1219] are presented in Table 4. Thus, the proposed algorithm expands the class of solved problems in line with the above criteria.

      Criterion Proposed algorithm Algorithms (in Section 2)
      1) Special properties of the adjacency matrix Special properties of the adjacency matrix are not given. The adjacency matrix must satisfy the stability conditions (all eigenvalues must be within the unit circle of the complex plane).
      2) Number field All computational results (eigenvalues, eigenvectors, and solutions of optimization tasks) are real numbers. In the general case, the solution is expressed in complex numbers. An imaginary part of a complex number is ignored.
      3) Formulation of the problem Finding the most effective solution for progress of the system. Finding a stationary solution.

      Table 4.  Comparison of algorithms

      6) Quality

      The employed method of multipliers[26] is characterized by the fact that at each iteration the problem is solved in the primal variables, which ensures the accuracy of the solution of the primal equations. With dual variables, accuracy is not required, only an indication of the activity or inactivity of the restrictions. The exchange of information between the primal and dual tasks (at least in the case of simple restrictions) makes the process of entering the area of unconditional optimization fast.

    • In this article, we considered the problem of maximizing the positive response of the main factors of a system. The challenge was to find a small but reasonable set of factors initiating impacts in order to maximize the response of the main factors of the system. Computation by the algorithm was reduced to the solution of a quadratic programming problem with nonlinear restrictions under the sequential computation of the optimal directions of the impacts ${{u}}_1, {{u}}_2, \cdots, {{u}}_k$, and then computing the positive increments of the indices ${{x}}_1, {{x}}_2, \cdots, {{x}}_j$. The selection of the most effective vertices was based on the accumulation of the projected components by the solution vector.

      The experimental results show that the algorithm achieves the required efficiency with respect to the minimum set of vertices (up to 4) necessary to achieve the maximum response of the system. We also showed that the algorithm provides a solution for models with a strong predominance of the selected leading factor, which is manifested as a large lag on the maximum eigenvalue relative to the other eigenvalues. Although the proposed algorithms have shown effectiveness in the selection of influence factors associated with response factors in cases of single-factor and two-factor models, in experiments with other cases they did not have a guaranteed solution. This is because the restrictions must be compatible in a well-defined statement of the problem.

      We showed that the problem is solvable in polynomial time. Using our algorithm, the choice of nodes as points of application of control impacts provides excellent performance and significantly improves the ability of decision makers to make control decisions using socio-economic models of the real world. The results shown in this article have good prospects for practical application. One possible direction for further research is the development of effective algorithms, which will not only be scalable for large networks but will also have a guaranteed solution. The study of the problem under different, more realistic restrictions is another challenging direction for future work.

    • This research was supported by the Russian Foundation for Basic Research (No. 17-01-00076).

Reference (31)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return