Justifying the small‐world phenomenon via random recursive trees1. Issue 2 (7th March 2016)

• Record Type: Journal Article
• Authors: Mehrabian, Abbas
• Is Part Of: Random structures & algorithms. Volume 50:Issue 2(2017)
• Page Start: 201
• Page End: 224
• Publication Date: 2016-03-07
• Subjects: small‐world phenomenon -- random recursive trees -- preferential attachment -- diameters of random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20648
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. The advantage of the technique is three‐fold: it is quite simple and provides short proofs, it is applicable to a broad variety of models including those incorporating preferential attachment, and it provides bounds with small constants. We illustrate this by proving, for the first time, logarithmic upper bounds for the diameters of the following well known models: the forest fire model, the copying model, the PageRank‐based selection model, the Aiello‐Chung‐Lu models, the generalized linear preference model, directed scale‐free graphs, the Cooper‐Frieze model, and random unordered increasing k ‐trees. Our results shed light on why the small‐world phenomenon is observed in so many real‐world graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 201–224, 2017