Majorization and the degree sequence of trees

Authors

DOI:

https://doi.org/10.47909/ijsmc.136

Keywords:

networks, trees, data structures, majorization, Lorenz curves, degree sequences

Abstract

Objective. This study investigated the relation between the degree sequences of trees and the majorization order.

Design/Methodology/Approach. The majorization technique was employed in accordance with the tenets of Muirhead’s theorem.

Results. In this study, we proved a theorem that provides a necessary and sufficient condition for degree sequences of trees to be comparable in the majorization order.

Research Limitations. Our research was focused on the study of trees rather than general networks. Furthermore, our investigation was primarily theoretical in nature.

Practical Implications. Given the pervasiveness of trees in the field of information science, our theoretical study made a significant contribution to the advancement of knowledge regarding trees as a crucial data structure.

Originality/Value. This study represented a rare instance of a text that combines two distinct but related areas of study: the Lorenz curves and majorization on the one hand and the degree sequences of networks on the other.

Downloads

Download data is not yet available.

References

Archambault, E., Beauchesne, O. H., & Caruso, J. (2011). Towards a multilingual, comprehensive and open scientific journal ontology. In B. Noyons, P. Ngulube, & J. Leta (Eds.) Proceedings of the ISSI 2011 conference (pp. 66–77). ISSI & University of Zululand.

Chubin, D. E. & Moitra, S. D. (1975). Content analysis of references: Adjunct or alternative to citation counting? Social Studies of Science, 5(4), 423–441. https://doi.org/10.1177/030631277500500403 DOI: https://doi.org/10.1177/030631277500500403

Egghe, L. (2024). Networks and their degree distribution, leading to a new concept of small worlds. Journal of Informetrics, 18(3), article 101554. https://doi.org/10.1016/j.joi.2024.101554 DOI: https://doi.org/10.1016/j.joi.2024.101554

Fidel, R. (1991). Searchers’ selection of search keys: I. The selection routine. Journal of the American Society for Information Science, 42(7), 490–500. https://doi.org/10.1002/(SICI)1097-4571(199108)42:7 DOI: https://doi.org/10.1002/(SICI)1097-4571(199108)42:7<490::AID-ASI4>3.0.CO;2-V

Hakimi, S. L. (1962). On realizability of a set of integers as degrees of the vertices of a linear graph I. Journal of the Society for Industrial and Applied Mathematics, 19(3), 496–507. https://doi:10.1137/0110037 DOI: https://doi.org/10.1137/0110037

Hardy, G. H., Littlewood, J. E., & Pólya, G. (1934). Inequalities. Cambridge University Press.

Kenekayoro, P., Buckley, K., & Thelwall, M. (2014). Automatic classification of academic web page types. Scientometrics, 101(2), 1015–1026. https://doi.org/10.1007/s11192-014-1292-9 DOI: https://doi.org/10.1007/s11192-014-1292-9

Knuth, D. E. (1973). The art of computer programming, Vol. 1: Fundamental algorithms (2nd ed.). Addison-Wesley.

Kosmulski, M. (2013). Family-tree of bibliometric indices. Journal of Informetrics, 7(4), 313–317. https://doi:10.1016/j.joi.2012.12.002 DOI: https://doi.org/10.1016/j.joi.2012.12.002

Kwasnik, B. H. (1999). The role of classification in knowledge representation and discovery. Library Trends, 48(1), 22–47.

Leydesdorff, L., Rotolo, D., & Rafols, I. (2012). Bibliometric perspectives on medical innovation using the Medical Subject Headings (MeSH) of PubMed. Journal of the American Society for Information Science and Technology, 63(11), 2239–2253. https://doi.org/10.1002/asi.22715 DOI: https://doi.org/10.1002/asi.22715

Lorenz, M. O. (1905). Methods of measuring the concentration of wealth. Publications of the American Statistical Association, 9, 209–219. https://doi.org/10.1080/15225437.1905.10503443 DOI: https://doi.org/10.1080/15225437.1905.10503443

Ma, Z. Y., Sun, A. X., & Cong, G. (2013). On predicting the popularity of newly emerging hashtags in Twitter. Journal of the American Society for Information Science and Technology, 64(7), 1399–1410. https://doi.org/10.1002/asi.22844 DOI: https://doi.org/10.1002/asi.22844

Marshall, A. W., Olkin, I., & Arnold, B. C. (2011). Inequalities: Theory of majorization and its applications. Springer. DOI: https://doi.org/10.1007/978-0-387-68276-1

Muirhead, R. F. (1903). Some methods applicable to identities and inequalities of symmetric algebraic functions of n letters. Proceedings of the Edinburgh Mathematical Society, 21, 144–157. https://doi.org/10.1017/S001309150003460X DOI: https://doi.org/10.1017/S001309150003460X

Rousseau, R. (2011). Lorenz curves determine partial orders for comparing network structures. DESIDOC Journal of Library & Information Technology, 31(5), 340–347. https://doi.org/10.14429/djlit.31.5.1190 DOI: https://doi.org/10.14429/djlit.31.4.1190

Rousseau, R., Egghe, L., & Guns, R. (2018). Becoming metric-wise. A bibliometric guide for researchers. Chandos-Elsevier.

Tschopp, E., Mateus, O., Benson, R. B. J. (2015). A specimen-level phylogenetic analysis and taxonomic revision of Diplodocidae (Dinosauria, Sauropoda). PeerJ, 3, Article e857. https://doi.org/10.7717/peerj.857 DOI: https://doi.org/10.7717/peerj.857

Wang, J., Berzins, K., Hicks, D., Melkers, J., Xiao, F. & Pinheiro, D. (2012). A boosted-trees method for name disambiguation. Scientometrics, 93(2), 391–411. https://doi.org/10.1007/s11192-012-0681-1 DOI: https://doi.org/10.1007/s11192-012-0681-1

Wasserman, S., & Faust, K. (1994). Social network analysis. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511815478

Winston, W. L. (1994). Operations research. Applications and algorithms. Duxbury Press.

Yang, Y., Wu, M. Z., & Cui, L. (2012). Integration of three visualization methods based on co-word analysis. Scientometrics, 90(2), 659–673. https://doi.org/10.1007/s11192-011-0541-4 DOI: https://doi.org/10.1007/s11192-011-0541-4

Zheng, R., Li, J. X., Chen, H. C., & Huang, Z. (2006). A framework for authorship identification of online messages: Writing-style features and classification techniques. Journal of the American Society for Information Science and Technology, 57(3), 378–393. https://doi.org/10.1002/asi.20316 DOI: https://doi.org/10.1002/asi.20316

Downloads

Published

2024-11-06

How to Cite

Egghe, L., & Rousseau, R. (2024). Majorization and the degree sequence of trees. Iberoamerican Journal of Science Measurement and Communication, 4(3), 1–9. https://doi.org/10.47909/ijsmc.136

Issue

Vol. 4 No. 3 (2024): Iberoamerican Journal of Science Measurement and Communication

Section

Original article

License

Copyright (c) 2024 Leo Egghe, Ronald Rousseau

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

This is an open access article distributed under the terms of the CC BY-NC 4.0, which permits copying and redistributing the material in any medium or format, adapting, transforming, and building upon the material as long as the license terms are followed.