On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities. (English) Zbl 1511.05209
Summary: We analyze a dynamic random undirected graph in which newly added vertices are connected to those already present in the graph either using, with probability \(p\), an anti-preferential attachment mechanism or, with probability \(1 - p\), a preferential attachment mechanism. We derive the asymptotic degree distribution in the general case and study the asymptotic behavior of the expected degree process in the general and that of the degree process in the pure anti-preferential attachment case. Degree homogenization mainly affects convergence rates for the former case and also the limiting degree distribution in the latter. Lastly, we perform a simulative study of a variation of the introduced model allowing for anti-preferential attachment probabilities given in terms of the current maximum degree of the graph.
References:
| [1] | Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223 |
| [2] | Bollobás, B.; Riordan, O.; Spencer, J.; Tusnády, G., The degree sequence of a scale-free random graph process, Random Struct. Algorithms, 18, 3, 279-290 (2001) · Zbl 0985.05047 |
| [3] | van der Hofstad, R., (Random graphs and complex networks. Vol. 1. Random graphs and complex networks. Vol. 1, Cambridge Series in Statistical and Probabilistic Mathematics, [43] (2017), Cambridge University Press: Cambridge University Press Cambridge), xvi+321 · Zbl 1361.05002 |
| [4] | Newman, M. E.; Barabási, A.-L. E.; Watts, D. J., The Structure and Dynamics of Networks (2006), Princeton University Press · Zbl 1362.00042 |
| [5] | Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 2, 167-256 (2003) · Zbl 1029.68010 |
| [6] | Krapivsky, P. L.; Redner, S.; Leyvraz, F., Connectivity of growing random networks, Phys. Rev. Lett., 85, 21, 4629 (2000) |
| [7] | Krapivsky, P. L.; Redner, S., Organization of growing random networks, Phys. Rev. E, 63, 6, Article 066123 pp. (2001) |
| [8] | Athreya, K. B., Preferential attachment random graphs with general weight function, Internet Math., 4, 4, 401-418 (2007) · Zbl 1238.05241 |
| [9] | Dereich, S.; Mörters, P., Random networks with sublinear preferential attachment: degree evolutions, Electron. J. Probab., 14, 43, 1222-1267 (2009) · Zbl 1185.05127 |
| [10] | Dereich, S.; Mörters, P., Random networks with sublinear preferential attachment: the giant component, Ann. Probab., 41, 1, 329-384 (2013) · Zbl 1260.05143 |
| [11] | Betken, C.; Döring, H.; Ortgiese, M., Fluctuations in a general preferential attachment model via Stein’s method, Random Struct. Algorithms, 55, 808-830 (2019) · Zbl 1433.05273 |
| [12] | Collevecchio, A.; Cotar, C.; LiCalzi, M., On a preferential attachment and generalized Pólya’s urn model, Ann. Appl. Probab., 23, 3, 1219-1253 (2013) · Zbl 1266.05150 |
| [13] | Broido, A. D.; Clauset, A., Scale-free networks are rare, Nat. Commun., 10, 1, 1017 (2019) |
| [14] | Cooper, C.; Frieze, A., A general model of web graphs, Random Struct. Algorithms, 22, 3, 311-335 (2003) · Zbl 1018.60007 |
| [15] | Pachon, A.; Sacerdote, L.; Yang, S., Scale-free behavior of networks with the copresence of preferential and uniform attachment rules, Physica D, 371, 1-12 (2018) · Zbl 1390.90140 |
| [16] | Cooper, C.; Frieze, A.; Vera, J., Random deletion in a scale-free random graph process, Internet Math., 1, 4, 463-483 (2004) · Zbl 1080.60006 |
| [17] | Wu, X.-Y.; Dong, Z.; Liu, K.; Cai, K.-Y., On the degree sequence of an evolving random graph process and its critical phenomenon, J. Appl. Probab., 46, 4, 1213-1220 (2009) · Zbl 1228.05123 |
| [18] | Cai, K.-Y.; Dong, Z.; Liu, K.; Wu, X.-Y., Phase transition on the degree sequence of a random graph process with vertex copying and deletion, Stochastic Process. Appl., 121, 4, 885-895 (2011) · Zbl 1218.60084 |
| [19] | Lansky, P.; Polito, F.; Sacerdote, L., The role of detachment of in-links in scale-free networks, J. Phys. A, 47, 34, Article 345002 pp. (2014) · Zbl 1296.90129 |
| [20] | Vallier, T., Robustness of preferential attachment under deletion of edges, Stoch. Models, 23, 2, 265-276 (2007) · Zbl 1125.05097 |
| [21] | Lindholm, M.; Vallier, T., On the degree evolution of a fixed vertex in some growing networks, Statist. Probab. Lett., 81, 6, 673-677 (2011) · Zbl 1213.62007 |
| [22] | Britton, T.; Lindholm, M.; Turova, T., A dynamic network in a dynamic population: asymptotic properties, J. Appl. Probab., 48, 4, 1163-1178 (2011) · Zbl 1231.92054 |
| [23] | Britton, T.; Lindholm, M., Dynamic random networks in dynamic populations, J. Stat. Phys., 139, 3, 518-535 (2010) · Zbl 1190.82037 |
| [24] | Johansson, T., Deletion of oldest edges in a preferential attachment graph (2016), preprint arXiv:1610.04588 |
| [25] | Hansen, J. C.; Jaworski, J., Random mappings with exchangeable in-degrees, Random Struct. Algorithms, 33, 1, 105-126 (2008) · Zbl 1152.60306 |
| [26] | Sendiña-Nadal, I.; Danziger, M. M.; Wang, Z.; Havlin, S.; Boccaletti, S., Assortativity and leadership emerge from anti-preferential attachment in heterogeneous networks, Sci. Rep., 6, Article 21297 pp. (2016) |
| [27] | B. Viswanath, A. Mislove, M. Cha, K.P. Gummadi, On the evolution of user interaction in facebook, in: Proceedings of the 2nd ACM Workshop on Online Social Networks, 2009, pp. 37-42, http://dx.doi.org/10.1145/1592665.1592675. |
| [28] | Teller Amado, S.; Granell, C.; De Domenico, M.; Soriano i. Fradera, J.; Gómez, S.; Arenas, À., Emergence of assortative mixing between clusters of cultured neurons, PLoS Comput. Biol., 10, 9, Article e100396 pp. (2014) |
| [29] | de Santos-Sierra, D.; Sendina-Nadal, I.; Leyva, I.; Almendral, J. A.; Anava, S.; Ayali, A.; Papo, D.; Boccaletti, S., Emergence of small-world anatomical networks in self-organizing clustered neuronal cultures, PLoS One, 9, 1, Article e85828 pp. (2014) |
| [30] | Sethuraman, S.; Venkataramani, S. C., On the growth of a superlinear preferential attachment scheme, (Probability and Analysis in Interacting Physical Systems. Probability and Analysis in Interacting Physical Systems, Springer Proc. Math. Stat., vol. 283 (2019), Springer, Cham), 243-265 · Zbl 1436.60039 |
| [31] | Tricomi, F. G.; Erdélyi, A., The asymptotic expansion of a ratio of gamma functions, Pacific J. Math., 1, 133-142 (1951) · Zbl 0043.29103 |
| [32] | Doob, J. L., Regularity properties of certain families of chance variables, Trans. Amer. Math. Soc., 47, 455-486 (1940) · JFM 66.0609.04 |
| [33] | Newman, M. E., Assortative mixing in networks, Phys. Rev. Lett., 89, 20, Article 208701 pp. (2002) |
| [34] | Hou, Z.; Tong, J.; Shi, D., Markov chain-based analysis of the degree distribution for a growing network, Acta Math. Sci. Ser. B (Engl. Ed.), 31, 1, 221-228 (2011) · Zbl 1240.05276 |
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.
