Diameter of P.A. random graphs with edge-step functions

DOI10.1002/RSA.20929MaRDI QIDQ5136926zbMATH OpenOpenAlexFDO

Authors Caio Alves, Rodrigo Ribeiro, Rémy Sanchis

Publication date 30 November 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.10165

zbMATH Keywords

cliquescomplex networksconcentration boundsdiameterpreferential attachmentscale-freesmall-world

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Extreme value theory; extremal stochastic processes (60G70)

Abstract: In this work we prove general bounds for the diameter of random graphs generated by a preferential attachment model whose parameter is a function $f:mathbbNo[0,1]$ that drives the asymptotic proportion between the numbers of vertices and edges. These results are sharp when $f$ is a extit{regularly varying function at infinity} with strictly negative index of regular variation~$-gamma$. For this particular class, we prove a characterization for the diameter that depends only on~$-gamma$. More specifically, we prove that the diameter of such graphs is of order $1/gamma$ with high probability, although its vertex set order goes to infinity polynomially. Sharp results for the diameter for a wide class of extit{slowly varying functions} are also obtained.

Recommendations

• Preferential attachment random graphs with edge-step functions
• Diameters in preferential attachment models
• The diameter of a scale-free random graph
• Diameter in ultra-small scale-free random graphs
• Preferential attachment random graphs with general weight function

Cited in

(6)

• Probability of diameter two for Steinhaus graphs
• \(\gamma\)-variable first-order logic of uniform attachment random graphs
• Preferential attachment random graphs with edge-step functions
• Spread of infection over P.A. random graphs with edge insertion
• Diameter in ultra-small scale-free random graphs
• Clustering and cliques in preferential attachment random graphs with edge insertion

This page was built for publication: Diameter of P.A. random graphs with edge-step functions

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