Abstract
In this work we prove general bounds for the diameter of random graphs generated by a preferential attachment model whose parameter is a function f:N→[0,1] that drives the asymptotic proportion between the numbers of vertices and edges. These results are sharp when f is a regularly varying function at infinity with strictly negative index of regular variation −γ. For this particular class, we prove a characterization for the diameter that depends only on −γ. More specifically, we prove that the diameter of such graphs is of order 1/γ with high probability, although its vertex set order goes to infinity polynomially. Sharp results for the diameter for a wide class of slowly varying functions are also obtained.
| Original language | English |
|---|---|
| Pages (from-to) | 612-636 |
| Number of pages | 25 |
| Journal | Random Structures and Algorithms |
| Volume | 57 |
| Issue number | 3 |
| DOIs | |
| State | Published - Oct 1 2020 |
| Externally published | Yes |
Funding
We are thankful to Roberto Imbuzeiro Oliveira for the many inspiring and pleasant conversations. C.A. was partially supported by Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP), grants 2013/24928‐2 and 2015/18930‐0, and by the DFG grant SA 3465/1‐1. . was partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) and by the project Stochastic Models of Disordered and Complex Systems. The Stochastic Models of Disordered and Complex Systems is a Millennium Nucleus (NC120062) supported by the Millennium Scientific Initiative of the Ministry of Science and Technology (Chile). R.S. has been partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) and by FAPEMIG (Programa Pesquisador Mineiro), grant PPM 00600/16. R.R This research was supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP), 2013/24928‐2 and 2015/18930‐0. DFG, SA 3465/1‐1, Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), Stochastic Models of Disordered and Complex Systems is a Millennium Nucleus, NC120062. Millennium Scientific Initiative of the Ministry of Science and Technology (Chile), FAPEMIG (Programa Pesquisador Mineiro), PPM 00600/16. Funding information We are thankful to Roberto Imbuzeiro Oliveira for the many inspiring and pleasant conversations. C.A. was partially supported by Funda??o de Amparo ? Pesquisa do Estado de S?o Paulo (FAPESP), grants 2013/24928-2 and 2015/18930-0, and by the DFG grant SA 3465/1-1. R.R. was partially supported by Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico (CNPq) and by the project Stochastic Models of Disordered and Complex Systems. The Stochastic Models of Disordered and Complex Systems is a Millennium Nucleus (NC120062) supported by the Millennium Scientific Initiative of the Ministry of Science and Technology (Chile). R.S. has been partially supported by Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico (CNPq) and by FAPEMIG (Programa Pesquisador Mineiro), grant PPM 00600/16.
Keywords
- cliques
- complex networks
- concentration bounds
- diameter
- preferential attachment
- scale-free
- small-world