Clustering and Cliques in Preferential Attachment Random Graphs with Edge Insertion

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)\) $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  \(-\gamma \) $-\gamma$ , where \(\gamma \in [0,1)\) $\gamma \in [0,1)$ . We also demonstrate an inverse relation between these two statistics: the clique number is essentially the reciprocal of the global clustering coefficient.