Laplacian Matrices for Extremely Balanced and Unbalanced Phylogenetic Trees
Phylogenetic trees are important tools in the study of evolutionary relationships between species. Measures such as the index of Sackin, Colless, and Total Cophenetic have been extensively used to quantify tree balance, one key property of phylogenies. Recently a new proposal has been introduced, based on the spectrum of the Laplacian matrix associated with the tree. In this work, we calculate the Laplacian matrix analytically for two extreme cases, corresponding to fully balanced and fully unbalanced trees. For maximally balanced trees no closed form for the Laplacian matrix was derived, but we present an algorithm to construct it. We show that Laplacian matrices of fully balanced trees display self-similar patterns that result in highly degenerated eigenvalues. Degeneracy is the main signature of this topology, since it is totally absent in fully unbalanced trees. We also establish some analytical and numerical results about the largest eigenvalue of Laplacian matrices for these topologies.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Designing Laplacian flows for opinion clustering in structurally balanced and unbalanced networks
In this work, we consider a group of n agents whose interactions can be represented using unsigned or signed structurally balanced graphs or a special case of structurally unbalanced graphs. A Laplacian-based model is pr…
Semi-supervised learning in unbalanced and heterogeneous networks
Community detection was a hot topic on network analysis, where the main aim is to perform unsupervised learning or clustering in networks. Recently, semi-supervised learning has received increasing attention among resear…
ClusteringCommunity DetectionEntropic Optimal Transport between Unbalanced Gaussian Measures has a Closed Form
Although optimal transport (OT) problems admit closed form solutions in a very few notable cases, e.g. in 1D or between Gaussians, these closed forms have proved extremely fecund for practitioners to define tools inspire…
FormOn the Balance of Unrooted Trees
We solve a class of optimization problems for (phylogenetic) $X$-trees or their shapes. These problems have recently appeared in different contexts, e.g. in the context of the impact of tree shapes on the size of TBR nei…
Optimal designs for Lasso and Dantzig selector using Expander Codes
We investigate the high-dimensional regression problem using adjacency matrices of unbalanced expander graphs. In this frame, we prove that the $\ell_{2}$-prediction error and the $\ell_{1}$-risk of the lasso and the Dan…