Diameter of P.A. random graphs with edge-step functions
| Autor: | Alves, Caio, Ribeiro, Rodrigo, Sanchis, Remy |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Random Struct Alg. 2020; 57: 612-636 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1002/rsa.20929 |
| Popis: | 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:\mathbb{N}\to[0,1]$ that drives the asymptotic proportion between the numbers of vertices and edges. These results are sharp when $f$ is a \textit{regularly varying function at infinity} with strictly negative index of regular variation~$-\gamma$. For this particular class, we prove a characterization for the diameter that depends only on~$-\gamma$. More specifically, we prove that the diameter of such graphs is of order $1/\gamma$ with high probability, although its vertex set order goes to infinity polynomially. Sharp results for the diameter for a wide class of \textit{slowly varying functions} are also obtained. Comment: After referee recommendation, all results not concerning the diameter have been removed to obtain a more streamlined paper. The paper has been published at Random Structures and Algorithms under the new title |
| Databáze: | arXiv |
| Externí odkaz: |
|