On Finding the Optimal Tree of a Complete Weighted Graph

• Autorzy: Hosseini Seyed Soheil , Wormald Nick , Tian Tianhai
• Konferencja: Federated Conference on Computer Science and Information Systems (15 ; 06-09.09.2020 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

We want to find a tree where the path length between any two vertices on this tree is as close as possible to their corresponding distance in the complete weighted graph of vertices upon which the tree is built. We use the residual sum of squares as the optimality criterion to formulate this problem, and use the Cholesky decomposition to solve the system of linear equations to optimise weights of a given tree. We also use two metaheuristics, namely Simulated Annealing (SA) and Iterated Local Search (ILS) to optimise the tree structure. Our results suggest that SA and ILS both perform well at finding the optimal tree structure when the dispersion of distances in the complete graph is large. However, when the dispersion of distances is small, only ILS has a solid performance.

Słowa kluczowe

EN

computational complexity; graph theory; iterative methods; search problems; simulated annealing

PL

złożoność obliczeniowa; teoria grafów; metody iteracyjne; problemy wyszukiwawcze; symulowane wyżarzanie

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2020
• Tom: Vol. 21
• Strony: 271--275
• Opis fizyczny: Bibliogr. 11 poz., wz., rys., tab.

Twórcy

autor

Hosseini Seyed Soheil

• School of Mathematics, Monash University, Victoria 3800, Australia

autor

Wormald Nick

• School of Mathematics, Monash University, Victoria 3800, Australia

autor

Tian Tianhai

• School of Mathematics, Monash University, Victoria 3800, Australia

Bibliografia

• 1. J. Felsenstein and J. Felenstein, Inferring phylogenies. Sinauer associates Sunderland, MA, 2004, vol. 2.
• 2. G. Narasimhan and M. Smid, Geometric spanner networks. Cambridge University Press, 2007.
• 3. R. N. Mantegna, “Hierarchical structure in financial markets,” The European Physical Journal B-Condensed Matter and Complex Systems, vol. 11, no. 1, pp. 193–197, 1999. [Online]. Available: https://doi.org/10.1007/s100510050929
• 4. M. Tumminello, T. Aste, T. Di Matteo, and R. N. Mantegna, “A tool for filtering information in complex systems,” Proceedings of the National Academy of Sciences, vol. 102, no. 30, pp. 10 421–10 426, 2005. [Online]. Available: https://doi.org/10.1073/pnas.0500298102
• 5. V. Boginski, S. Butenko, and P. M. Pardalos, “Statistical analysis of financial networks,” Computational statistics & data analysis, vol. 48, no. 2, pp. 431–443, 2005. [Online]. Available: https://doi.org/10.1016/j.csda.2004.02.004
• 6. M. Tumminello, C. Coronnello, F. Lillo, S. Micciche, and R. N. Mantegna, “Spanning trees and bootstrap reliability estimation in correlation-based networks,” International Journal of Bifurcation and Chaos, vol. 17, no. 07, pp. 2319–2329, 2007. [Online]. Available: https://doi.org/10.1142/S0218127407018415
• 7. A. Kocheturov, M. Batsyn, and P. M. Pardalos, “Dynamics of cluster structures in a financial market network,” Physica A: Statistical Mechanics and its Applications, vol. 413, pp. 523–533, 2014. [Online]. Available: https://doi.org/10.1016/j.physa.2014.06.077
• 8. J.-P. Onnela, A. Chakraborti, K. Kaski, J. Kertesz, and A. Kanto, “Asset trees and asset graphs in financial markets,” Physica Scripta, vol. 2003, no. T106, p. 48, 2003.
• 9. J. Birch, A. A. Pantelous, and K. Soramäki, “Analysis of correlation based networks representing dax 30 stock price returns,” Computational Economics, vol. 47, no. 4, pp. 501–525, 2016. [Online]. Available: https://doi.org/10.1007/s10614-015-9481-z
• 10. D. Han et al., “Network analysis of the chinese stock market during the turbulence of 2015–2016 using log-returns, volumes and mutual information,” Physica A: Statistical Mechanics and its Applications, vol. 523, pp. 1091–1109, 2019. [Online]. Available: https://doi.org/10.1016/j.physa.2019.04.128
• 11. R. Desper and O. Gascuel, “Theoretical foundation of the balanced minimum evolution method of phylogenetic inference and its relationship to weighted least-squares tree fitting,” Molecular Biology and Evolution, vol. 21, no. 3, pp. 587–598, 2004. [Online]. Available: https://doi.org/10.1093/molbev/msh049

Uwagi

1. Track 1: Artificial Intelligence

2. Technical Session: 13th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).