Geometric preferential attachment with choice-based edge step
Yu.A. Malyshkin
Tver State University
DOI: 10.26456/pcascnn/2024.16.381
Short communication
Abstract: We study the asymptotic behavior of the maximum degree in the geometric graph model with a preferential attachment choice-based edge step. Geometric graphs are natural models that describe some nanoscale systems, while preferential attachment provides a good description of complex networks, particularly different neural networks. The model is a recursively built sequence of graphs. We start with the initial graph on a single vertex and we add a new vertex and draw a few edges on each step. Each vertex is assigned a parameter that represents its location. The recursion step consists of two parts. First, we introduce a new vertex and draw edges to close enough vertices. This step represents the geometric part of the model. Then, we draw edges between vertices by preferential attachment with the choice rule. We prove that dependent on model parameters, the maximum degree could exhibit sublinear (similar to the standard preferential attachment) and linear (representing concentration effect) behavior.
Keywords: geometric graphs, complex networks, random graphs, preferential attachment, power of choice
- Yury A. Malyshkin – Ph. D., Docent of Applied Mathematics and Cybernetics Department, Tver State University
Reference:
Malyshkin, Yu.A. Geometric preferential attachment with choice-based edge step / Yu.A. Malyshkin // Physical and chemical aspects of the study of clusters, nanostructures and nanomaterials. — 2024. — I. 16. — P. 381-386. DOI: 10.26456/pcascnn/2024.16.381. (In Russian).
Full article (in Russian): download PDF file
References:
1. Živkovic J., Tadic B. Nanonetworks: The graph theory framework for modeling nanoscale systems. Nanoscale Systems: Mathematical Modeling, Theory and Applications, 2013, vol. 2, pp. 30-48. DOI: 10.2478/nsmmt-2013-0003.
2. Vecchio D.A., Mahler S.H., Hammig M.D., Kotov N.A. Structural analysis of nanoscale network materials using graph theory. ACS Nano, 2021, vol. 15, issue 8, pp. 12847-12859. DOI: 10.1021/acsnano.1c04711.
3. Rana M.M., Nguyen D.D. Geometric graph learning to predict changes in binding free energy and protein thermodynamic stability upon mutation, The Journal of Physical Chemistry Letters, 2023, vol. 14, issue 49, pp. 10870-10879. DOI: 10.1021/acs.jpclett.3c02679.
4. Barabási A., Albert R. Emergence of scaling in random networks, Science, 1999, vol. 286, issue 5439, pp. 509-512. DOI: 10.1126/science.286.5439.509.
5. Móri T.F. On random trees, Studia Scientiarum Mathematicarum Hungarica, 2002, vol. 39, issue 1-2, pp. 143-155. DOI: 10.1556/SScMath.39.2002.1-2.9.
6. Móri T.F. The maximum degree of the Barabási-Albert random tree, Combinatorics, Probability and Computing, 2005, vol. 14, issue 3, pp. 339-348. DOI: 10.1017/S0963548304006133.
7. Haslegrave J., Jordan J. Preferential attachment with choice, Random Structures and Algorithms, 2016, vol. 48, issue 4, pp. 751-766. DOI: 10.1002/rsa.20616.
8. Krapivsky P.L, Redner S. Choice-driven phase transition in complex networks, Journal of Statistical Mechanics: Theory and Experiment, 2014, vol. 2014, art. no. P04021, 14 p. DOI: 10.1088/1742-5468/2014/04/P04021.
9. Malyshkin Y. Preferential attachment combined with the random number of choices, Internet Mathematics, 2018, vol. 1, issue 1, pp. 1-25. DOI: 10.24166/im.01.2018.
10. Malyshkin Y., Paquette E. The power of choice combined with preferential attachment, Electronic Communications in Probability, 2014, vol. 19, issue 44, pp. 1-13. DOI: 10.1214/ECP.v19-3461.
11. Haslegrave J., Jordan J., Yarrow M. Condensation in preferential attachment models with location-based choicem Random Structures and Algorithms, 2020, vol. 56, issue 3, pp. 775-795. DOI: 10.1002/rsa.20889.
12. Malyshkin Y. Sublinear preferential attachment combined with a growing number of choices, Electronic Communications in Probability, 2020, vol. 25, issue 87, pp. 1-12. DOI: 10.1214/20-ECP368.
13. Malyshkin Y., Paquette E. The power of choice over preferential attachment, Latin American Journal of Probability and Mathematical Statistics, 2015, vol. 12, issue 2, pp. 903-915.
14. Alves C., Ribeiro R., Sanchis R. Preferential attachment random graphs with edge-step functions, Journal of Theoretical Probability, 2021, vol. 34, issue 1, pp. 438-476. DOI: 10.1007/s10959-019-00959-0.
15. Chen H.F. Stochastic approximation and its applications, Nonconvex Optimization and Its Applications. New York, Springer, 2002, vol. 64, XV, 360 p. DOI: 10.1007/b101987.
16. Malyshkin Y. Preferential attachment with choice-based edge step. Available at: https://arxiv.org/abs/2309.16591 (accessed 01.08.2024). DOI: 10.48550/arXiv.2309.16591.