Citation
B. Bollobas, A.D. Scott. "Coupling Scale-free and Classical Random Graphs". Internet Math, 14(2):215-225, 2003.

Abstract
Recently many new "scale-free" random graph models have been introduced, motivated by the power-law degree sequences observed in many large-scale real-world networks. The most studied of these is the Barabási-Albert model, made precise as the LCD model by the present authors. Here we use coupling techniques to show that in certain ways the LCD model is not too far from a standard random graph; in particular, the fractions of vertices that must be retained under an optimal attack in order to keep a giant component are within a constant factor for the scale-free and classical models.

Electronic downloads

• http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.im/1089229509&page=record

• HTML

  B. Bollobas, A.D. Scott. <a
  href="http://chess.eecs.berkeley.edu/pubs/726.html"
  >Coupling Scale-free and Classical Random
  Graphs</a>, <i>Internet Math</i>,
  14(2):215-225,  2003.

• Plain text

  B. Bollobas, A.D. Scott. "Coupling Scale-free and
  Classical Random Graphs". <i>Internet
  Math</i>, 14(2):215-225,  2003.

• BibTeX

  @article{BollobasScott03_CouplingScalefreeClassicalRandomGraphs,
      author = {B. Bollobas and A.D. Scott},
      title = {Coupling Scale-free and Classical Random Graphs},
      journal = {Internet Math},
      volume = {14},
      number = {2},
      pages = {215-225},
      year = {2003},
      abstract = {Recently many new "scale-free" random graph models
                have been introduced, motivated by the power-law
                degree sequences observed in many large-scale
                real-world networks. The most studied of these is
                the Barabási-Albert model, made precise as the
                LCD model by the present authors. Here we use
                coupling techniques to show that in certain ways
                the LCD model is not too far from a standard
                random graph; in particular, the fractions of
                vertices that must be retained under an optimal
                attack in order to keep a giant component are
                within a constant factor for the scale-free and
                classical models.},
      URL = {http://chess.eecs.berkeley.edu/pubs/726.html}
  }
  

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