ВОССТАНОВЛЕНИЕ МАТРИЦЫ СМЕЖНОСТИ В ЗАДАННЫХ ПАРАМЕТРАХ ДЛЯ ИСХОДНОЙ ГРАФОВОЙ МОДЕЛИ С ДЕТЕРМИНИРОВАННОЙ ПРИЧИННОСТЬЮ

  • А. Н. Целых Южный Федеральный Университет
  • В. С. Васильев Южный Федеральный Университет
  • Л. А. Целых Таганрогский институт имени А.П. Чехова (филиал) Ростовского государственного экономического университета (РИНХ)
Ключевые слова: Восстановление матрицы смежности, оптимизационные методы, когнитивные модели, детерминированная причинность, ориентированный взвешенный граф

Аннотация

В данном исследовании разработан подход формирования графа системы, обладающего заданными передаточными свойствами, не утрачивающего эффективных соотноше-ний между векторами воздействий и откликов, на которых достигается максимум отно-шения этих норм (или отношения их квадратов норм), и реализующего на передаточной матрице эти экстремальные условия. Реализована задача восстановления матрицы смежности в заданных параметрах для исходной модели графа. Данная задача в обобщенной постановке не решалась и является новой. Решение данной задачи на основе комбинации положений теории систем, линейной и матричной алгебры позволяет формализовать за-висимость влияния характеристик сети на свойства сети, что дает возможность конструировать сети, обладающие заданными свойствами. Мы применяем понятие передаточ-ной матрицы к задаче максимизации передачи влияния в социально-экономической системе. В основе задачи оптимального изменения используется минимизация матричной нормы, согласованной с векторными нормами воздействий и откликов. Такая постановка задачи делает возможным формирование графа системы, обладающего заданными передаточ-ными свойствами. Алгоритм, реализующий данный подход, является вычислительно эф-фективным с O(m3), где m – это число пар задаваемых векторов, поскольку в его основе лежит метод множителей Лагранжа 2-го порядка и метод сопряженных направлений. Поскольку решаются задачи квадратичного программирования с линейными ограничения-ми, то критерием получения решения является не достижение требуемой точности, а выход в область безусловной оптимизации (ни одно ограничение не нарушается, множите-ли Лагранжа, соответствующие ограничениям в форме неравенств, неотрицательны), что происходит существенно быстрее по сравнению с задачами общего нелинейного про-граммирования.

Литература

1. Anand K. and other. The missing links: A global study on uncovering financial network structures from partial data, J. Financ. Stab., 2018, Vol. 35, pp. 107-119.
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.
Опубликован
2019-09-24
Выпуск
Раздел
РАЗДЕЛ II. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ.