A Geometric Preferential Attachment Model of Networks

摘要

We study a random graph G_n that combines certain aspects of geometric random graphs and preferential attachment graphs. The vertices of G_n are n sequentially generated points x_1, x_2,... ,x_n chosen uniformly at random from the unit sphere in R~3. After generating x_t, we randomly connect it to m points from those points in x_1, x_2,... ,x_(t-1) which are within distance r. Neighbours are chosen with probability proportional to their current degree. We show that if m is sufficiently large and if r > log n~(1/2-β) for some constant β then whp at time n the number of vertices of degree k follows a power law with exponent 3. Unlike the preferential attachment graph, this geometric preferential attachment graph has small separators, similar to experimental observations of. We further show that if m ≥ K log n, K sufficiently large, then G_n is connected and has diameter O(m/r) whp.