A Geometric Preferential Attachment Model of Networks Ⅱ

摘要

A detailed understanding of expansion in complex networks can greatly aid in the design and analysis of algorithms for a variety of important network tasks, including routing messages, ranking nodes, and compressing graphs. This has motivated several recent investigations of expansion properties in real-world graphs and also in random models of real-world graphs, like the preferential attachment graph. The results point to a gap between real-world observations and theoretical models. Some real-world graphs are expanders and others are not, but a graph generated by the preferential attachment model is an expander whp. We study a random graph G_n that combines certain aspects of geometric random graphs and preferential attachment graphs. This model yields a graph with power-law degree distribution where the expansion property depends on a tunable parameter of the model. 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 inx_1,x_2, … ,X_(t-1)….