On the dense preferential attachment graph models and their graphon induced counterpart

DOI10.1017/JPR.2019.34MaRDI QIDQ5226260zbMATH OpenOpenAlexFDO

Authors Dávid Kunszenti-Kovács, Ágnes Backhausz

Publication date 31 July 2019

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.06760, http://real.mtak.hu/101244/7/1701.06760.pdf

zbMATH Keywords

cut normdense graph limitjumble normPólya urn process

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80) Applications of graph theory (05C90)

Abstract: Letting $mathcalM$ denote the space of finite measures on $mathbbN$, and $m{u}_{l}ambdainmathcalM$ denote the Poisson distribution with parameter $lambda$, the function $W:[0,1{]}^{2}omathcalM$ given by [ W(x,y)=mu_{clog xlog y} ] is called the PAG graphon with density $c$. It is known that this is the limit, in the multigraph homomorphism sense, of the dense Preferential Attachment Graph (PAG) model with edge density $c$. This graphon can then in turn be used to generate the so-called W-random graphs in a natural way. The aim of this paper is to compare the dense PAG model with the W-random graph model obtained from the corresponding graphon. Motivated by the multigraph limit theory, we investigate the expected jumble norm distance of the two models in terms on the number of vertices $n$. We present a coupling for which the expectation can be bounded from above by $O(lo{g}^{2}ncdot{n}^{-1/3})$, and provide a universal lower bound that is coupling independent, but with a worse exponent.

Recommendations

• Multigraph limit of the dense configuration model and the preferential attachment graph
• An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Superlogarithmic cliques in dense inhomogeneous random graphs
• Isomorphism and embedding problems for infinite limits of scale-free graphs

Cites work

• A preferential attachment process approaching the Rado graph
• A survey of random processes with reinforcement
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Emergence of Scaling in Random Networks
• Ferguson distributions via Polya urn schemes
• Generalized Dirichlet distribution in Bayesian analysis
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3357742 (Why is no real title available?)
• Identifiability for graphexes and the weak kernel metric
• Introduction to Random Graphs
• Large networks and graph limits
• Limits of randomly grown graph sequences
• Multigraph limit of the dense configuration model and the preferential attachment graph
• Multigraph limits, unbounded kernels, and Banach space decorated graphs
• On the Convergence of Moments in the Central Limit Theorem
• On the Rate of Convergence of Moments in the Central Limit Theorem for Lattice Distributions
• Preferential attachment processes approaching the Rado multigraph
• Random graph dynamics

Cited in

(2)

• Multigraph limit of the dense configuration model and the preferential attachment graph
• High Degree Vertices and Eigenvalues in the Preferential Attachment Graph

This page was built for publication: On the dense preferential attachment graph models and their graphon induced counterpart

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