Clustering in preferential attachment random graphs with edge-step. (December 2021) - Alves, Caio; Ribeiro, Rodrigo; Sanchis, Rémy
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\in \mathbb{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^{-γ(p)}$ for a positive function $γ$ of p, whereas the clique number of these graphs is, up to subpolynomially small factors, of order $t^{(1-p)/(2-p)}$ .