Clustering and Cliques in P.A random graphs with edge insertion

arXiv2307.03732MaRDI QIDQ6442998FDOQ6442998

Caio Alves, Rodrigo Ribeiro, Rémy Sanchis

Publication date: 7 July 2023

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Other physical applications of random processes (60K40)

This page was built for publication: Clustering and Cliques in P.A random graphs with edge insertion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442998)