Preferential Attachment and Vertex Arrival Times

Abstract

We study preferential attachment mechanisms in random graphs that are parameterized by (i) a constant bias affecting the degree-biased distribution on the vertex set and (ii) the distribution of times at which new vertices are created by the model. The class of random graphs so defined admits a representation theorem reminiscent of residual allocation, or "stick-breaking" schemes. We characterize how the vertex arrival times affect the asymptotic degree distribution, and relate the latter to neutral-to-the-left processes. Our random graphs generate edges "one end at a time", which sets up a one-to-one correspondence between random graphs and random partitions of natural numbers; via this map, our representation induces a result on (not necessarily exchangeable) random partitions that generalizes a theorem of Griffiths and Spanó. A number of examples clarify how the class intersects with several known random graph models.

34 pages, 1 figure

References in corpus (7)

• Emergence of scaling in random networks
• Sparse graphs using exchangeable random measures
• Are Gibbs-type priors the most natural generalization of the Dirichlet process?
• The Class of Random Graphs Arising from Exchangeable Random Measures
• Edge exchangeable models for network data
• On edge exchangeable random graphs
• Generalized Mittag Leffler distributions arising as limits in preferential attachment models

Cited by in corpus (4)

• A Preferential Attachment Model for the Stellar Initial Mass Function
• Sampling and Inference for Beta Neutral-to-the-Left Models of Sparse Networks
• Weak local limit of preferential attachment random trees with additive fitness
• Gibbs Partitions, Riemann-Liouville Fractional Operators, Mittag-Leffler Functions, and Fragmentations Derived From Stable Subordinators