Clustering in preferential attachment random graphs with edge-step. (December 2021)

• Record Type: Journal Article
• Authors: Alves, Caio; Ribeiro, Rodrigo; Sanchis, Rémy
• Is Part Of: Journal of applied probability. Volume 58:Number 4(2021)
• Page Start: 890
• Page End: 908
• Publication Date: 2021-12
• Subjects: Complex networks -- clustering coefficients -- concentration bounds -- transitivity -- clique number; 05C82 -- 60K40 -- 68R10; 519.2
• DOI: 10.1017/jpr.2021.20
• Languages: English
• ISSNs: 0021-9002

Abstract

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^{-\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)}$ .