LUSTERING IN PREFERENTIAL ATTACHMENT RANDOM GRAPHS WITH EDGE-STE

Autor(es)

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

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

^[1] Univ Leipzig, Fac Math & Comp Sci, Leipzig - Germany

^[2] Pontificia Univ Catolica Chile, Math, Santiago - Chile

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

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF APPLIED PROBABILITY; v. 58, n. 4, p. 890-908, DEC 2021.
• Citações Web of Science: 0

Resumo

We prove concentration inequality results for geometric graph properties of an instance of the Cooper-Frieze {[}5] preferential attachment model with edge-steps. More precisely, we investigate a random graph model that at each time t epsilon N, with probability p adds a new vertex to the graph (a vertex-step occurs) or with probability 1 - p an edge connecting two existent vertices is added (an edge-step occurs). We prove concentration results for the global clustering coefficient as well as the clique number. More formally, we prove that the global clustering, with high probability, decays as t-(gamma(p)) for a positive function gamma of p, whereas the clique number of these graphs is, up to subpolynomially small factors, of order t((1-p)/(2-p)). (AU)

• 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
• 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