Coupling Scale-Free and Classical Random Graphs

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