Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-23T21:10:23.532Z Has data issue: false hasContentIssue false
  • English
  • Français

DEGREE-BASED GINI INDEX FOR GRAPHS

Published online by Cambridge University Press:  14 March 2019

Carly Domicolo  and
Hosam Mahmoud
Carly Domicolo
Affiliation:
Department of Statistics, The George Washington University, Washington, D.C. 20052, USA E-mail: [email protected]; [email protected]
Hosam Mahmoud
Affiliation:
Department of Statistics, The George Washington University, Washington, D.C. 20052, USA E-mail: [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In Balaji and Mahmoud [1], the authors introduced a distance-based Gini index for rooted trees. In this paper, we introduce a degree-based Gini index (or just simply degree Gini index) for graphs. The latter index is a topological measure on a graph capturing the proximity to regular graphs. When applied across the random members of a class of graphs, we can identify an average measure of regularity for the class. Whence, we can compare the classes of graphs from the vantage point of closeness to regularity.

We develop a simplified computational formula for the degree Gini index and study its extreme values. We show that the degree Gini index falls in the interval [0, 1). The main focus in our study is the degree Gini index for the class of binary trees. Via a left-packing transformation, we show that, for an arbitrary sequence of binary trees, the Gini index has inferior and superior limits in the interval [0, 1/4]. We also show, via the degree Gini index, that uniform rooted binary trees are more regular than binary search trees grown from random permutations.

Keywords

chemical treecombinatorial probabilityGini indexrandom treetopological indexWiener index
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 34 , Issue 2 , April 2020 , pp. 157 - 171
Copyright
Copyright © Cambridge University Press 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Balaji, H. & Mahmoud, H. (2017). The Gini index of random trees with an application to caterpillars. Journal of Applied Probability 54: 701–709.CrossRefGoogle Scholar
2.Ceriani, L. & Verme, P. (2012). The origins of the Gini index: extracts from Variabilità e Mutabilità (1912) by Corrado Gini. Journal of Economic Inequality 10: 421–443.CrossRefGoogle Scholar
3.Devroye, L. (1986). A note on the height of binary search trees. Journal of the ACM 33: 489–498.CrossRefGoogle Scholar
4.Devroye, L. (1991). Limit laws for local counters in random binary search trees. Random Structures & Algorithms 2: 303–315.CrossRefGoogle Scholar
5.Drmota, M. (2003). On the variance of the height of random binary search trees. Journal of the ACM 50: 333–374.CrossRefGoogle Scholar
6.Eggemann, N. & Noble, S. (2011). The clustering coefficient of a scale-free random graph. Discrete Applied Mathematics 159: 953–965.CrossRefGoogle Scholar
7.Feng, Q. & Hu, Z. (2011). On the Zagreb index of random recursive trees. Journal of Applied Probability 48: 1189–1196.CrossRefGoogle Scholar
8.Feng, Q., Mahmoud, H., & Panholzer, A. (2008). Limit laws for the Randič index of random binary tree models. The Annals of the Institute of Statistical Mathematics 60: 319–343.CrossRefGoogle Scholar
9.Flajolet, P. & Odlyzko, A. (1982). The height of binary trees and other families of simple trees. Journal of Computer and System Sciences 25: 171–213.CrossRefGoogle Scholar
10.Gastwirth, J. (1972). The estimation of the Lorenz curve and Gini index. Review of Economics and Statistics 54: 306–316.CrossRefGoogle Scholar
11.Gini, C. (1912). Veriabilità e Mutabilità, C. Cuppini, Bologna, Italy.Google Scholar
12.Kemp, R. (1984). Fundamentals of the Average Case Analysis of Particular Algorithms. Stuttgart, Germany: Wiley-Teubner.CrossRefGoogle Scholar
13.Knuth, D. (1997). The Art of Computer Programming, Vol. 1, Fundamental Algorithms, 3rd ed., Reading, Massachusetts, USA: Addison-Wesley Longman.Google Scholar
14.Lee, J., Manzil, Z., Günnemann, S., & Smola, A. (2015). The clustering coefficient of preferential attachment networks with affinities. Proceedings of Machine learning Research 38: 571–580.Google Scholar
15.Mahmoud, H. (1995). The joint distribution of the three types of nodes in uniform binary trees. Algorithmica 13: 313–323.CrossRefGoogle Scholar
16.Mahmoud, H. (2008). Pólya Urn Models. Boca Raton, Florida, USA: Chapman-Hall.CrossRefGoogle Scholar
17.Neininger, R. (2002). The Wiener index of random trees. Combinatorics, Probability & Computing 11: 587–597.CrossRefGoogle Scholar
18.Prodinger, H. (1996). A note on the distribution of the three types of nodes in uniform binary trees. Seminaire Lotharingien de Combinatoire 38: 5.Google Scholar
19.Thon, D. (1982). An Axiomatization of the Gini Coefficient. Mathematical Social Sciences 2: 131–143.CrossRefGoogle Scholar
20.Timmerman, H., Todeschini, R., Consonni, V., Mannhold, R., & Kubinyi, H. (2002). Handbook of Molecular Descriptors. Weinheim: Wiley-VCH.Google Scholar
21.Zhang, P. & Dey, D. (2019+). The degree profile and Gini index of random caterpillar trees. Probability in the Engineering and Informational Sciences (to appear). doi:10.1017/S0269964818000475Google Scholar
22.Zhang, P. & Mahmoud, H. (2016). The degree profile and weight in Apollonian networks and k-trees. Advances in Applied Probability 48: 163–175.CrossRefGoogle Scholar