1. Clustering in preferential attachment random graphs with edge-step
- Author
-
Caio Alves, Remy Sanchis, and Rodrigo Ribeiro
- Subjects
Statistics and Probability ,Random graph ,General Mathematics ,Complex network ,Preferential attachment ,Vertex (geometry) ,Combinatorics ,Spatial network ,ComputingMethodologies_DOCUMENTANDTEXTPROCESSING ,Statistics, Probability and Uncertainty ,Concentration inequality ,Cluster analysis ,Mathematics ,Clustering coefficient - Abstract
We prove concentration inequality results for geometric graph properties of an instance of the Cooper–Frieze [5] preferential attachment model withedge-steps. More precisely, we investigate a random graph model that at each time$t\in \mathbb{N}$, with probabilitypadds a new vertex to the graph (avertex-stepoccurs) or with probability$1-p$an edge connecting two existent vertices is added (anedge-stepoccurs). We prove concentration results for theglobal clustering coefficientas well as theclique number. More formally, we prove that the global clustering, with high probability, decays as$t^{-\gamma(p)}$for a positive function$\gamma$ofp, whereas the clique number of these graphs is, up to subpolynomially small factors, of order$t^{(1-p)/(2-p)}$.
- Published
- 2021