Clustering in a preferential attachment random graph with edge-steps – 2019

with C. Alves (U. Leipzig) and R. Sanchis (UFMG) – Journal of Applied Probability

Abstract

In this paper we investigate geometric properties of graphs generated by a preferential attachment random graph model with edge-steps. More precisely, at each time t∈N, with probability p a new vertex is added 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 that the global clustering coefficient decays as $t^{\gamma(p)}$ for a positive function $\gamma$ of p. We also prove that the clique number of these graphs is, up to sub-polynomially small factors, of order $t^{(1−p)/(2−p)}$