1206.4586 (Svante Janson et al.)

An example of graph limits of growing sequences of random graphs    [PDF]

Svante Janson, Simone Severini

We consider in this note 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 Erdos-Renyi 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 has for any given number of vertices n 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.

View original: http://arxiv.org/abs/1206.4586