LUSTERING IN PREFERENTIAL ATTACHMENT RANDOM GRAPHS WITH EDGE-STE

Author(s)

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

Affiliation

^[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

• Document type: Journal article
• Source: JOURNAL OF APPLIED PROBABILITY; v. 58, n. 4, p. 890-908, DEC 2021.
• Web of Science Citations: 0

Abstract

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)

• FAPESP's process: 13/24928-2 - Random walks and dependent percolation
• Grantee: Caio Teodoro de Magalhães Alves
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 15/18930-0 - Decoupling in correlated percolation models
• Grantee: Caio Teodoro de Magalhães Alves
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor