Agglomeration in a preferential attachment random graph with edge-steps

MaRDI QIDQ6312182zbMATH OpenFDO

Authors Caio Alves, Rodrigo Ribeiro, Rémy Sanchis

Publication date 8 January 2019

Mathematics Subject Classification ID

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

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 $tinmathbbN$, 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^{-gamma(p)}$ for a positive function $gamma$ 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)}$.

This page was built for publication: Agglomeration in a preferential attachment random graph with edge-steps

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