@inproceedings{berger2003degree,
author = {Berger, Noam and Bollobas, Bela and Borgs, Christian and Chayes, Jennifer and Riordan, Oliver},
title = {Degree Distribution of the FKP Network Model},
booktitle = {Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science},
year = {2003},
month = {January},
abstract = {Recently, Fabrikant, Koutsoupias and Papadimitriou [7] introduced a natural and beautifully simple model of network growth involving a trade-o between geometric and network objectives, with relative strength characterized by a single parameter which scales as a power of the number of nodes. In addition to giving experimental results, they proved a power-law lower bound on part of the degree sequence, for a wide range of scalings of the parameter. Here we prove that, despite the FKP results, the overall degree distribution is very far from satisfying a power law. First, we establish that for almost all scalings of the parameter, either all but a vanishingly small fraction of the nodes have degree 1, or there is exponential decay of node degrees. In the former case, a power law can hold for only a vanishingly small fraction of the nodes. Furthermore, we show that in this case there is a large number of nodes with almost maximum degree. So a power law fails to hold even approximately at either end of the degree sequence range. Thus the power laws found in [7] are very different from those given by other internet models or found experimentally [8].},
url = {http://approjects.co.za/?big=en-us/research/publication/degree-distribution-fkp-network-model/},
pages = {725-738},
edition = {Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science},
}