Paper Info
Title
Degree distribution of the FKP network model
Abstract
Power laws, in particular power-law degree distributions, have been observed in real-world networks in a very wide range of contexts, including social networks, biological networks, and artificial networks such as the physical internet or abstract world wide web. Recently, these observations have triggered much work attempting to explain the power laws in terms of new 'scale-free' random graph models. So far, perhaps the most effective mechanism for explaining power laws is the combination of growth and preferential attachment. In [A. Fabrikant, E. Koutsoupias, C.H. Papadimitriou, Heuristically optimized trade-offs: A new paradigm for power laws in the internet ICALP 2002, in: LNCS, vol. 2380, pp. 110-122], Fabrikant, Koutsoupias and Papadimitriou propose a new 'paradigm' for explaining power laws, based on trade-offs between competing objectives. They also introduce a new, simple and elegant parametrized model for the internet, and prove some kind of power-law bound on the degree sequence for a wide range of scalings of the trade-off parameter. Here we shall show that this model does not have the usual kind of power-law degree distribution observed in the real world: for the most interesting range of the parameter, neither the bulk of the nodes, nor the few highest degree nodes have degrees following a power law. We shall show that almost all nodes have degree 1, and that there is a strong bunching of degrees near the maximum.
Year
DOI
Venue
2007
10.1016/j.tcs.2007.02.049
ICALP
Keywords
DocType
Volume
degree distribution,network model,power law,satisfiability,maximum degree,lower bound,exponential decay,degree sequence
Journal
379
Issue
ISSN
ISBN
3
0304-3975
3-540-40493-7
Citations 
PageRank 
References 
19
1.49
6
Authors
5
Name
Order
Citations
PageRank
Noam Berger112919.76
Béla Bollobás22696474.16
Christian Borgs31311104.00
Jennifer T. Chayes41283103.28
Oliver Riordan5618.19