Diameter of PA random graphs with edge-step functions

Autor(es)

Alves, Caio ^[1] ; Ribeiro, Rodrigo ^[2] ; Sanchis, Remy ^[3]

Afiliação do(s) autor(es)

^[1] Univ Leipzig, Inst Math, Leipzig - Germany

^[2] PUC Chile, Macul - Chile

^[3] Univ Fed Minas Gerais, Dept Matemat, Belo Horizonte, MG - Brazil

• Tipo de documento: Artigo Científico
• Fonte: RANDOM STRUCTURES & ALGORITHMS; v. 57, n. 3 MAY 2020.
• Citações Web of Science: 0

Resumo

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 -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 slowly varying functions are also obtained. (AU)

• Processo FAPESP: 15/18930-0 - Desacoplamento em modelos de percolação com correlação
• Beneficiário: Caio Teodoro de Magalhães Alves
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 13/24928-2 - Passeios aleatórios e percolação dependente
• Beneficiário: Caio Teodoro de Magalhães Alves
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado