Research work · 2006
A Geometric Preferential Attachment Model of Networks
Abraham D. Flaxman, ALAN M. FRIEZE, Juan C. Vera
Internet Mathematics
Abstract
We study a random graph _Gn_ that combines certain aspects of geometric random graphs and preferential attachment graphs. The vertices of _Gn_ are _n_ sequentially generated points _x_1, _x_2, . . . , _x_n chosen uniformly at random from the unit sphere in ℝ3. After generating _xt_, we randomly connect that point to _m_ points from those points in _x_1, _x_2, . . . , _xt_-1 that are within distance _r_ of _xt_. Neighbors are chosen with probability proportional to their current degree, and a parameter a biases the choice towards self loops. We show that if _m_ is sufficiently large, if _r_ ≥ ln _n/n_1/2-β for some constant _β_, and if α > 2, then with high probabilty (whp) at time n the number of vertices of degree _k_ follows a power law with exponent α + 1. Unlike the preferential attachment graph, this geometric preferential attachment graph has small separators, similar to experimental observations of [Blandford et al. 03]. We further show that if _m_ ≥ _K_ ln _n_, for _K_ sufficiently large, then _Gn_ is connected and has diameter _O_(ln _n/r_) whp.