2023/07/07 by Caio Alves, Alves, Caio, Rodrigo Ribeiro +3
Computer Science · Mathematics · Physics and Astronomy · #68R10 #Advanced Graph Theory Research #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Primary 05C82 #Probability (math.PR) #Secondary 60K40
paper · pdf · doi:10.48550/arxiv.2307.03732
openalex publication_date 2023/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we investigate the global clustering coefficient (a.k.a transitivity) and clique number of graphs generated by a preferential attachment random graph model with an additional feature of allowing edge connections between existing vertices. Specifically, at each time step t, either a new vertex is added with probability f(t), or an edge is added between two existing vertices with probability 1-f(t). We establish concentration inequalities for the global clustering and clique number of the resulting graphs under the assumption that f(t) is a regularly varying function at infinity with index of regular variation -γ, where γ∈ [0,1). We also demonstrate an inverse relation between these two statistics: the clique number is essentially the reciprocal of the global clustering coefficient.