Loading...
Please wait, while we are loading the content...
Similar Documents
Diameters in preferential attachment models (2009).
| Content Provider | CiteSeerX |
|---|---|
| Author | Hofstad, Remco Hooghiemstra, Gerard |
| Abstract | In this paper, we investigate the diameter in preferential attachment (PA-) models, thus quantifying the statement that these models are small worlds. There is a substantial amount of literature proving that, in quite generality, PA-graphs possess power-law degree sequences with exponent τ> 2. The models studied here are such that edges are attached to older vertices proportional to the degree plus a constant, i.e., we consider linear PA-models. We prove that the diameter is bounded by a constant times log t, where t is the size of the graph. When the power-law exponent τ exceeds 3, then we also log t log log t prove a lower bound of the form, while when τ ∈ (2, 3), we improve the upper bound to a constant times log log t. These bounds are consistent with predictions by physicists that the distances in PA-graphs are similar to the ones in other scale-free random graphs, where distances have been shown to be of order log log t, when τ ∈ (2, 3), and of order log t when τ> 3. 1 |
| File Format | |
| Publisher Date | 2009-01-01 |
| Access Restriction | Open |
| Subject Keyword | Preferential Attachment Model Power-law Exponent Pa-graphs Posse Power-law Degree Sequence Order Log Log Quite Generality Upper Bound Small World Preferential Attachment Constant Time Log Substantial Amount Order Log Constant Time Log Log Linear Pa-models Scale-free Random Graph |
| Content Type | Text |
