×

zbMATH — the first resource for mathematics

Geometric preferential attachment in non-uniform metric spaces. (English) Zbl 1283.05249
This paper deals with models of random graphs which have both an element of being ‘geometric’, in the sense that, as the graph evolves, the probability that a new vertex is adjacent to an existing vertex depends on their proximity to each other (they are put down randomly in some suitable metric space), but also a \` preferential attachment element\' in that the probability of adjacency depends on the degree of the existing vertex. Models of this sort were initially developed around 2006 by Flaxman, Frieze and Weiss in two papers. The author [Adv. Appl. Probab. 42, No. 2, 319–330 (2010; Zbl 1210.05158)] showed, under non-trivial assumptions both on the probability measure determining where the vertices are put down in the metric space and the strength of the effect of distance on connection probabilities, that the limiting proportion of vertices with degree \(d\) is the same as in the (rigorous formulation of) the Barabási-Albert model in [B. Bollobás et al., Random Struct. Algorithms 18, No. 3, 279–290 (2001; Zbl 0985.05047)].
The paper under review extends the author’s earlier results in two directions: firstly by weakening the assumption that the measure of the open ball of radius \(r\) round a point \(x\) of the metric space be independent of \(x\): this can lead to degree distribution being similar to that found in the model of preferential attachment with multiplicative fitness considered in [C. Borgs and J. Chayes, in: Proceedings of the 39th annual ACM symposium on theory of computing, San Diego, CA, USA, STOC 07. New York, NY: Association for Computing Machinery (ACM) 135–144 (2007; Zbl 1232.68018)].
The other extension is to make the attractiveness of a vertex at location \(x\) to one at vertex \(y\) be not necessarily the same as the attractiveness of one at vertex \(y\) to one at vertex \(x\): in other words, to introduce asymmetry to the notion of attractiveness.
We omit detailed statements of these main results as they are technical. The proofs work by starting with the underlying metric space being finite, and using stochastic approximation techniques to show convergence of measures, and then using a coupling argument to extend to the infinite case.

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
60D05 Geometric probability and stochastic geometry
PDF BibTeX XML Cite
Full Text: DOI arXiv