АЛГОРИТМ РЕКОНСТРУКЦИИ МАТРИЦЫ СМЕЖНОСТИ ПРИЧИННЫХ ГРАФОВЫХ МОДЕЛЕЙ В ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ

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

Аннотация

Рассматривается проблема моделирования сложных систем при отсутствии на-
блюдаемых переменных. Для решения этой проблемы предлагается использовать причин-
ные графовые модели. Класс причинных моделей, который мы здесь рассматриваем, опре-
деляется как нестохастические причинные модели с ненаблюдаемыми переменными. Эти
модели представляются в виде направленного графа, создаваемого на основе человеческих
ментальных репрезентациях. При этом на дугах причинность выражена в виде некоторых
меток, которые имеют знак, определяющий направление изменений состояния системы.
Рассматриваемые причинные модели включают неоднородные, сложные и качественныетипы переменных, иллюстрирующие нечисловую природу узлов и связей, а, следовательно,
отсутствие и невозможность получения временных рядов данных. В условиях отсутствия
наблюдаемых переменных и невозможности проведения экспериментов, проблема рекон-
струкции матрицы смежности графовой причинной модели становится гораздо более
сложной. Требуется получить модель с определенным спектральным разложением, которое
реализует основную функцию моделируемой системы. На основе этой концепции предлагает-
ся новый метод реконструкции матрицы смежности, реализованный на соответствующей
матрице причинного распространения или передаточной матрице. Идея состоит в том,
чтобы использовать комбинаторную оптимизацию на основе спектральной теории графов
для генерации данных из качественной нестохастической причинной модели и реконструиро-
вать матрицу смежности, используя эти данные. В этом случае собственные векторы
идентифицируются как ключевые цели процесса реконструкции матрицы, что постулирует
фундаментальный подход, основанный на спектральных свойствах графа. Результаты вы-
числительных экспериментов решения задачи реконструкции матрицы смежности для при-
чинных графовых моделей в отсутствии наблюдаемых переменных с использованием разра-
ботанного алгоритма показали, что алгоритм эффективно реконструирует матрицы в за-
данных параметрах с допустимыми показателями схожести. Доказана сходимость при-
ближения к решению алгоритма реконструкции матриц не медленнее, чем со скоростью
геометрической прогрессии. С технической точки зрения, преимуществом алгоритма явля-
ется реализация инструмента автоматической настройки параметра регуляризации, при-
годного для пользователей без предварительных математических знаний.

Литература

1. Pearl J. Bayesianism and Causality, or, Why I am Only a Half-Bayesian, 2001, pp. 19-36.
2. Pandey B. et al. A comprehensive survey of edge prediction in social networks: Techniques,
parameters and challenges, Expert Syst. Appl., 2019, Vol. 124, pp. 164-181.
3. Delgado F.M., Gómez-Vela F. Computational methods for Gene Regulatory Networks
reconstruction and analysis: A review, Artif. Intell. Med., 2019, Vol. 95, pp. 133-145.
4. Wu X. et al. Analyses and applications of optimization methods for complex network
reconstruction, Knowledge-Based Syst., 2020, Vol. 193, pp. 105406.
5. Han X. et al. Robust Reconstruction of Complex Networks from Sparse Data, Phys. Rev. Lett.,
2015, Vol. 114, No. 2, pp. 028701.
6. Wang W.-X. et al. Network Reconstruction Based on Evolutionary-Game Data via
Compressive Sensing, Phys. Rev. X, 2011, Vol. 1, No. 2, pp. 021021.
7. Shen Z. et al. Reconstructing propagation networks with natural diversity and identifying
hidden sources, Nat. Commun., 2014, Vol. 5, No. 1, pp. 4323.
8. Squartini T. et al. Reconstruction methods for networks: The case of economic and financial
systems, Phys. Rep., 2018, Vol. 757, pp. 1–47.
9. 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.
10. Wang W. et al. Kernel framework based on non-negative matrix factorization for networks
reconstruction and link prediction, Knowledge-Based Syst., 2017, Vol. 137, pp. 104-114.
11. 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.
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. Timme M. Revealing Network Connectivity from Response Dynamics, Phys. Rev. Lett., 2007,
Vol. 98, No. 22, pp. 224101.
14. Yu D., Righero M., Kocarev L. Estimating Topology of Networks, Phys. Rev. Lett., 2006,
Vol. 97, No. 18, pp. 188701.
15. Zhang Z. et al. Reconstruction of dynamic networks with time-delayed interactions in the
presence of fast-varying noises, Phys. Rev. E, 2019, Vol. 99, No. 4, pp. 042311.
16. Bongard J., Lipson H. Automated reverse engineering of nonlinear dynamical systems, Proc.
Natl. Acad. Sci., 2007, Vol. 104, No. 24, pp. 9943-9948.
17. Li S. et al. Network reconstruction by linear dynamics, Phys. A Stat. Mech. its Appl., 2014,
Vol. 404, pp. 118-125.
18. Barranca V.J., Zhou D., Cai D. Compressive sensing reconstruction of feed-forward
connectivity in pulse-coupled nonlinear networks, Phys. Rev. E, 2016, Vol. 93, No. 6,
pp. 060201.
19. Simić S.K., Stanić Z. Polynomial reconstruction of signed graphs, Linear Algebra Appl., 2016,
Vol. 501, pp. 390-408.
20. Simić S.K., Stanić Z. On the polynomial reconstruction of graphs whose vertex-deleted
subgraphs have spectra bounded from below by −2, Linear Algebra Appl., 2008, Vol. 428, No.
8–9, pp. 1865-1873.
21. Sciriha I. Graphs with a common eigenvalue deck, Linear Algebra Appl., 2009, Vol. 430,
No. 1, pp. 78-85.
22. Wang W., Xu C.-X. Some results on the spectral reconstruction problem, Linear Algebra Appl.,
2007, Vol. 427, No. 1, pp. 151-159.
23. Bunimovich L., Shu L. Generalized eigenvectors of isospectral transformations, spectral
equivalence and reconstruction of original networks, Linear Algebra Appl., 2018, Vol. 551,
pp. 104-124.
24. Xu K. et al. 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.
25. 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.
26. Kavanagh R.J. The application of matrix methods to multi-variable control systems,
J. Franklin Inst., 1956, Vol. 262, No. 5, pp. 349-367.
27. Bertsekas D.P. The Method of Multipliers for Equality Constrained Problems, Constrained
Optimization and Lagrange Multiplier Methods. Elsevier, 1982, pp. 95-157.
28. Tikhonov A., Arsenin V. Solutions of Ill-Posed Problems. New York: Wiley, 1977.
29. Pedrycz W., Homenda W. From Fuzzy Cognitive Maps to Granular Cognitive Maps, IEEE
Trans. Fuzzy Syst., 2014, Vol. 22, No. 4, pp. 859-869.
30. Kim D.-H. Cognitive Maps of Policy Makers on Financial Crises of South Korea and
Malaysia: A Comparative Study, Int. Rev. Public Adm., 2004, Vol. 9, No. 2, pp. 31-38.
31. Büyüközkan G., Vardaloğlu Z. Analyzing of CPFR success factors using fuzzy cognitive maps
in retail industry, Expert Syst. Appl., 2012, Vol. 39, No. 12, pp. 10438-10455.
32. Tselykh A., Tselykh L. Methodology for comparative cognitive modeling based on the analysis
of fuzzy target and control factors, Izv. SFedU. Eng. Sci., 2015, Vol. 7 (168), pp. 101-115.
33. Poczeta K., Kubuś Ł., Yastrebov A. Analysis of an evolutionary algorithm for complex fuzzy
cognitive map learning based on graph theory metrics and output concepts, Biosystems, 2019,
Vol. 179, pp. 39-47.
Опубликован
2021-11-14
Выпуск
Раздел
РАЗДЕЛ IV. АНАЛИЗ ДАННЫХ И ОБРАБОТКА ИНФОРМАЦИИ