Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
A Geometric Preferential Attachment Model of Networks II
| |
|
A Geometric Preferential Attachment Model of Networks II
Abraham D. Flaxman1, Alan M. Frieze1 and Juan Vera1
| (1) |
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA15213, U.S.A. |
Abstract
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
. After generating x
t
, we randomly connect it to m points from those points in x
1, x
2,..., x
t − 1 ....
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|