РЕШЕНИЕ ОБРАТНОЙ ЗАДАЧИ СПЕКТРАЛЬНОЙ ТЕОРИИ ГРАФОВ ПРИ ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ
Аннотация
Статья посвящена решению основной обратной задачи спектральной теории графов – определении основных параметров графа по спектру его собственных значений. В данной работе нас интересуют когнитивные причинные графовые модели сложных систем, динамика переменных которых недоступна. Мы рассматриваем нестохастические графовые модели, которые имеют нечисловые значения узлов и связей, а также плохо определенные системные факторы. При отсутствии исходных данных решение обратной задачи для направленного взвешенного знакового графа становится значительно более сложным. Когда графы имеют одинаковую топологию, но разные веса на дугах, то их спектры образуют в пространстве решений некоторое множество нечетких коллинеарных векторов. Линии этих векторов расходятся в пространстве векторов из-за их направленности к разным вершинам. В данной работе предлагается использовать алгоритм, позволяющий точно восстановить веса когнитивного графа, когда известен условный главный собственный вектор и топологический шаблон матрицы смежности. Данный алгоритм учитывает важную особенность матрицы смежности графа – направление главного собственного вектора к целевой вершине, что позволяет найти правильное решение из набора нечетких коллинеарных векторов в пространстве решений. Для того, чтобы добиться полного восстановления весов графа с приемлемой точностью предлагается объединить спектр графа и модель эффективную управления с задачей комбинаторной оптимизации. Восстанавливая веса матрицы смежности с использованием нашего подхода, мы сравниваем их с заданным графом. При сравнении учитываются такие параметры графа, как спектр графа, коэффициенты подобия для реконструированной матрицы, векторы отклика и управления
Список литературы
1. Chu M.T., Golub G.H. Inverse Eigenvalue Problems: Theory, Algorithms, and Applications. Oxford University Press, 2005.
2. Tselykh A., Vasilev V., Tselykh L. Assessment of influence productivity in cognitive models, Artif. Intell. Rev., 2020, 53, pp. 5383-5409. Available at: https://doi.org/10.1007/s10462-020-09823-8.
3. Nicoletti S., Carletti T., Fanelli D., Battistelli G., Chisci L. Generating directed networks with prescribed Laplacian spectra, J. Phys. Complex., 2021, 2, 015004. Available at: https://doi.org/ 10.1088/2632-072X/abbd35.
4. Butterworth J., Dunne P.E. Spectral Techniques in Argumentation Framework Analysis. In: 6th Interna-tional Conf. on Computational Models of Argument (COMMA). Potsdam, Germany, 2016, pp. 9-16. Available at: https://doi.org/10.3233/978-1-61499-686-6-167.
5. Shine A., Kempe D. Generative Graph Models based on Laplacian Spectra?, In: The World Wide Web Conference. ACM, New York, NY, USA, 2019, pp. 1691-1701. Available at: https://doi.org/10.1145/ 3308558.3313631.
6. Martinkus K., Loukas A., Perraudin N., Wattenhofer R. Spectre: Spectral conditioning helps to over-come the expressivity limits of one-shot graph generators, In: 39th International Conference on Machine Learning (ICML 2022), 2022, pp. 15159-15179.
7. Luo T., Mo Z., Pan S.J. Fast Graph Generation via Spectral Diffusion, IEEE Trans. Pattern Anal. Mach. Intell., 2024, 46, pp. 3496-3508. Available at: https://doi.org/10.1109/TPAMI.2023.3344758.
8. Pandey P.K., Badarla V. Reconstruction of network topology using status-time-series data, Phys. A Stat. Mech. its Appl., 2018, 490, pp. 573-583. Available at: https://doi.org/10.1016/j.physa.2017.08.091.
9. Wang Z., Jiang W., Wu W., Wang S. Reconstruction of complex network from time series data based on graph attention network and Gumbel Softmax, Int. J. Mod. Phys. C, 2023, 34, Available at: https://doi.org/10.1142/S0129183123500572.
10. Zhang Z., Chen Y., Mi Y., Hu G. Reconstruction of dynamic networks with time-delayed interactions in the presence of fast-varying noises, Phys. Rev. E, 2019, 99, 042311. Available at: https://doi.org/10.1103/PhysRevE.99.042311.
11. Timme M. Revealing Network Connectivity from Response Dynamics, Phys. Rev. Lett., 2007, 98, 224101. Available at: https://doi.org/10.1103/PhysRevLett.98.224101.
12. Bertsekas D.P. The Method of Multipliers for Equality Constrained Problems, In: Constrained Optimi-zation and Lagrange Multiplier Methods. Elsevier, 1982, pp. 95-157. Available at: https://doi.org/10.1016/B978-0-12-093480-5.50006-4.
13. Bertsekas D.P. Constrained Optimization and Lagrange Multiplier Methods, Athena Scientifi, Belmont, MA, 1996.
14. Tikhonov A., Arsenin V. Solutions of Ill-Posed Problems. Wiley, New York, 1977.
15. Lancaster, P., Tismenetsky, M.: The theory of matrices: with applications. Academic Press, Orlando, Fla, USA (1985).
16. Groumpos P.P. Why Model Complex Dynamic Systems Using Fuzzy Cognitive Maps? Robot. Autom. Eng. J., 2017, 1. Available at: https://doi.org/10.19080/RAEJ.2017.01.555563.
17. Mazzuto G., Stylios C., Ciarapica F.E., Bevilacqua M., Voula G. Improved Decision-Making through a DEMATEL and Fuzzy Cognitive Maps-Based Framework, Math. Probl. Eng., 2022, pp. 1-14. Available at: https://doi.org/10.1155/2022/2749435.
18. Kim D.-H. Cognitive Maps of Policy Makers on Financial Crises of South Korea and Malaysia:
A Comparative Study, Int. Rev. Public Adm., 2004, 9, pp. 31-38. Available at: https://doi.org/10.1080/ 12294659.2005.10805047.
19. Bonham G.M., Shapiro M. CHAPTER SIX. Explanation of the Unexpected: The Syrian Intervention in Jordan in 1970, In: Structure of Decision: The Cognitive Maps of Political Elites. Princeton University Press, 2015, pp. 113-141. Available at: https://doi.org/10.1515/9781400871957-009.
20. van Esch F.A.W.J. From belief to behaviour. Using cognitive maps to test ideational policy explanations, In: 10th Conference of the ECPR Standing Group on the European Union. ECPR Press, Rome, 2021.
21. Powell M.J.D. An efficient method for finding the minimum of a function of several variables without calculating derivatives, Comput. J., 1964, 7, pp. 155.162. Available at: https://doi.org/10.1093/comjnl/7.2.155.
