We have introduced a new continuous-time network evolution model. We have described cooperation, so we have considered the cliques of nodes. The evolution of the network was based on cliques of nodes of the network and was governed by a branching process. The basic properties of the evolution process were described. Asymptotic theorems were proved for the number of cliques having a fixed size and the degree of a fixed node. The generating function was calculated, and then the probability of extinction was obtained. For the proof, advanced results of multi-type branching processes were used. Besides precise mathematical proofs, simulation examples also supported our results.
Citation: István Fazekas, Attila Barta, László Fórián, Bettina Porvázsnyik. A continuous-time network evolution model describing $ N $-interactions[J]. AIMS Mathematics, 2024, 9(12): 35721-35742. doi: 10.3934/math.20241695
We have introduced a new continuous-time network evolution model. We have described cooperation, so we have considered the cliques of nodes. The evolution of the network was based on cliques of nodes of the network and was governed by a branching process. The basic properties of the evolution process were described. Asymptotic theorems were proved for the number of cliques having a fixed size and the degree of a fixed node. The generating function was calculated, and then the probability of extinction was obtained. For the proof, advanced results of multi-type branching processes were used. Besides precise mathematical proofs, simulation examples also supported our results.
[1] | A. L. Barabási, Network science, Cambridge University Press: Cambridge, UK, 2018. |
[2] | B. Bollobás, O. Riordan, Random graphs and branching processes, In: B. Bollobás, R. Kozma, D. Miklós (Eds.), Handbook of Large-Scale Random Networks, Bolyai Society Mathematical Studies, Springer: Berlin, Heidelberg, 18 (2008). https://doi.org/10.1007/978-3-540-69395-6_1 |
[3] | A. Rudas, B. Tóth, B. Valkó, Random trees and general branching processes, Random Struct. Algor., 31 (2007), 186–202. https://doi.org/10.1002/rsa.20137 doi: 10.1002/rsa.20137 |
[4] | A. Rudas, B. Tóth, Random tree growth with branching processes — A survey, In: B. Bollobás, R. Kozma, D. Miklós (Eds.), Handbook of Large-Scale Random Networks, Bolyai Society Mathematical Studies, Springer: Berlin, Heidelberg, 18, (2008). https://doi.org/10.1007/978-3-540-69395-6_4 |
[5] | K. B. Athreya, A. P. Ghosh, S. Sethuraman, Growth of preferential attachment random graphs via continuous-time branching processes, P. Indian AS-Math. Sci., 118 (2008), 473–494. https://doi.org/10.1007/s12044-008-0036-2 doi: 10.1007/s12044-008-0036-2 |
[6] | F. Gao, A. van der Vaart, R. Castro, R. van der Hofstad, Consistent estimation in general sublinear preferential attachment trees, Electron. J. Stat., 11 (2017), 3979–3999. https://doi.org/10.1214/17-EJS1356 doi: 10.1214/17-EJS1356 |
[7] | C. Holmgren, S. Janson, Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees, Probab. Surv., 14 (2017), 53–154. https://doi.org/10.1214/16-PS272 doi: 10.1214/16-PS272 |
[8] | S. Rosengren, A multi-type preferential attachment tree, Internet Math., 1 (2018). https://doi.org/10.24166/im.05.2018 |
[9] | S. Banerjee, X. Huang, Degree centrality and root finding in growing random networks, Electron. J. Probab., 28 (2023), 1–39. https://doi.org/10.1214/23-EJP930 doi: 10.1214/23-EJP930 |
[10] | A. Iksanov, K. Kolesko, M. Meiners, Asymptotic fluctuations in supercritical Crump-Mode-Jagers processes, Ann. Probab., 52 (2024), 1538–1606. https://doi.org/10.1214/24-AOP1697 doi: 10.1214/24-AOP1697 |
[11] | T. F. Móri, S. Rokob, Moments of general time dependent branching processes with applications, Acta Math. Hung., 159 (2019), 131–149. https://doi.org/10.1007/s10474-019-00976-9 doi: 10.1007/s10474-019-00976-9 |
[12] | Á. Backhausz, T. F. Móri, A random graph model based on 3-interactions, Ann. Univ. Sci. Budapest. Sect. Comput., 36 (2012), 41–52. |
[13] | I. Fazekas, B. Porvázsnyik, Scale-free property for degrees and weights in an N-interactions random graph model, J. Math. Sci., 214 (2016), 69–82. https://doi.org/10.1007/s10958-016-2758-5 doi: 10.1007/s10958-016-2758-5 |
[14] | T. F. Móri, S. Rokob, A random graph model driven by time-dependent branching dynamics, Ann. Univ. Sci. Budapest. Sect. Comp., 46 (2017), 191–213. |
[15] | I. Fazekas, A. Barta, A continuous-time network evolution model describing 2- and 3-interactions, Mathematics, 9 (2021), 3143. https://doi.org/10.3390/math9233143 doi: 10.3390/math9233143 |
[16] | Q. Feng, X. Li, Z. Hu, Asymptotic degree distribution in a homogeneous evolving network model, Stat. Probabil. Lett., 193 (2023), 109740. https://doi.org/10.1016/j.spl.2022.109740 doi: 10.1016/j.spl.2022.109740 |
[17] | M. Deijfen, R. Fitzner, Birds of a feather or opposites attract-effects in network modelling, arXiv Preprint, 2017. https://doi.org/10.48550/arXiv.1612.03127 |
[18] | A. Iksanov, M. Meiners, Rate of convergence in the law of large numbers for supercritical general multi-type branching processes, Stoch. Proc. Appl., 125 (2015), 708–738. https://doi.org/10.1016/j.spa.2014.10.004 doi: 10.1016/j.spa.2014.10.004 |
[19] | P. Jagers, Branching processes with biological applications, Wiley: London, 1975. |
[20] | P. Haccou, P. Jagers, V. A. Vatunin, Branching processes: Variation, growth, and extinction of populations, Cambridge University Press: Cambridge, UK, 2005. |
[21] | C. J. Mode, Multitype branching processes: Theory and applications, American Elsevier: New York, USA, 1971. |
[22] | O. Nerman, On the convergence of supercritical general branching processes, PhD Theses, University of Göteborg, 1979. |
[23] | O. Nerman, On the convergence of supercritical general (C-M-J) branching processes, Z. Wahrsch. Verw. Gebiete, 57 (1981), 365–395. https://doi.org/10.1007/BF00534830 doi: 10.1007/BF00534830 |
[24] | E. Seneta, Non-negative matrices and Markov chains, Springer: New York, USA, 1981. https://doi.org/10.1007/0-387-32792-4 |
[25] | Simulation codes for the article 'A continuous-time network evolution model describing N-interactions', 2024. Available from: https://github.com/bartaa89/n_interact. |