Annals of Computer Science and Information Systems, Volume 21

DOI: http://dx.doi.org/10.15439/2020F4

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 271–275 (2020)

Full text

Abstract. 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.

References

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