×

Domination number of an interval catch digraph family and its use for testing uniformity. (English) Zbl 1435.05178

Summary: We consider a special type of interval catch digraph (ICD) for one-dimensional data in a randomized setting and propose its use for testing uniformity. These ICDs are defined with expansion and centrality parameters, hence are called parameterized ICDs (PICDs). We derive the exact (and asymptotic) distribution of the domination number of this PICD when its vertices are from a uniform (and non-uniform) distribution in one dimension for the entire parameter ranges; thereby determine the parameters for which the asymptotic distribution is non-degenerate. We use the domination number for testing uniformity of one-dimensional data, prove its consistency against certain alternatives, and compare it with commonly used and recently proposed tests in literature and also arc density of two ICD families in terms of size and power. Based on our Monte Carlo simulations, we demonstrate that PICD domination number has higher power for certain types of alternatives compared to other tests.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
60D05 Geometric probability and stochastic geometry
60C05 Combinatorial probability
62E20 Asymptotic distribution theory in statistics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arlazarov, VV; Zhukovsky, AE; Krivtsov, VE, Using intersection graphs for smartphone-based document localization, Sci Tech Inform Process, 44, 5, 365-372 (2017) · doi:10.3103/S0147688217050021
[2] Drachenberg, R.Interval digraphs: a generalization of interval graphs [Master’s thesis]. Denver (CO): University of Colorado; 1994. p. 80202.
[3] Quadrini, M, Culmone, R, Merelli, E.Topological Classification of RNA Structures via Intersection Graph. In: Martín-Vide C, Neruda R, Vega-Rodríguez M. editors. Theory and Practice of Natural Computing. TPNC 2017. Lecture Notes in Computer Science, vol. 10687. Cham: Springer; 2017. https://link.springer.com/chapter/10.1007/978-3-319-71069-3_16#citeas. · Zbl 1505.92145
[4] Roberts, FS., Discrete mathematical models (1976), Upper Saddle River (NJ): Prentice-Hall, Upper Saddle River (NJ)
[5] Prisner, E., A characterizaiton of interval catch digraphs, Discrete Math, 73, 285-289 (1989) · Zbl 0669.05038 · doi:10.1016/0012-365X(89)90271-9
[6] Prisner, E., Algorithms for interval catch digraphs, Discrete Appl Math, 51, 147-157 (1994) · Zbl 0810.68104 · doi:10.1016/0166-218X(94)90104-X
[7] Cannon, A, Cowen, L.Approximation algorithms for the class cover problem. Proceedings of the 6th International Symposium on Artificial Intelligence and Mathematics; 2000 Jan 5-7; Fort Lauderdale, Florida; 2000. · Zbl 1075.68609
[8] Marchette, DM., Random graphs for statistical pattern recognition (2004), Hoboken (NJ): Wiley-Interscience, Hoboken (NJ) · Zbl 1057.62048
[9] Beer, E.; Fill, JA; Janson, S., On vertex, edge, and vertex-edge random graphs, Electron J Comb, 18, #P110 (2011) · Zbl 1217.05205
[10] Priebe, C.; DeVinney, JG; Marchette, DJ., On the distribution of the domination number of random class cover catch digraphs, Stat Probab Lett, 55, 239-246 (2001) · Zbl 0999.05082 · doi:10.1016/S0167-7152(01)00129-8
[11] DeVinney, J.; Priebe, C., A new family of proximity graphs: class cover catch digraphs, Discrete Appl Math, 154, 14, 1975-1982 (2006) · Zbl 1102.05030 · doi:10.1016/j.dam.2006.04.004
[12] Manukyan, A.; Ceyhan, E., Classification of imbalanced data with a geometric digraph family, J Mach Learn Res, 17, 189, 1-40 (2016) · Zbl 1392.62190
[13] Xiang, P.; Wierman, JC., A CLT for a one-dimensional class cover problem, Stat Probab Lett, 79, 2, 223-233 (2009) · Zbl 1157.60017 · doi:10.1016/j.spl.2008.07.045
[14] Ceyhan, E., The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data, Discrete Math, 308, 23, 5376-5393 (2008) · Zbl 1219.05114 · doi:10.1016/j.disc.2007.10.003
[15] Hedetniemi, ST; Laskar, RC., Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math, 86, 1-3, 257-277 (1990) · Zbl 0733.05076 · doi:10.1016/0012-365X(90)90365-O
[16] Henning, MA; Yeo, A., Total domination in graphs (2013), New York: Springer, New York · Zbl 1408.05002
[17] Hao, G., Total domination in digraphs, Quaest Math, 40, 3, 333-346 (2017) · Zbl 1423.05121 · doi:10.2989/16073606.2017.1288664
[18] Lee, C., Domination in digraphs, J Korean Math Soc, 4, 843-853 (1998) · Zbl 0917.05040
[19] Niepel, L.; Knor, M., Domination in a digraph and in its reverse, Discrete Appl Math, 157, 13, 2973-2977 (2009) · Zbl 1211.05121 · doi:10.1016/j.dam.2009.04.011
[20] L’Ecuyer, P.Software for uniform random number generation: distinguishing the good and the bad. In Peters BA, Smith JS, Medeiros DJ, Rohrec MW, editors. Proceedings of the 2001 winter simulation conference, Arlington, VA, USA; 2001.
[21] Fahidy, TZ., On the potential application of uniformity tests in circular statistics to chemical processes, Int J Chem, 5, 1, 31-38 (2013) · doi:10.5539/ijc.v5n1p31
[22] Milošević, B., Asymptotic efficiency of goodness-of-fit tests based on too-lin characterization, Commun Stat-Simul Comput, 1-20 (2018)
[23] Chen, H.; Friedman, JH., A new graph-based two-sample test for multivariate and object data, J Amer Statist Assoc, 112, 517, 397-409 (2017) · doi:10.1080/01621459.2016.1147356
[24] Jain, AK, Xu, X, Ho, TK, et al. Uniformity testing using minimal spanning tree. Proceedings of the 16th International Conference on Pattern Recognition (ICPR’02); Vol. 4, 2002. p. 40281.
[25] Ceyhan, E., Density of a random interval catch digraph family and its use for testing uniformity, REVSTAT, 14, 4, 349-394 (2016) · Zbl 1370.05186
[26] Ceyhan, E., The distribution of the relative arc density of a family of interval catch digraph based on uniform data, Metrika, 75, 6, 761-793 (2012) · Zbl 1410.62078 · doi:10.1007/s00184-011-0351-y
[27] Zamanzade, E., Testing uniformity based on new entropy estimators, J Stat Comput Simul, 85, 16, 3191-3205 (2015) · Zbl 1510.62213 · doi:10.1080/00949655.2014.958085
[28] Ceyhan, E.; Priebe, C., The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association, Stat Probab Lett, 73, 1, 37-50 (2005) · Zbl 1080.62031 · doi:10.1016/j.spl.2005.02.012
[29] Francis, MC; Jacob, D.; Jana, S., Uniquely restricted matchings in interval graphs, SIAM J Discrete Math, 32, 1, 148-172 (2018) · Zbl 1378.05137 · doi:10.1137/16M1074631
[30] Sen, M.; Das, S.; Roy, A., Interval digraphs: an analogue of interval graphs, J Graph Theory, 13, 189-202 (1989) · Zbl 0689.05025 · doi:10.1002/jgt.3190130508
[31] Das, AK; Das, S.; Sen, M., Forbidden substructure for interval digraphs/bigraphs, Discrete Math, 339, 2, 1028-1051 (2016) · Zbl 1327.05132 · doi:10.1016/j.disc.2015.10.010
[32] Jaromczyk, JW; Toussaint, GT., Relative neighborhood graphs and their relatives, Proc IEEE, 80, 1502-1517 (1992) · doi:10.1109/5.163414
[33] Maehara, H., A digraph represented by a family of boxes or spheres, J Graph Theory, 8, 3, 431-439 (1984) · Zbl 0552.05030 · doi:10.1002/jgt.3190080312
[34] West, DB., Introduction to graph theory (2001), Upper Saddle River: Springer, Upper Saddle River
[35] Chartrand, G.; Harary, F.; Bill, QY., On the out-domination and in-domination numbers of a digraph, Discrete Math, 197-198, 179-183 (1999) · Zbl 0978.05057 · doi:10.1016/S0012-365X(98)00232-5
[36] Ceyhan, E.; Priebe, C., On the distribution of the domination number of a new family of parametrized random digraphs, Model Assist Stat Appl, 1, 4, 231-255 (2007) · Zbl 1127.05092
[37] Janson, S, Łuczak, T, Ruciński, A.Random graphs. New York: John Wiley & Sons, Inc.; 2000. (Wiley-Interscience series in discrete mathematics and optimization). · Zbl 0968.05003
[38] Grzegorzewski, P.; Wieczorkowski, R., Entropy-based goodness of fit test for exponentiality, Commun Stat Theory Methods, 28, 1183-1202 (1999) · Zbl 0919.62041 · doi:10.1080/03610929908832351
[39] Priebe, C.; Marchette, DJ; DeVinney, J., Classification using class cover catch digraphs, J Classif, 20, 1, 3-23 (2003) · Zbl 1055.62074 · doi:10.1007/s00357-003-0003-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.