The Number of Triangles in Random Intersection Graphs

Abstract

Let $T_n$ be the number of triangles in the random intersection graph G(n, m, p). When the mean of $T_n$ is bounded, we obtain an upper bound on the total variation distance between $T_n$ and a Poisson distribution. When the mean of $T_n$ tends to infinity, the Stein–Tikhomirov method is used to bound the error for the normal approximation of $T_n$ with respect to the Kolmogorov metric.

Keywords

Random intersection graph / Stein’s method / Poisson approximation / Normal approximation

References

[1] Adell, J.A., Jodrá. P.: Exact Kolmogorov and total variation distances between some familiar discrete distributions. J. Ineq. Appl. 2006, Article 64307 (2006)

[2] Ball FG, Sirl DJ, Trapman P. Epidemics on random intersection graphs. Ann. Appl. Probab.. 2014, 24 1081-1128

[3] Barbour AD, Karoński M, Ruciński A. A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B.. 1989, 47 125-145

[4] Barbour AD, Reinert G. The shortest distance in random multi-type intersection graphs. Random Struct. Algorithms. 2011, 39 179-209

[5] Behrisch, M.: Component evolution in random intersection graphs. Electron. J. Combin.14 # R17 (2007)

[6] Bloznelis M. Degree and clustering coefficient in sparse random intersection graphs. Ann. Appl. Probab.. 2013, 23 1254-1289

[7] Bloznelis, M., Godehardt, E., Jaworski, J., Kurauskas, V., Rybarczyk, K.: Recent progress in complex network analysis: properties of random intersection graphs. In: Data Science. Learning by Latent Structures, and Knowledge Discovery, pp. 79–88. Springer, Berlin (2015)

[8] Bloznelis, M., Jaworski, J.: The asymptotic normality of the global clustering coefficient in sparse random intersection graphs. Algorithms and models for the web graph, pp. 16–29, Lecture Notes in Comput. Sci., 10836. Springer, Cham (2018)

[9] Bloznelis, M., Kurauskas, V.: Large cliques in sparse random intersection graphs. Electron. J. Combin.24(2), Paper No. 2.5 (2017)

[10] Chatterjee, S.: Large deviations for Random Graphs. École d’Été de Probabilités de Saint Flour XLV, Springer Lecture Notes in Mathematics (2015)

[11] Chatterjee S. An introduction to large deviations for random graphs. Bull. Am. Math. Soc.. 2016, 53 617-642

[12] Chatterjee S, Varadhan SRS. The large deviation principle for the Erdős-Rényi random graph. Eur. J. Combin.. 2011, 32 1000-1017

[13] Chen, L.H.Y., Röllin, A.: Stein couplings for normal approximation. Preprint (2010) arXiv:1003.6039

[14] Deijfen M, Kets W. Random intersection graphs with tunable degree distribution and clustering. Probab. Eng. Inf. Sci.. 2009, 23 661-674

[15] Esary JD, Proschan F, Walkup DW. Association of random variables, with applications. Ann. Math. Stat.. 1967, 38 1466-1474

[16] Fill JA, Scheinerman ER, Singer-Cohen KB. Random intersection graphs when $m=\omega (n)$: An equivalence theorem relating the evolution of the $G(n, m, p)$ and $G(n, p)$ models. Random Struct. Algorithms. 2000, 16 156-176

[17] Grimmett R. Percolation. 1999 2 New York: Springer

[18] Janson S, Luczak T, Ruciński A. Random Graphs. 2000 New York: Wiley

[19] Karjalainen, J., Leskelä, L.: Moment-based parameter estimation in binomial random intersection graph models. Algorithms and models for the web graph, pp. 1–15, Lecture Notes in Comput. Sci., 10519. Springer, Cham (2017)

[20] Karoński M, Scheinerman ER, Singer-Cohen KB. On random intersection graphs: the subgraph problem. Comb. Probab. Comput.. 1999, 8 131-159

[21] Kim J, Lee SJ, Na J. On the total variation distance between the binomial random graph and the random intersection graph. Random Struct. Algorithms. 2018, 52 662-679

[22] Krokowski, K., Reichenbachs, A., Tha̋le, C.: Discrete Malliavin-Stein method: Berry-Esseen bounds for random graphs and percolation. Ann. Probab. 45, 1071–1109 (2017)

[23] Lagerås, A.N., Lindholm, M.: A note on the component structure in random intersection graphs with tunable clustering. Electron. J. Combin.15 # N10 (2008)

[24] Newman CM. Normal fluctuations and the FKG inequalities. Commun. Math. Phys.. 1980, 74 119-128

[25] Pietro, R.D., Mancini, L.V., Mei, A. Radhakrishnan, J.: How to design connected sensor networks that are provably secure. Sec. Commun. (2006) http://delis.upb.de/paper/DELIS-TR-0360.pdf

[26] Rennie BC, Dobson AJ. On stirling numbers of the second kind. J. Combin. Theory. 1969, 7 116-121

[27] Röllin, A.: Kolmogorov bounds for the normal approximation of the number of triangles in the Erdős–Rényi random graph. Preprint. (2017) arXiv:1704.00410

[28] Ruciński A. When are small subgraphs of a random graph normally distributed?. Probab. Theory Rel. Fields. 1988, 78 1-10

[29] Rybarczyk K. Diameter, connectivity, and phase transition of the uniform random intersection graph. Discrete Math.. 2011, 311 1998-2019

[30] Rybarczyk K, Stark D. Poisson approximation of the number of cliques in random intersection graphs. J. Appl. Probab.. 2010, 47 826-840

[31] Singer-Cohen, K.B.: Random intersection graphs. Ph.D. thesis, Department of Mathematical Sciences, The John Hopkins University (1995)

[32] Stark D. The vertex degree distribution of random intersection graphs. Random Struct. Algorithms. 2004, 24 249-258

[33] Stein, C.: A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In: Proceedings of the Sixth Berkeley Symposium on Mathematics Statistics and Probability, Vol. II: Probability theory, pp. 583–602 (1972)

[34] Tikhomirov AN. Convergence rate in the central limit theorem for weakly dependent random variables. Theory Probab. Appl.. 1980, 25 790-809

Funding

National Natural Science Foundation of China(12071251)