SOLUTION OF THE INVERSE PROBLEM OF SPECTRAL GRAPH THEORY IN THE ABSENCE OF OBSERVABLE VARIABLES
Abstract
The article is devoted to solving the main inverse problem of spectral graph theory – determining the main parameters of a graph based on the spectrum of its eigenvalues. The article studies cognitive causal graph models of complex systems with unknown dynamics of variables. Non-stochastic graph models with non-numeric values of nodes and links, as well as poorly defined system factors are considered. In the absence of initial data, solving the inverse problem for a directed weighted signed graph is significantly complicated. When graphs have the same topology but different weights on arcs, their spectra form a set of fuzzy collinear vectors in the solution space. The straight lines of these vectors diverge in the vector space due to their directionality to different vertices. The article proposes to use an algorithm that allows one to accurately restore the weights of a cognitive graph when the conditional principal eigenvector and the topological structure of the adjacency matrix are known. This algorithm takes into account an important feature of the adjacency matrix of the graph - the direction of the main eigenvector to the target vertex, which allows finding the correct solution from a set of fuzzy collinear vectors in the solution space. To achieve complete restoration of the graph weights with acceptable accuracy, it is proposed to combine the graph spectrum and the effective control model with the combinatorial optimization problem. Restoring the adjacency matrix weights using our approach, we compare them with the given graph. The comparison takes into account such graph parameters as the graph spectrum, similarity coefficients of the restored matrix, response and control vectors
References
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.
