Citation
Noam Berger, Bela Bollobas, Christian Borgs, Jennifer Chayes, Oliver Riordan. "Degree Distribution of the FKP Network Model". ICALP 2003 International Colloquium on Automata, Languages and Programming, 306-316, 2003.

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.

Electronic downloads

• http://dx.doi.org/10.1007/3-540-45061-0_57

• HTML

  Noam Berger, Bela Bollobas, Christian Borgs, Jennifer
  Chayes, Oliver Riordan. <a
  href="http://chess.eecs.berkeley.edu/pubs/722.html"
  >Degree Distribution of the FKP Network Model</a>,
  ICALP 2003 International Colloquium on Automata, Languages
  and Programming, 306-316, 2003.

• Plain text

  Noam Berger, Bela Bollobas, Christian Borgs, Jennifer
  Chayes, Oliver Riordan. "Degree Distribution of the FKP
  Network Model". ICALP 2003 International Colloquium on
  Automata, Languages and Programming, 306-316, 2003.

• BibTeX

  @inproceedings{BergerBollobasBorgsChayesRiordan03_DegreeDistributionOfFKPNetworkModel,
      author = {Noam Berger and Bela Bollobas and Christian Borgs
                and Jennifer Chayes and Oliver Riordan},
      title = {Degree Distribution of the FKP Network Model},
      booktitle = {ICALP 2003 International Colloquium on Automata,
                Languages and Programming},
      pages = {306-316},
      year = {2003},
      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.},
      URL = {http://chess.eecs.berkeley.edu/pubs/722.html}
  }
  

Posted by Christopher Brooks on 4 Nov 2010.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.