*banner
 

Coupling Scale-free and Classical Random Graphs
B. Bollobas, A.D. Scott

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

Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess