ON THE DENSE PREFERENTIAL ATTACHMENT GRAPH MODELS AND THEIR GRAPHON INDUCED COUNTERPART

Backhausz, Ágnes and Kunszenti-Kovács, Dávid (2019) ON THE DENSE PREFERENTIAL ATTACHMENT GRAPH MODELS AND THEIR GRAPHON INDUCED COUNTERPART. Journal of Applied Probability, 56 (2). pp. 590-601. ISSN 0021-9002

	Text ap16547_final.pdf - Accepted Version Restricted to Registered users only Download (400kB)
Preview	Text 1701.06760.pdf Download (290kB) | Preview

Abstract

Letting $\mathcal{M}$ denote the space of finite measures on $\mathbb{N}$, and $\mu_\lambda\in\mathcal{M}$ denote the Poisson distribution with parameter $\lambda$, the function $W:[0,1]^2\to\mathcal{M}$ given by $W(x,y)=\mu_{c\log x\log 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, and similar constructions also work in the slightly more general context of the so-called $\mathrm{PAG}_{\kappa}$ models.\\ The aim of this paper is to compare these dense $\mathrm{PAG}_{\kappa}$ models with the W-random graph models obtained from the corresponding graphons. Motivated by the multigraph limit theory, we investigate the expected jumble norm distance of the two models in terms of the number of vertices $n$. We present a coupling for which the expectation can be bounded from above by $O(\log^{3/2} n\cdot n^{-1/2})$, and provide a universal lower bound that is coupling-independent, but without the logarithmic term.

Actions (login required)

Edit Item