An example of graph limits of growing sequences of random graphs

DOI10.4310/JOC.2013.V4.N1.A3MaRDI QIDQ2443436zbMATH OpenFDO

Authors S. Jansen, Simone Severini

Publication date 7 April 2014

Published in Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

graph limitsgrowing graphrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: We consider a class of growing random graphs obtained by creating vertices sequentially one by one: at each step, we choose uniformly the neighbours of the newly created vertex; its degree is a random variable with a fixed but arbitrary distribution, depending on the number of existing vertices. Examples from this class turn out to be the ER random graph, a natural random threshold graph, etc. By working with the notion of graph limits, we define a kernel which, under certain conditions, is the limit of the growing random graph. Moreover, for a subclass of models, the growing graph on any given n vertices has the same distribution as the random graph with n vertices that the kernel defines. The motivation stems from a model of graph growth whose attachment mechanism does not require information about properties of the graph at each iteration.

Review text

This paper studies graph limits of growing sequences of random graphs. The graphs grow as follows. At each step we add one node, and the neighbors of the new node are chosen uniformly, and the number is a random variable with a fixed but arbitrary distribution depending on the number of nodes already present. Some examples of such random graphs are examined within the framework of graph limits. A kernel is defined in order to discover the limit of the growing random graph. It is shown that the growing graph on \(n\) nodes can have the same distribution as the random graph with \(n\) nodes that the kernel defines. Some open problems are also discussed.

Recommendations

• Limits of randomly grown graph sequences
• Threshold graph limits and random threshold graphs
• Generating infinite random graphs
• On limits of sparse random graphs
• Continuum limits for classical sequential growth models

Cited in

(10)

• On the likelihood of forests
• Limits of random trees. II
• Limit of a nonpreferential attachment multitype network model
• Continuum limits for classical sequential growth models
• Co-evolution of networks and quantum dynamics: a generalization of preferential attachment
• Threshold graph limits and random threshold graphs
• Out-of-equilibrium random walks
• Generating infinite random graphs
• A random graph growth model
• Limits of randomly grown graph sequences

This page was built for publication: An example of graph limits of growing sequences of random graphs

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