THE RECONSTRUCTION OF THE ADJACENCY MATRIX IN THE GIVEN PARAMETERS FOR THE ORIGINAL GRAPH MODEL WITH A DETERMINISTIC CAUSALITY
Abstract
In this study, a new approach to the creation of a system graph, which has a given transfer properties, does not lose effective relations between the vectors of effects and responses, which achieves the maximum ratio of norms (or the ratio of squared norms), and implements these ex-treme conditions on the transfer matrix. The problem of adjacency matrix reconstruction for the given parameters is solved in order to construct the initial graph model. This problem in the gen-eralized statement was not solved and is novel. The solution of this problem on the basis of a com-bination of the system theory, linear and matrix algebra allows to formalize the dependence of the influence of network characteristics to the properties of the network, which makes it possible to design a network with specified properties. We apply the concept of a transfer matrix to the prob-lem of maximizing the spread of influence in the socioeconomic system. The optimal change prob-lem is based on the minimization of the matrix norm consistent with the vector norms of impacts and responses. This formulation of the problem makes it possible to construct a graph of the sys-tem with the given transfer properties. The algorithm implementing this approach is computation-ally efficient with harness of O(m3 ), where m is the number of pairs of given vectors, because it is based on the 2nd order Lagrange multiplier method and the conjugate direction method. Since the problems of quadratic programming with linear constraints are solved, the criterion for obtaining a solution is not to achieve the required accuracy, but to enter the domain of unconditional optimi-zation (no constraint is not violated, Lagrange multipliers corresponding to the constraints in the form of inequalities are non-negative), which is much faster than in the general nonlinear pro-gramming problems.
References
2. Bertsekas D.P. Constrained Optimization and Lagrange Multiplier Methods. Belmont, MA: Athena Scientifi, 1996.
3. Comellas F., Diaz-Lopez J. Spectral reconstruction of complex networks, Phys. A Stat. Mech. its Appl., 2008, Vol. 387, No. 25, pp. 6436–6442.
4. Fan J., Cheng J. Matrix completion by deep matrix factorization, Neural Networks, 2018, Vol. 98, pp. 34-41.
5. Kaplan D. Structural Equation Modeling (2nd ed.): Foundations and Extensions. 2455 Teller Road, Thousand Oaks California 91320 United States: SAGE Publications, Inc., 2009.
6. Kavanagh R.J. The application of matrix methods to multi-variable control systems, J. Franklin Inst., 1956, Vol. 262, No. 5, pp. 349-367.
7. Kolaczyk E.D. Statistical Analysis of Network Data. New York, NY: Springer New York, 2009.
8. Kosko B. Fuzzy cognitive maps, Int. J. Man. Mach. Stud., 1986, Vol. 24, No. 1, pp. 65-75.
9. Koulouriotis D.E., Diakoulakis I.E., Emiris D.M. Learning fuzzy cognitive maps using evolution strategies: a novel schema for modeling and simulating high-level behavior, Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546): IEEE, pp. 364-371.
10. Maiorino E. and other. Spectral reconstruction of protein contact networks, Phys. A Stat. Mech. its Appl., 2017, Vol. 471, pp. 804-817.
11. Mantegna R.N., Stanley H.E., Chriss N.A. An Introduction to Econophysics: Correlations and Complexity in Finance, Phys. Today, 2000, Vol. 53, No. 12, pp. 70-70.
12. Napoletani D., Sauer T.D. Reconstructing the topology of sparsely connected dynamical networks, Phys. Rev. E, 2008, Vol. 77, No. 2, pp. 026103.
13. Pandey P.K., Badarla V. Reconstruction of network topology using status-time-series data, Phys. A Stat. Mech. its Appl., 2018, Vol. 490, pp. 573-583.
14. Shahrampour S., Preciado V.M. Topology Identification of Directed Dynamical Networks via Power Spectral Analysis, IEEE Trans. Automat. Contr., 2015, Vol. 60, No. 8, pp. 2260-2265.
15. Shen Y., Baingana B., Giannakis G.B. Kernel-Based Structural Equation Models for Topology Identification of Directed Networks, IEEE Trans. Signal Process, 2017, Vol. 65, No. 10, pp. 2503-2516.
16. Squartini T. and other. Reconstruction methods for networks: The case of economic and financial systems, Phys. Rep., 2018, Vol. 757, pp. 1-47.
17. Tikhonov A., Arsenin V. Solutions of Ill-Posed Problems. New York: Wiley, 1977.
18. Tselykh A., Vasilev V., Tselykh L. Management of Control Impacts Based on Maximizing the Spread of Influence, Int. J. Autom. Comput., 2019, Vol. 16, No. 3, pp. 341-353.
19. Wang C.-L., Li C., Wang J. Comparisons of several algorithms for Toeplitz matrix recovery, Comput. Math. with Appl., 2016, Vol. 71, No. 1, pp. 133-146.
20. Wang W. and other. Kernel framework based on non-negative matrix factorization for networks reconstruction and link prediction, Knowledge-Based Syst., 2017, Vol. 137, pp. 104-114.
21. Wang Y.X.R., Huang H. Review on statistical methods for gene network reconstruction using expression data, J. Theor. Biol., 2014, Vol. 362, pp. 53–61.
22. Wittmann D.M. and other. Reconstruction of graphs based on random walks, Theor. Comput. Sci., 2009, Vol. 410, No. 38-40, pp. 3826-3838.
23. Wu J. and other. A two-stage algorithm for network reconstruction, Appl. Soft Comput., 2018, Vol. 70, pp. 751-763.
24. Wu J., Dang N., Jiao Y. Reconstruction of networks from one-step data by matching positions, Phys. A Stat. Mech. its Appl., 2018, Vol. 497, pp. 118-125.
25. Wu X., Wang W., Zheng W.X. Topology detection of complex networks with hidden variables and stochastic perturbations, 2012 IEEE International Symposium on Circuits and Systems. IEEE, 2012, pp. 898-901.
26. Xu K. and other. Discovering target groups in social networking sites: An effective method for maximizing joint influential power, Electron. Commer. Res. Appl., 2012, Vol. 11, No. 4, pp. 318–334.
