Robustness of Preferential Attachment Under Deletion of Edges

Abstract

The effect of deletion of old edges in the preferential attachment model introduced by Barabási and Albert ^[1] is studied. We consider a model where every edge is deleted after a time Δ. The resulting graph has only Δ edges and with a high probability (1 + c) Δ nodes for some positive c. However, its structure doesn't resemble the structure of the former model even for large Δ. In particular, we prove that the expected degrees of the resulting graph are uniformly bounded by a constant that does not depend on Δ. We discuss applications of our model for the evolution of networks where competition occurs.

Keywords:

• Preferential attachment
• Random graphs

Mathematics Subject Classification:

• Primary 05C80
• Secondary 60J10

ACKNOWLEDGMENTS

The author thanks Tatyana Turova for helpful comments and stimulating discussions on several aspects of the problem. The author also thanks the referee for helpful remarks.