Agglomeration in a preferential attachment random graph with edge-steps

2019/01/08 by Alves, Caio, Ribeiro, Rodrigo, Sanchis, Remy
#05C82 (Primary) #60K40 #68R10 (Secondary) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1901.02486

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∈ℕ, 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^-γ(p) for a positive function γ 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).

Related

• Clustering and Cliques in P.A random graphs with edge insertion
• Preferential Attachment Random Graphs with Edge-Step Functions
• The Fine Structure of Preferential Attachment Graphs I: Somewhere-Denseness
• De-Preferential Attachment Random Graphs
• Growth of preferential attachment random graphs via continuous-time branching processes